0doO's blog

By 0doO, history, 5 weeks ago, In English

Thank you for taking part in our contest, we know leaves a lot to be desired. But we believe that you can find interesting among our problems.

A. Nene's Game

Idea: Otomachi_Una

Tutorial
Solution

B. Nene and the Card Game

Idea: Otomachi_Una

Hint
Tutorial
Solution

C. Nene's Magical Matrix

Idea: Otomachi_Una

Hint
Tutorial
Proof
Solution

D. Nene and the Mex Operator

Idea: Otomachi_Una

Hint
Tutorial
Solution

E. Nene vs. Monsters

idea: Otomachi_Una

Hint1
Hint2
Hint3
Tutorial
Solution

F. Nene and the Passing Game

idea: Otomachi_Una

Hint
Tutorial
Solution
  • Vote: I like it
  • +98
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by 0doO (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

I didn't see the meaning of splitting E into E1 and E2, the difference is only $$$k=2$$$ and $$$k=3$$$... The pretests of both problems are so weak, and the time limit for E2 is tight. (upd: seems that std::set has too large constant, and I should use list.)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not tight.. my solution runs only 300ms during the testing.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Not exactly. E1 has a simpler solution. Brute force until no more than 2 consecutive monsters, and for all the consecutive monsters, only the first one will survive. The time complexity is $$$O(n\sqrt(V))$$$. So you don't need to handle three consecutive monsters, which involves some math calculations. In my case, I wrote a binary search + matrix multiplication to deal with <=4 consecutive monsters which is dumb.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      True

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In fact,E2 also has a simpler solution.Brute force until no more than 3 consecutive monsters,and it's easy to do that.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What's the difference between this and E2? If you can handle the <= 2 case, it will be easy to handle the <= 3 case too.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        But it seems that many participants passed E1 but not E2.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Not everyone solved them like in the tutorial. Some of them only make guesses following their intuition and they can pass E1 not E2. Like recursing on the continuous segments, if you recurse until the length of the segment is only 1, it is easy to hack, and the data would be like 0 1 100000 repeated. But if you recurse until the length<=2 then stop, it seems hard to hack and yet the participants don't know what is the time complexity and it passes E1. When it comes to E2, the participants are not brave enough to guess that if they stop at length<=3 they will pass.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by 0doO (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Very well explained. Thanks!

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

thx for the tutorial u r amazing guys and now i'm specialist

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lichenghan (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

I became pupil, feels good!

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I became expert, feels good!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you for such an amazing round. I'm so happy because this was my best ever codeforces round. Solved 3 and placed 2.3k. Thank you so much Chinese boy

»
5 weeks ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Thanks for the fast tutorial. It's interesting in 1956D - Nene and the Mex Operator to be able to change all values of any k consecutive elements to k

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yeah! Then bitmask to see which values we should keep, and convert all other ranges to their length squared! Incredibly cool problem.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Very cool problem indeed! I especially like the tower-of-hanoi-like construction of the k consective elements of k with MEX.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do we actually check which elements to keep and whom to add in the range?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You literally just check all $$$2^n$$$ possibilities by iterating over all subsets and checking the maximum value.

        Have a look at this (starting from the main function, you can ignore all other functions as they’re related to the construction of the sequence of operations rather than the answer)

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oo damn. The tutorial said something about dp and i was stick on that. Thanks

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can do DP as well: 256761916. I would not recommend it though, because it is quite complicated and error-prone, and checking all subsets is simply a less risky way (in contest).

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ayush2321 avighnakc hashman I actually neither used bitmask nor dp, instead, I used a greedy approach where I always took the segment the got me the highest increase.

              Here's the code for it:
              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Can you please explain your greedy solution?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Sure, since I already know that for each segment of length k I can make its sum = k^2. I check all possible segments and take the segment that has the maximum increase = k^2 — original_sum

                  Update this segment and then look again for other segments and stop when there's no segment with positive increase

                  The complexity of this I assume is n^2 * (number_of_segments_changed + 1) which total is less than n^3

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                <spoiler summary="ll n; cin>>n; vectora(n); for(ll i=0;i<n;i++) cin>>a[i]; vectorpref(n+1,0); pref[0]=0; pref[1]=a[0]; for(ll i=2;i<=n;i++) pref[i]=pref[i-1]+a[i-1]; // cout<<pref[n]<<ln; vector<pair<ll,ll>>ans; ll i=0; ll sol=0; while(i<n) { ll flag=0; for(ll j=n;j>i;j--) { ll len=j-i; ll sum=pref[j]-pref[i]; // cout<<sum<<" "; if(len*len>sum) { sol+=len*len; // cout<<sol<<" "; ll temp=j; // cout<<temp<<" "; ll flag1=0; while(temp>i+1) { ans.push_back({i+1,temp}); ans.push_back({temp,temp}); temp--; } ans.push_back({i+1,j}); i=j; flag=1; break; } } if(flag==0) { sol+=a[i]; i++; } } cout<<sol<<" "<<ans.size()<<ln; for(auto it:ans){ cout<<it.first<<" "<<it.second<<ln; }"> ...

                I almost used same method but I am getting wrong answer. could you help me ??

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  The thing we discussed here is only how to get the best sum, constructing the operations needed to achieve this answer is more complicated than what you did.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the proof section of the editorial for C, is there a chance that you've mixed up the assignments?

If $$$x=n$$$ or $$$y=m$$$, the conclusion holds.

This should be $$$x=m$$$ or $$$y=n$$$, right?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by 0doO (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is the intuition behind knowing that you need to construct this matrix in problem C?
1 2 3 ... n
2 2 3 ... n
3 3 3 ... n
...............
n n n ... n

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is a little easier to think about performing the operations in reverse. Intially you have

    0 0 0 0
    0 0 0 0
    0 0 0 0
    0 0 0 0
    

    Then, using the permutation 1, 2, 3, 4, perform the operation on the first row and column

    1 2 3 4
    2 0 0 0
    3 0 0 0
    4 0 0 0
    

    Using the permutation on the second row and column:

    1 2 3 4
    2 2 3 4
    3 3 0 0
    4 4 0 0
    

    Notice that I didn't overwrite the previous values at a[1][2] and at a[2][1]. This is because I'm performing the operations in reverse, so the one I perform first will be the one that lasts. Doing this on the third row and column gives:

    1 2 3 4
    2 2 3 4
    3 3 3 4
    4 4 4 0
    

    and finally fourth row (or column; in reality you only need $$$2n-1$$$ operations)

    1 2 3 4
    2 2 3 4
    3 3 3 4
    4 4 4 4
    

    which gets you your answer.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      But how can you arrive at the conclusion that you need to construct that matrix in the first place? Constructing the matrix itself is easy.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I arrived at that conclusion by brute forcing smaller cases ($$$n=3$$$ and $$$n=4$$$). It looked like a pattern arose, and I couldn't seem to improve it further, so yeah.

        If you're interested, the editorial also proves that this answer is optimal.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        During the round I tried to act greedily, I wanted to build a 4 * 4 table entirely from elements equal to 4. After looking at the cases, I realized that there are a maximum of 7 such elements. And then, using this logic, you can complete the corners and get a table one larger in size. (In my opinion, in such problems you need to write everything down on a piece of paper and you certainly don’t need to strictly prove everything)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    There's no intuition, just guessing without proof. It's a bad problem

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Though the proof in the editorial is quite clear, it's hard for everyone to actually think about it in a contest.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Define g(x) as the number of elements in the matrix equal to x.

        Given n,

        It remains to prove that g(x) >= 2*x - 1, for x = 1 ... n ?

        Then you can prove the recurrence f(x+1) = f(x) - g(x) <= n^2 - x^2 from the assumption f(x) <= n^2 - (x-1)^2

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Unfortunately, such problems are only becoming more frequent :(

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My thoughts: since we're replacing each row and value with permutations, we can simply give 1, 2, ..., n to every row (left -> right) and every column (up -> down). Other permutations are equivalent. Then, for every a[i][j], the maximum possible value you can get is max(i, j), which corresponds to the matrix.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For me there is some intuition. Let me try to explain

    You can try to think greedily: for some number $$$x$$$, how many times do you think it's possible for $$$x$$$ to appear in the final matrix? My intuition say it should appear at most $$$2n - 1$$$ times because you can only set rows and columns permutations from $$$1$$$ to $$$n$$$.

    Now which number should you assign to $$$x$$$? Again my intuition says it should be the maximum number in the permutation which is $$$n$$$.

    Now since I used $$$2n - 1$$$ of my $$$n's$$$. I'm left with $$$n^2 - 2n + 1$$$ spots left in the matrix. Which is equal to $$$(n-1)^2$$$, and my permutation cannot contain $$$n$$$ anymore. Notice that you're left with the same problem above, but with $$$n = n - 1$$$.

    My intuition says that if I follow this logic, my final matrix should look like:

     1 2 3 ... n
    2 2 3 ... n
    3 3 3 ... n
    ...........
    n n n ... n
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

The sum over all the elements of the matrix in problem C can be calculated by $$$\frac{n * (n + 1) * (4*n - 1)}{6}$$$, here’s the link to OEIS, although I can’t figure out why this is the exact sequence, I wonder if some of you guys would be so kind as to explain it to me.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    This is the sequence because the optimal matrix is always

    1 2 3 ... n
    2 2 3 ... n
    3 3 3 ... n
    ..... ... n
    n n n n n n
    

    and $$$\displaystyle \sum_{i=1}^{n} i(2i-1) = \frac{n(n+1)(4n-1)}{6}$$$ (see WolframAlpha)

    You can also derive this yourself by rewriting $$$\displaystyle \sum_{i=1}^{n} i(2i-1) = 2 \sum_{i=1}^{n} i^2 - \sum_{i=1}^{n} i = 2\frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2} = \frac{n(n+1)(4n-1)}{6}$$$

»
5 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

in problem e2 i am getting tle on tc 54. total tc are 56. (very close to optimum approach) could anyone tell me how to resolve tle .

sumbission link:- https://mirror.codeforces.com/contest/1956/submission/256603484

code:- // warning :- the template is big , it can cover your entire page .

Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The link for editorial in contest announcement has a typo

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So many people got E1 by simply simulating the process for a decent number of rounds (say 500). Was this one of the intended approaches for E1?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simply simulating can be hacked using the testcase:

    1 2 1e5 0 1 2 1e5 0 1 2 1e5 ... ...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it can be proven that sqrt(2 * A) simulation is enough for E1 (and also for E2, but its just too large to actually do). If you actually read the editorial, it says that for general k, there needs to be O(A^(1/k)).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are problems put with codeforc.es?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

as per editorial, we define f(x) as the number of elements greater or equal to x. The sum of all elements in the matrix is ∑f(i) because an element with value x will be counted x times in the formula before.

What is the motivation for stating this f(x) ?

I am thinking during n operation how many times I can preserve n then n-1 then n-2 ... and so on, that i figure out this construction.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The motivation is that it helps you prove your intuition. It’s not actually required to solve the problem without a proof.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out task D. My solution is to iterate over a bitmask of length n, which will iterate over the assignment operations. Then I try to make the maximum mex on the segment and update the answer. At the end, I restore the answer.

This is my code: https://mirror.codeforces.com/contest/1956/submission/256538264

Thanks to the authors for a wonderful round!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try this case :

    2

    0 0

    your operation is giving maximum answer 2 . but it is possible to gain 4.

    [0, 0]

    l = 1, r = 2 , the array become [1, 1]

    then l = 1, r = 1 the array become [0, 1]

    finally l = 1, r = 2 the array become [2, 2]

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

easy to cheese F in $$$O(n\log^2{n})$$$ (segtree + small-to-large): 256586729

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's your approach? there's tons of log^2 solutions to F but none of them should pass, crazy that yours does

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Firstly, two nodes $$$i$$$ and $$$j$$$, $$$(i < j)$$$ have an edge iff:

      1. $$$(l_i + l_j\leq j - i) \to (i + l_i \leq j - l_j)$$$
      2. $$$(r_i + r_j\geq j - i) \to (i + r_i \geq j - r_j)$$$

      I will iterate over $$$i$$$ in increasing order, and for each $$$i$$$, I will add edges to all $$$j$$$ such that:

      1. $$$i < j$$$
      2. $$$(i, j)$$$ edge is valid
      3. $$$i$$$ and $$$j$$$ are not in the same connected component in the graph induced by the currently added edges.

      How to add all such edges?

      Sort indices of nodes in increasing order of their $$$j - l_j$$$ value and call this array $$$S$$$. Notice that an edge $$$(i, j)$$$ can be trivially found by checking if the minimum value of $$$j - r_j$$$ on a particular suffix of $$$S$$$ is $$$\leq i + r_i$$$. We will speed this process up using a segment tree.

      Build a segment tree upon $$$S$$$, where you store the value $$$j - r_j$$$ at the location of index $$$j$$$. The segment tree needs to support two things:

      1. Querying some suffix for the two elements with smallest values of $$$j - r_j$$$ such that both are currently in different components.
      2. Updating the component representative of some node.

      It is easy to build such a segment tree.

      Now, you just iterate over $$$i$$$ in increasing order, find an edge $$$i \to j$$$ if it exists, and if it does, then you will merge the smaller component into the larger component and update the component representative of all nodes in the smaller component in the segment tree.

      I used some problem specific things to optimise the iterative segment tree, and some other bs to somehow get it to pass.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        crazy

        I added some asserts in your merge function and sum of all dsu movings is less than 2*N for all cases, so your solution is effectively nlogn for these testcases.

        Not sure why. Perhaps weak test cases / hard to generate counterexample, but there's also a lot of structure to the queries: you're basically "adding points" above the diagonal and doing "merge queries" below the diagonal (look at the conditions relative to the point (i, i)), and they're sort of "reflected" across this line (in the opposite way of how you would usually view it).

        Not sure what that means for the structure, would be very cool if you could prove some kind of bound on this process, seems hard though.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I think segment tree is overkill.Instead, we can use priority queue My code

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yup, this relies on the observation that the order of "range merges" and "point add query" don't matter, since point add queries will only ever add points to the right of (i, i), while its query is always to the to the left of (i, i), so no need to do anything w/ dynamic data structures. only realized that this morning.

          i suppose the whole 2d merging thing is a roundabout way to arrive at the editorial's first observation then, lol

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for fast editorial

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

256520814,please anyone can help me with this ,I am not able to understand why am I getting wrong submission at test 3.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    1<<num will overflow. num can be as high 200000.

    Why are you calculating duplicates that way by the way ? You can simply use a map.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is optimal strategy to make strong tests for problem E?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that number of contestants is not that big so the number of solutions they may provide is very small and during contest kick it by some tests, but jokes apart that is difficult things to do from the side of jury and before the contest to find out what kinds of solutions could be almost not probable and that makes competitive programming so challenging and so weird sometimes due to weak test data..

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess another question is how to construct a testcase such that it takes about V^{1/k} turns to have no consecutive k monsters alive. I think(?) some of the FST on E2 came from people simulating not enough steps.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me out with my code for E1/E2. (WA on tc 2)

Here is my submission 256685619

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider the case: n = 5 and a[N] = {5,6,0,0,4}

    With your approach, the answer is a[2] and a[5] while the real answer is only a[5]

    The difference is because you didn't add

    for(int p=1;p<=n;p++) 
        if(a[p]&&a[p%n+1]) 
            a[p%n+1]=max(0,a[p%n+1]-a[p]);
        else break;
    

    after checking that there are no four consecutive non-zero numbers.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C was cray cray

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Struggling to understand how does induction step work here for proof of Problem C:

Otherwise, if the last operation is to paint a row, then this row has exactly $$$m−x$$$ black cells. And, by induction, other rows will contain at most $$$(n−1)m−x(y−1)$$$ black cells. Painting a column in the last step is similar.

Would really appreciate if someone could elaborate this proof.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

A very good competition but D"s print is hard.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain this line of the editorial of the problem E?

If four consecutive monsters have energy level x, y, z, w (x, y, z, w > 0) and they did not die after t rounds of spells, then y will receive at least t points of damage, z will receive at least (t-1) + (t-2) + ... = O(t^2) of damage, and w will receive at least O(t^3) of damage.

That is to say, let V = max(ai) for i = 1 to n, after O(V^(3/2)) rounds, at least one of x, y, z, w will die.

at least o(t^2) means?? what does it want to convey?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

cool problem D. i enjoyed the process of coming up with idea to construct the sequence

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, what does operate really do? I still don't understand T_T

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's just setting the segment $$$[L,R]$$$ in the array to its $$$MEX$$$

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is the solution is finding from all subset ( 2^N possibilities ), we change the subarray in which in the set is "turned on" to become the MEX and leave the turn off as it is and then finding the maximum sum one ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I recommend you to read the editorial again but this is simply what happens:

        • The first fact we can change any value in some subarray $$$[L,R]$$$ to be $$$R-L+1$$$ (the size of that subarray), as we can set all its values to 0 and start building our new subarray

        • Based on that fact, We check all the possible combinations, consecutive ones in our mask means try change all the values in that subarray to its length, otherwise leave it as it's.

        • Now take the greatest sum and keep that state.

        • At the end iterate again over the $$$mask$$$ where results in the greatest sum, change all consecutive ones subarray to their lengths.

        • This is done simply like building tower-of-hanoi problem, to create $$$MEX$$$ of value $$$n$$$, we must build first value $$$n-1$$$ and so on. (try solving tower of Hanoi to get the idea).

        • The editorial here just apply the operation, if we had to make operation $$$[L,R]$$$, oper change this subarray to its length by simple $$$MEX$$$ algorithm

        I hope this helps, if something isn't clear, please let me know

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          just to make it clear, the solve(k) of the editorial is just for how to create the sequence of operations right? if the problem only asked for the optimal problem, we could just find it through all 2^n possibilities without having to use solve(k) ?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Yes, exactly.

            You could even find the optimal solution in $$$O(N^3)$$$ or even better in $$$O(N^2)$$$ using $$$DP$$$.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

problems links are incorrect for example https://codeforc.es/contest/1956/problem/E2, dot between codeforc, es

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Otomachi_Una (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

IN problem D, I used online compiler ideone in default setting and previosly present code on Geek for geeks for sliding window technique. That's why issue of similiarity arised. I insist of understanding and taking in account this fact. I will take care of this issue now onwards[problem:D][submission:256537093]

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Curious how'd one write a checker for D ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why should it be difficult?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If it is easy then I donno what data structure to maintain that computes range mex, and also does range assignments. may be I could find a way to compute range mex from segment tree or something but definitely not sure about range assignments

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone explain me one thing, that my 257525583 solution for the C problem does seem to work but the testcase output doesn't even match, I was so confused by this problem for 2 days trying to match the testcase output then I realized it works without it.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In F's tutorial,

There are $$$2n$$$ vertices in the graph. Vertice $$$i$$$ links to vertices $$$([n+i-r_i,n+i-l_\color{blue}{1}\color{black}]\cup[n+i+l_i,n+i+r_i])\cap[n+1,2n]\cap Z$$$.

Shouldn't it be $$$l_\color{red}i$$$ or I missunderstand it?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's the provided perspective on problem B for this round: https://mirror.codeforces.com/contest/1956/problem/B "My initial approach:

For a type of number card with 2 copies, securing one such card guarantees one point. For a type with only 1 copy, if my count of cards (the number of types with 2 copies) exceeds the opponent's, then my score is: the number of pairs of identical number cards + the remaining single number cards on the field. Otherwise (if the count of cards <= opponent's), because I play first, I must start by placing pairs of identical cards; otherwise, I place single cards. In this scenario, I can only score based on pairs of identical cards.

Correct solution:

Mentioning that I play first and that both sides prioritize placing pairs of identical numbers. Ultimately, only the score for having pairs of identical cards needs to be output since my count of cards (number of types with 2 copies) always remains <= opponent's. The cards each side possesses are initialized as the letters ABCDE, ABCDE ABCDE indicating that we can only perform exchanges between cards of the same letter on the upper and lower rows. Whenever one side completes a pair of identical letters, the other side also completes it simultaneously. This means that both sides have the same number of pairs of identical letter cards and single letter cards. Combining this observation with my initial conclusion, in cases where the counts are equal for pairs of cards, since I play first, it's disadvantageous for me, so I can only maintain the count of cards with pairs of 2."

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

it can be proven in E that if we brute through the array logn rounds, there must be at least a zero in it. that's my intuition when i first saw the problem. it's not crucial to solving the problem but i think it is fun.