noooo I want yesterday's rating please this one killed me:(

i did same for a but it give me wrong aaaaahhh

btw great tutorial like what i am thinking thanks

A was very tricky for me to prove that such strategy gives minimum moves.

Questions were really good.

For the case 110100, we can take i = 1, j = 3, k = 4 and the string will become 111000 which is sorted but the answer given in test case is 2 steps

Got clapped but round was nice, thanks !

Hey can anyone tell me what is wrong in my approach. And please while pointing out my mistake, tell me how to think in the way to get to the approach mentioned in the editorial. It would be of great help to me. 337853452

What's case 1 in editorial for F? Doesn't [3, 0, 1] fall into case 1, but allow only 1 single operation?

337862621

any clue why my code keeps wrong? give me hint plz

For B , I just saw the consistent occurances of 12/3 , 102/3 , 1002/3 , then i realized that 3 would always divide the numbers having sum of digits factors of 3 , so therefore 2.x is the best solution here

I solved B by observing the pattern and got y = 10^9 - 1 - x always works, can anyone prove this

2140B - Another Divisibility Problem can be solved with other values of $$$y$$$ as well, for example $$$y = 999... - x$$$ depending on $$$x$$$. Because,

$$$x \text{#} y = x \cdot 10^d + y = x \cdot (10^d − 1) + (x + y)$$$

So, to make the $$$10^d - 1$$$, which is basically $$$9999...$$$ for $$$d$$$ times, to be divisible by $$$x + y$$$, we can make $$$x + y$$$ itself be of this shape. For $$$x$$$ to be any $$$k$$$-digit number, $$$x + y$$$ can be of shape with any $$$k$$$ or more digits of $$$9$$$ s. Since the constraints state that $$$x \lt 10^8$$$ and $$$y \lt 10^9$$$, we can set $$$x + y$$$ to be $$$999,999,999$$$ i.e. $$$y = 10^9 - 1 - x$$$.

Also, obviously, $$$y = 8 \cdot x$$$ works for the same reason as tutorial.

Upd: can anybody explain why the downvotes? Cause I'm pretty sure there's nothing wrong in terms of logic cause I literally got AC with this approach. 337798106

E2 Bonus Solution:

What's wrong with my code ? 337868493

Love the reference to my favorite song — "A Cruel Angel's Thesis" by Yoko Takahashi ‧ 1995

My solution to Problem D works as follows: the original problem is equivalent to finding a matching among the intervals $$$1, \cdots, n$$$ that maximizes the value

Using the identity $$$\max(A, B) = \frac{A + B}{2} + \frac{|A - B|}{2}$$$, this expression can be rewritten as

For even $$$n$$$, the first term is constant (equal to half the total sum of the lengths of the intervals), and the second term is maximized by partitioning the array $$$a[j] = r_j + l_j$$$ into two halves and subtracting the sum of the smaller half from the sum of the larger half. This can be computed efficiently using prefix sums in $$$\mathcal{O}(1)$$$ time per query after preprocessing.

For odd $$$n$$$, one interval (say $$$i$$$) remains unmatched. We enumerate each $$$i = 1, \cdots, n$$$ as the unmatched interval, and the value in equation $$$(\star)$$$ can be easily evaluated in $$$\mathcal{O}(1)$$$ time using a similar prefix sum approach with minor modifications, resulting to an $$$\mathcal{O}(n)$$$ solution.

This method is basically identical to the one in the editorial, but more clear to me.

the second problem was a humbling experience for me

can someone explain this part This can be solved by maintain prefix minimum over odd and even indexes.

for problem E, dp[i][mask][1] is actually the same as dp[i][~mask][0]; you can just maintain one

can someone help me understand, why this code of mine for problem C is giving wrong answer, I am not able to understand.

//this is the code

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> ind[2];
    map<ll, vector<ll>> mp0,mp1;
    ll cost = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ind[i % 2].push_back(a[i]);
        if (i % 2 == 0){
            cost += a[i];
            mp0[a[i]].push_back(i);
        }
        else{
            cost -= a[i];
            mp1[a[i]].push_back(i);
        }
    }

    sort(ind[0].begin(), ind[0].end()); // even paratiy
    sort(ind[1].begin(), ind[1].end()); // odd pararity

    ll temp_cost = 0;
    if (n % 2 == 0) temp_cost = n - 2;
    else temp_cost = n - 1;

    if (ind[0].empty() || ind[1].empty()) {
        cout << cost << "\n";
        return;
    }

    ll num1 = ind[1].back();   
    ll num2 = ind[0][0];       

    ll temp_cost2 = 0;
    if (!mp1[num1].empty() && !mp0[num2].empty()) {
        temp_cost2 = num1 - num2 +
            max(abs(mp1[num1][0] - mp0[num2].back()),
                abs(mp0[num2][0] - mp1[num1].back()));
    }
    ll cost2=cost;
    if (temp_cost2 >= temp_cost) {
        cost2 = cost2 + num1 - num2;
        cost2 += temp_cost2;
        //cout << cost << "\n";
    }

    cout<<max(temp_cost+cost,cost2) << "\n"; 
}

