Блог пользователя 0doO

Автор 0doO, история, 7 месяцев назад, По-английски

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
Разбор задач Codeforces Round 939 (Div. 2)
  • Проголосовать: нравится
  • +106
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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.)

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      True

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Very well explained. Thanks!

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I became pupil, feels good!

»
7 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I became expert, feels good!

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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).

            • »
              »
              »
              »
              »
              »
              »
              7 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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:
              • »
                »
                »
                »
                »
                »
                »
                »
                7 месяцев назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Can you please explain your greedy solution?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 месяцев назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится

                  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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 месяцев назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                <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 ??

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 месяцев назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      Unfortunately, such problems are only becoming more frequent :(

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
»
7 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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}$$$

»
7 месяцев назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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://codeforces.net/contest/1956/submission/256603484

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

Spoiler
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The link for editorial in contest announcement has a typo

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Simply simulating can be hacked using the testcase:

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why are problems put with codeforc.es?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.net/contest/1956/submission/256538264

Thanks to the authors for a wonderful round!

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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]

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for fast editorial

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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..

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Here is my submission 256685619

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C was cray cray

»
7 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      • »
        »
        »
        »
        7 месяцев назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          7 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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) ?

»
7 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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]

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Curious how'd one write a checker for D ?

  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    why should it be difficult?

    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
7 месяцев назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's the provided perspective on problem B for this round: https://codeforces.net/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."

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Input 2 1 2 Output 1 1 1 1 1 1 7 3 1 1 1 2 1 2 1 2 2 1 1 2 Checker Log wrong answer Integer parameter [name=m] equals to 7, violates the range [0, 4] (test case 2) what this is giving me the error?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C is so annoying.. :( However problem D is cool.