Imakf's blog

Codeforces Round 906 Editorial
By Imakf, history, 13 months ago, In English

1890A - Doremy's Paint 3

idea: Cocoly1990

Solution
Code

1890B - Qingshan Loves Strings

idea: Imakf

Solution
Code

1889A - Qingshan Loves Strings 2

idea: Imakf

Solution
Code

1889B - Doremy's Connecting Plan

idea: Cocoly1990

Solution
Code

1889C2 - Doremy's Drying Plan (Hard Version)

idea: waaitg, Imakf

Easy Solution
Hard Solution
Code

1889D - Game of Stacks

idea: waaitg

Solution
Code

1889E - Doremy's Swapping Trees

idea: waaitg

Solution
Code

1889F - Doremy's Average Tree

idea: waaitg, Imakf

Solution
Code
  • Vote: I like it
  • +174
  • Vote: I do not like it

Comments Comments (69)
| Write comment?
»
13 months ago, # |
  Vote: I like it -15 Vote: I do not like it

i love solving observation problems like c , i just tried some cases and came up with the soluion .

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    but i tried many cases without caming up a solution:\

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      deque is a good tool

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I remember doing it without deque, but it was a mess to implement, used a set to keep track of occurrences of 0s and 1s.
        Got 4 WAs on the way (During the contest!) :(
        Submission for reference — 230261688

        → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very fast editorial!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

Thanks for the super fast editorial and great round ! As usual, here is my advice about the problems I solved :)

A
B
C
D
E1

Thank you for the round, looking forward to take part in another one

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I felt C was difficult to implement, maybe I suck at implementation and have more admiration for mathematical problems.
    Back to specialist now :/

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But for the Problem A what if the input is 6 2 3 5 4 4. Then the idea that is given in the editorial is wrong.

    → Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

good contest — good problems, except b was kinda troll (i found it funny though)