For problem C, I used a DP approach. Surprisingly, when I implemented it with a regular array (initialized using memset), it resulted in TLE. However, switching to a map for memoization led to an AC. Could someone explain why this happens?

where balanced paranthesis come from in d editorial??? (*cry emoji)

How can u directly find out left out segment in O(1) in D editorial ??

Oh WOW, that's a fast editorial.

Loved the problems, and I FINALLY became a specialist.

I got the idea of C, but for those who didn't, I think the change in the statement of C gave it away. B was a little hard tho

2140B extended The editorial was prepared together with my coach, after he tried during the contest to brute-force all divisors of $$$10^k-1$$$ and $$$x$$$ and ran into TLE. Submission.

I like how noone mentioned that question 2140D was just an evangelion reference

bro I didn't got yesterday's contest's rating

This is what I got for B and it got accepted lol. If anyone could lmk why this works that would be cool. I was basing this off the fact that both these numbers will be divisible by 3 as both their digit sums would be divisible by 3 and just kinda tested from there and it worked:

#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<long long, long long> > vpll;

const ll INF = 4e18;

void solve() {
  ll x;
  cin >> x; 
  string s = to_string(x);
  bool flag = false;
  if (s[0] == '9') flag = true;
  string y;
  if (flag) y.push_back('9');

  for (int i = 0; i < s.length(); i++) {
    y += to_string('9'-s[i]);
  }

  cout << y << '\n';
} 

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  //cin.ignore(numeric_limits<streamsize>::max(), '\n');
  while(t--) {
    solve();
  }
}

What is wrong in this solution for D:

First we initially compute the sum of all segments , Initial_sum = $$$S = \sum_{i=1}^{n} y_i - x_i$$$ then we want to compute the additional segments length formed by marking these segments, if we sort the $$$l_i$$$'s and $$$r_i$$$'s and then take the sum of (highest $$$r_i$$$ — least $$$l_i$$$) + (2nd highest $$$r_i$$$ — 2nd least $$$l_i$$$) + ..... and add this sum to the Initial_sum

Can someone please explain the solution of E2 after calculating the dp values. How is it calculating the original answer from binary(0, 1)?

You can think of this approach : let's choose y=k*x; Now you can so this :

// you can use all values generated below. you can change 1000 to your number // for 1000 these are valid : 2 8 26 36 100 302 908 // basicaaly formula is to count = 10k/k+1 should be divisible. here 10k is concatination of 10 and k // but here y has limit that can atmost 10*x so we can use only 2 and 8 in this code.

// void solve(){ // ll num=10; // for(ll i=1;i<=1000;i++){ // if(i/num>0) num=num*10; // ll x=num*10+i; // if(x%(i+1)==0){ // cout << i << " "; // } // } // cout << endl; // } ~~~~~ Your code here... ~~~~~

For problem D, a very "neat" way of reaching the greedy conclusion is by expanding the formula of the chosen segments' sum. Let's name the of chosen segments $$$C$$$ and the rest be $$$R$$$.

Our formula is :

If we manage to eliminate contribution of group $$$R$$$ from this equation it will be easy to select group $$$C$$$ to maximize this expression. To do so we can expand the second term, based on this substitution :

Where $$$n$$$ is the input size, by substitution our formula becomes :

Now it's clear to see that maximizing this expression is equivalent to maximizing sum of right and left of a segment, since summation of all lefts is constant.

Can anyone explain what they mean in the solution for problem C when it says

This is very confusing to me.

"In Problem D editorial it says you can directly find the left out segment in O(1) — can someone explain how to actually do that part?"

Here's a brainf*ck solution of 2140B - Another Divisibility Problem for no reason