→ Reply
»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Div. 1 B and C1 are great! (Maybe also C2 but I didn't solve it) I like the way to optimize the algorithm.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think in C2 segments where dp transition works the same way can only be merged together or a new one may be created at the end. So to support maximums on segments we don't need any data structure, we just need to store these segments and merge them sometimes (there are at most $$$10$$$ segments, so we can do it by just storing an array of these segments and deleting elements from it).

→ Reply
»
13 months ago, # |
  Vote: I like it +44 Vote: I do not like it

My mind went blank and did not notice the $$$i=1$$$ thing in B so I accidentally solved a more complicated version of the problem where indices of vertices may be arbitrary numbers. I think it is a good exercise if you wish to think about it.

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Is it something like only edges from $$$(1,2),(1,3),....,(1,n)$$$ and $$$(2,3),(3,4),...,(n-1,n)$$$ edges matter?
    I solved using this approach, kept on deleting the edge having the least value of $$$c*i*j - a[i] - a[j]$$$, and updating the edge values.
    Or it's even more complicated?

    Proof of the approach
    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I think your approach won't work for the generalized version. In your proof, the condition $$$a_j - a_i > c\cdot (j-i)\cdot k$$$ is just necessary but not sufficient. For example, if we have $$$(5, 1), (6, 25), (7, 1), (8, 25)$$$, you'll find that we can only connect 6 and 8 in the first step.

      → Reply
»
13 months ago, # |
  Vote: I like it +16 Vote: I do not like it

the problems are so smart that I feel like I'm idiot D: anyway, that is a good round, thanks!

→ Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In Div2C/Div1A, I didn't understand why would it take at most 300 operations. I'd be grateful if someone can explain.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most 300 operations.

    Because the problem tells you

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Technically that doesn't tell you that this particular algorithm produces a solution with at most 300 insertions (or that it terminates at all).

      I know it's common to meta-game problems like this (I do it myself too) along the lines of: “Hmm, this problem is div1-A, so it can't be too difficult. There must be a solution that is not too hard. I've come up with an approach that gives the right answer for the samples and a few other cases I can think of, so it's probably the correct algorithm, so I'll just submit it and hope the pretests warn me if it's wrong.”

      This often works, but it's not the same as proving that it works.

      → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You perform at most one insertion per character originally in the string

    → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    The clue is in this sentence: “This operation is actually equivalent to moving the last 1 to the front or moving the first 0 to the end.”

    The algorithm can be summed up as:

    1. 0s1 → s
    2. 1s0 → s
    3. 0s0 → 0s001 (append "01") → s00 (apply rule 1)
    4. 1s1 → 011s1 (prepend "01") → 11s (apply rule 1)

    The problem is that the third and fourth rule, even after expanding them as I did above, do not reduce the problem size. This raises the question if the algorithm terminates at all, and if so, how many insertions there can be.

    The key is to observe that the rule 3 effectively does a left rotation (0s0 → s00) and rule 4 a right rotation (1s1 → 11s). Since s contains an equal number of 0s and 1s, you can do at most $$$|s|/2-1$$$ rotations before the first and last character are different (example: $$$s=000001111110$$$ takes 5 turns), and you can reduce the problem size with rule 1 or 2. This shows that the algorithm does terminate, and you can already infer a quadratic upper bound on the number of insertions.

    But this can be improved to $$$\mathcal{O}(N)$$$ as follows. When you've applied rule 3 $$$n$$$ times in a row, then you know that $$$s$$$ ends with at least $$$n$$$ 0s, and you cannot apply rule 4 until all those zeros have been removed, which can only happen by applying rule 1. This shows that every application of rule 3 and 4 must be paired with an eventual application of rule 1.

    That's how we know we need at most $$$|s|/2-1 = 49$$$ insertions in total.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Woowww! You and your explanation are amazing. Thanks a lot. I'd been having headache over this since the contest.

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C1 (easy) unlucky for python, same solution accepted in C++ (even a slower version). Yes there were people who solved it, but only 3.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Div2 E1/ Div1 C1 if we take test case
5 3 2
1 4
2 5
2 4
According to editorial [1 4] and [2 5] should not be considered as they intersect and there is no position i which is covered by exactly these two intervals, but the answer is obtained by taking these two segments. Can someone correct me if I am wrong?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    In the "no intersection" case we aren't considering only pairs which don't intersect, but any pairs of segments. Since we don't know if they intersect, we assume they don't and calculate the answer based on that. If those segments did in fact intersect in a way that made the answer larger, it would get counted in the second case anyway.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how in problem Div. 1 D the idea for the easy version is extended to the original problem?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2E1 editorial, I still haven't figure out how to handle the case when two interval intersect using array or set. Could someone explain for me this case, or it could be nice to see the actual implementation

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You check check my implementation. https://codeforces.net/contest/1890/submission/230287888 It currently runs in O(3*n). But with casework on mx1,mx2 and using the fact from editorial that there are at most n useful intersection. You bring it to O(n)

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain this part:


              int mx1 = -1, mx2 = -1;
        rep(j,i,to){
            if(sz(rain[j]) == 0) continue;
            if(j != i){
                if(mx2 == -1 || rain[mx2].back() <= rain[j].back()){
                    mx2 = j;
                    if(mx1 == -1 || rain[mx1].back() <= rain[mx2].back()) swap(mx1,mx2); 
                }
            }
            int ct = rain[j].back();
            int c2 = pre[min(ct,to)][2]-pre[j-1][2];
            c2 += pre[max(ct,to)][1]-pre[i-1][1];
            two = max(two, c2);
        }
      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This part is searching through all intersection of rain starting from i. In the second part of code, I am calculating the answer as number of 2s on intersection part + number of 1 in entire covered part. In the first part I am trying to find the next rain index to search. Among all rain with rightEnd >= to, You only care about the largest two ending points, because all other will always have > 2 intersection. I have stored it as mx1 and mx2. You can ignore the search on mx1 and mx2 if its right end is before "to". In my implementation, I am not ignoring

        → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain Div2 E1 solution with the code. I couldn’t understand the editorial.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any advice on How to solve problem D using UnionFind and counting the population with DFS?

My submission: 230232830

I know that it can be solved using PQ, but I have the doubt if it is possible to solve it with this approach

→ Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

why does s_i + s_j >= i + j — 1 imply that either s_i >= i and s_j >= j have to be true, why cant s_i >= j and s_j >= i ?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You say $$$s_i \geq j$$$ and $$$s_j \geq i$$$.

    If $$$i \leq j$$$, then $$$s_i \geq i$$$.

    If $$$i \geq j$$$, then $$$s_j \geq j$$$.

    So either $$$s_i \geq i$$$ or $$$s_j \geq j$$$ is true.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me where my code is failing for Div 2 C problem? Submission id 230209550

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a wonderful contest Problems were mainly based on observations and less on standard techniques. Thank you for such contest.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1889A — Qingshan Loves Strings 2 In this question we are allowed to insert only "01" then why it the tutorial suggesting to insert "10".

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can smb explain what this mean in D from div2 906? iota (p + 1, p + n + 1, 1); I read the solution and it wasn't mention there, so I'm a little bit confused

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem c1(easy) i cant understand this word "In the "no intersection" case, we can just simply pick two best intervals."
i don't think it can solve simply:(

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem D we say that I always connect with the 1st city to minimize the multiplication i * j * c , but how can i be certain that this always right since taking other two cities may have a bigger Sum(ak)?

can anyone please explain this!!

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Let's consider a pair of singleton vertices $$$i$$$ and $$$j$$$. The claim is that if we can connect $$$i$$$ and $$$j$$$, then we can connect either $$$i$$$ or $$$j$$$ to $$$1$$$. If $$$i=1$$$ or $$$j=1$$$ that's trivially true. Otherwise, we know $$$i, j ≥ 2$$$ and we can assume without loss of generality that $$$a_i ≤ a_j$$$ (otherwise just swap $$$i$$$ and $$$j$$$).

    We want to prove $$$a_i + a_j ≥ ijc$$$ implies $$$a_1 + a_j ≥ 1jc$$$ or simpler $$$a_j ≥ jc$$$ (since worst case, $$$a_1 = 0$$$).

    steps of proof

    The same logic also works for sums of connected components, but we don't even need it, because the above shows that it's enough to connect singleton vertices to vertex 1.

    → Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't see how to "see" the solution for Div2C... Can someone explain the intuition?

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So sorry, I meant Div2C

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        For C you can observe the fact that the condition described in the problem is opposite of what the condition for palindrome is i.e for each i : [0, s.size()/2], s[i] == s[s.size()-i-1]. Keeping this in mind the condition for problem becomes for...., s[i] != s[s.size()-i-1]. Now consider a case when length of the string is ODD. In this case you can observe that no matter what you do the character at the position (s.size())/2 will always be equal to itself hence you have to give up i.e for odd string or for strings that only have unique character that answer can never be formed.

        Now when the answer can be formed, Notice two things:

        1. when s[i] == s[n-i-1], s[i] == '0', in this case the only thing you can do is add "01" at the n-i-1 position making -> s[i] = '0' s[new] = '1'.

        2. when s[i] == s[n-i-1], s[i] == '1', in this case you have to add "01" before the ith position making s[new] = '0' and s[n-i-1] = '1'.

        Keep doing the above for 301 iterations, if in the end the result array has a size > 300, that means answer was never possible otherwise it print the answer.

        Spoiler

        → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D of div-2 does the given constant actually have any impact ? Like whats the significance of c?

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With $$$c = 1$$$ the tests would be weak.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why does this not work, if we sort the array based on c = 1 from which we are getting the order and then check if we can build the tree using that order? here is my submission for the same.

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It works, but giving $$$c = 1$$$ in the statement would mean that it's harder to kill wrong solutions.

        → Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it +54 Vote: I do not like it

For div1 F, we can solve it faster in $$$O(n\log{n})$$$. To get a prefix of an array $$$a_1, a_2, a_3, \ldots a_t$$$, where $$$a_i$$$ is the value on node $$$i$$$, we should consider all valid nodes, and find if there exists a covering with $$$\le k$$$ nodes. A node covers all nodes in it's subtree.

Then to do this fast, we consider an auxillary graph. We should only consider the nodes, such that they're on the path $$$[a, r]$$$ for $$$1 \le a \le t$$$. We can see, that since $$$a$$$ is forced, all the valid nodes on the path from $$$a$$$ to $$$r$$$ must have the same value. So this leads us into splitting the path of $$$[t+1, n]$$$ into 2 parts. The one already in auxillary tree, and the one that isn't. For the part that isn't, we can simply find it and work with it directly, since it is amortised $$$O(n)$$$. We can easily find the closest ancestor valid node in the auxillary tree too.

Now we consider 3 cases, either no operation, an operation with the value of the path in the auxillary tree, or an operation with a value of the added path.

For no operation, we should invalidate as usual, and mark this path as unneeded, i.e. it doesn't need to be covered, but it can be.

For an operation with the value of the added path, we need to remove all the nodes in path to the current node. We can notice that this is a simple function of the degrees of the needed nodes of ancestor, as we split each old cover into the children covers. Additionally, if we have to delete them, we can do so directly as it again amortises to $$$O(n)$$$.

For an operation with the value of the auxllary tree, we can simply connect it to the auxillary tree. If the auxillary tree currently doesn't need a covering, we need a covering now, so we can make the values force need it. Again, doing this explicitly amortises to $$$O(n)$$$.

Most of the difficulty is maintaining the moving parts, but here is a full implementation 230451211 (My implementation is 400 lines :p)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody explain Div1C2/Div2E2 in more detail, after we understood dp in O(n^2k)?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow. Just learned from div1c one can simply use a sparse table instead of a segment tree to handle this kind of dp. Really nice!

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how the sparse tree with updates works? I am confused on this array example:

    3, 1, 4, 1, 5, 9, 2, 6

    The sparse tree looks like

    3, 1, 4, 1, 5, 9, 2, 6
3, 4, 4, 5, 9, 9, 6
4, 5, 9, 9, 9
9

    After updating the index 3 to 10 based on the solution's implementation the sparse tree becomes

    3, 1, 4, 10, 5, 9, 2, 6
3, 4, 10, 5, 9, 9, 6
10, 5, 9, 9, 9
9

    Querying the max of (1,7) will return max(st[1,2],st[4,2])=max(4,9)=9, the answer should be 10. It seems to me that you need to update all ranges in the sparse tree that include index 3, making the sparse tree look like this

    3, 1, 4, 10, 5, 9, 2, 6
3, 4, 10, 10, 9, 9, 6
10, 10, 10, 10, 9
10

    However, this is O(n) (maybe even O(nlogn)) causing TLE, and not how it is implemented in the solution.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Never mind, I figured it out. The change function is only used in the construction of the sparse tree, so changes in the middle of the sparse tree will never happen.

      → Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In Problem 1889B Deremy's connecting path, My code is failing for test case 4th and in that, 81st test is failing. i couldn't seem to resolve the problem because I cannot see that 81st test of the test case 4th. I don't think there is a overflow problem because I am using double and my algorithm seems to be correct. i think there is some corner case missing. 1. My algorithm: I will divide the array a by c( to reduce c=1) I will first find the maximum index (1<=i<= n) such that one can make edge (1,i). i will take the sum from 1st to ith index. then i will iterate from i+1 to n, and as soon as I find an index j such that edge (1,j) can be formed with (sum+a[j]) >= 1.j then I will update the sum till jth starting from 1st. Could anyone please help?

Just for reference: My Submission https://codeforces.net/contest/1890/submission/232326341

→ Reply
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem E in div1 is great, but the limitations are incredibly strict for completely no reason...

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem C1(easy version), can someone elaborate on the proof of the statement "In the "intersection" case, there are at most n useful interval".

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1 Problem C2 could be solved without sparse tables. Instead we observe that when you query an interval, it is the same as getting the minimum dp value from the leftmost element in the interval up until the current position i. These minimums could be store using Arpa trick. Here is a link: https://codeforces.net/blog/entry/48994

→ Reply
»
12 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I was solving Div1 B Doremy's connecting plan but i was getting wrong answer in testcase 3 token 576 can you please provide me this perticular token's data.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1889/submission/239421653 can anybody stress test it pls

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What if the input given is 4 4 5 3 1 7 6 2. Then this solution will be not correct for the problem A how we are going to get the solution for this question?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another and an elegant approach to solve E1 . we can first find the points which are covered by either 1 or 2 intervals and also the index of the interval which covers them . Now our problem boils down to finding the largest subarray with 2 unique values.

→ Reply