(Assuming all cells are 32-bit instead of 8-bit as normal, if someone can implement an 8-bit solution I'm more than excited to see it)

[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<
// Inputs the number of testcases
[>
[-]>[-]+[[-]>[-],[+[-----------[>[-]++++++[<------>-]<--<<[->>++++++++++<<]>>[-<<+>>]<+>]]]<]<
// Inputs n
[->++<]>
// Calculate 2*n
>[-]>[-]+>[-]+<[>[-<-<<[->+>+<<]>[-<+>]>>]++++++++++>[-]+>[-]>[-]>[-]<<<<<
[->-[>+>>]>[[-<+>]+>+>>]<<<<<]>>-[-<<+>>]<[-]++++++++[-<++++++>]>>[-<<+>>]<<]
<[.[-]<]<
// Output 2*n
[-]++++++++++.[-]
// Output newline character
<<-
// Decrement testcase number
]

I don't understand the complexity in E1, isn't is supposed to be $$$O(n^2 \cdot 2^n)$$$, because of the for loop over "good" vector?

taskkill /f /im libmain.exe && taskkill /f /im xhost.exe

Hello, My account was recently flagged for cheating in this round. I would like to clarify my situation.

I did not share my code with anyone, nor did I copy from others. I usually keep my solutions locked, but I understand now that similarity in code can happen naturally since many problems have standard approaches. This might have caused suspicion.

I respect Codeforces and its rules, and I never intended to violate them. If my actions caused unintentional leakage or misunderstanding, I sincerely apologize. I will be more careful in the future to avoid such issues.

I kindly request the admins to review my case. Thank you for your time and understanding.

Similar problem for B from Project Euler. Editorial

In the editorial for problem D, I dont understand:

My question being

Thanks a lot in advance!

Problem C: I'm not quite sure how you're meant to use prefix sums. Can anyone explain?

I instead (338651248) used an approach along the lines of "for each + element, what's the best — element to swap it with?". Explaining exactly how I did it is difficult, but essentially it works by considering how the distances (i.e. abs(l-r)) between + elements and — elements change as you iterate over the + elements.

For problem F, is y taken to be the absolute value of x — floor(x/k)*k? I'm not sure if it's ever possible to get infinitely decreasing sum otherwise.

for problem "another divisibility problem" doesnt x#x % x = 0? so returning x always works, nowhere in the problem can I find something that forbids you from doing that. it can be mathematically proven that x#x % x = 0:

let x be = 42 for example

4242 % 42 = (42 *10^2 + 42) % 42

42(10^2+1) % 42

this equals to zero since 10^2 +1 is an integer, that number multiplied by 42 is divisible by 42. this works for all numbers as long as 2 is substituted by the number of digits x has.

I think there's a slight logical error in Case 2 in the editorial for F. The editorial asserts that if any operation can be performed on the last n-1 elements of the array, then performing that operation will take us to Case 1. This is not true when the operation only modifies one element and that element is equal to the minimum of the array. For example, consider the array [1, 1, 3, 3]. We can perform an operation on the three larger elements, which makes the array [0, 1, 3, 3], which does not fall under Case 1.

The reason the model solution still works is that if this happens, then we can perform the same operation again, replacing the element that was decreased with the original minimum element of the array. At this point, we have two occurrences of the original minimum — 1, so we have an element other than $$$a_1$$$ with the opposite parity of the elements of the original array, putting us into Case 1.

I don't understand this :

for (int r = 1; r <= n; r++)
{   
    for(int k=1;k<=m;k++){
        finans += (((binpow(k-1,n-r)*binpow(m-k+1,r))%MOD) * (cnt[pl][n][r]))%MOD;
    }
}
cout << finans%MOD << endl;

Why is the result calculated this way?

what is wrong with this approach for C-

import sys
input = sys.stdin.readline
MOD = 1_000_000_007

def ans():
  n = int(input())
  l = list(map(int, input().split()))
  s = x = y = 0
  m = 1_000_000_007
  ma = -1_000_000_007

  for j in range(n):
    if j % 2 == 0:
      s += l[j]
      if (2*l[j] + j) < m:
        m, y = (2*l[j] + j), j
    else:
      s -= l[j]
      if (2*l[j] + j) > ma:
        ma, x = (2*l[j] + j), j

  xa = ya = 0
  mr = 1_000_000_007
  maa = -1_000_000_007

  for j in range(1, n+1):
    if (n - j) % 2 == 0:
      if (2*l[-j] + j - 1) < mr:
        mr, ya = (2*l[-j] + j - 1), n - j
    else:
      if (2*l[-j] + j - 1) > maa:
        maa, xa = (2*l[-j] + j - 1), n - j

  u1 = ma - m
  u2 = maa - mr  
  u = max(u1, u2)
  return s + max(u, (n - 1 - (n + 1) % 2))

for _ in range(int(input())):
  print(ans())