awoo's blog

Educational Codeforces Round 161 Editorial
By awoo, history, 11 months ago, translation, In English

1922A - Tricky Template

Idea: Roms

Tutorial
Solution (awoo)

1922B - Forming Triangles

Idea: Roms

Tutorial
Solution (Roms)

1922C - Closest Cities

Idea: BledDest

Tutorial
Solution (Roms)

1922D - Berserk Monsters

Idea: BledDest

Tutorial
Solution (Neon)

1922E - Increasing Subsequences

Idea: Roms

Tutorial
Solution (Neon)

1922F - Replace on Segment

Idea: Roms

Tutorial
Solution (Neon)
  • Vote: I like it
  • +116
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +43 Vote: I do not like it

If using a double linked list to implement 1922D, we can get a solution of O(n) time.

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

    I created array for storing right & left alive monster

    // intialization
int right[n+2] , left[n+2] ;
for(int i=1 ; i<=n ; i++)
{
    right[i] = i+1 ;
    left[i] = i-1 ;
}

// after each round
for(int it : died_in_round)
{
    left[right[it]] = left[it] ;
    right[left[it]] = right[it] ;
}
    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wrote a similar solution but using sets was so elegant!

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

    Bro I messed up and used both set and double linked list. Can you tag your solution for me to view. I just wrote a bunch of code and somehow got AC.

    → Reply
»
11 months ago, # |
← Rev. 5   Vote: I like it -15 Vote: I do not like it

We can do 1922B - Forming Triangles without binomial coefficient. 242267553 We can assume that the three sides chosen by us are (2^x,2^(x+d1),2^(x+d1+d2)) d1, d2 ≥ 0. Our triangle must meet these conditions 2^x + 2^(x+d1) > 2^(x+d1+d2). In the other way, sum of two minimum must be greater than maximum one.

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

    nice

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

    Can you explain more about your code? I was unable to understand it.

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

      that is almost same idea with the idea in editorial but it's like dp observation form of it

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

In problem E we could also construct an increasing sequence 1, 2, 3, ..., N. We could easily see that it has S = 2^N increasing subsequences (including the empty one).

If S*2 equals X, we just need to add N+1 at the end, else we need to add some values to get X-S more increasing subsequences.

Notice that if we add a value 1 <= v <= N to the end of the sequence, we would get 2^(v-1) more increasing subsequences, so we just need to check each bit from MSB to LSB.

Submission: 242459743

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

    Thanks!!!.

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

    I used this method in the contest

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

    This was very helpful. Thank you

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

    I thought of the same approach. But, I am getting first test case wrong on system test 6.

    For 905093722480139348, your code returns:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3

    The largest number is 59, so according to your logic it should be 2^59. The remaining numbers: 59 56 52 51 50 49 48 44 41 40 39 38 37 33 32 31 30 29 28 24 23 21 20 19 17 15 13 12 11 7 5 3

    Should be 2^(v-1), which when I calculate turns out to sum with 2^59 as 905093722480139264. What am I doing wrong?

    This is the code I used to test:

        ll ar[] = {59,56,52 ,51,50,49,48,44,41,40,39,38,37,33,32,31,30,29,28,24,23,21,20,19,17,15,13,12,11,7,5,3};
    ll sm = pow(2LL, 59);
    for (int i = 0; i < 32; ++i) {
        sm += pow(2LL, ar[i]-1);
    }

    cout << sm;

    My submission num (Java): 242767859

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

      Change the line sm += pow(2LL, ar[i]-1); to sm += (ll)pow(2LL, ar[i]-1); and it should produce the correct result. In C++ the pow function return double typed value, adding double in that range may give some miscalculation, I don't know much about Java but it could also be the same issue.

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

For problem B, I got accepted in the contest, but then I woke up this morning and got Time Limit Exceeded on Test case 6? I'm so confused why did this happen. I was supposed to hit expert.

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

    That's because someone made this test case to hack some code and succeeded during the hack phase, and these successful hacks were added to the system tests, which were used to judge the final results.

    Such rules are described in this blog: https://codeforces.net/blog/entry/21496

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

      oh ok, my same solution translated to java (as opposed to my original python) somehow gets accepted. i'm very confused

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

        In general,C++ is faster than java,and java is faster than Python.It has to do with the feature of each languages.

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

        hell it s*cks man same happened to me! I think its about time that codeforces set different time limits for python and c++ for questions otherwise it seems like there's no point in having multiple languages

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

          oh yea sorry to hear! I ended up passing in python after the contest by simply not using a dictionary and instead using an array. i think it is because dictionary is only O(1) access on average so i guess that adversarial test case made all the values in the array hash to the same slot or smth. that's evil haha

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

Problem F can also be solved in $$$O((n^3 \cdot x)/64))$$$ using bitsets: link

Note that since $$$x$$$ is at most $$$100$$$, we can simply use 128 bit integers instead of bitsets for an even better constant factor.

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

I'm very confused by the editorial for E, so I feel like sharing my own (AC) approach:

First, observe that a strictly increasing array with $$$k$$$ elements will have $$$2^k$$$ increasing subsequences (including the empty subsequence), the elements to be removed can be any subset of all the elements. So for input $$$n$$$, we can find the largest power of 2 which is $$$\leq n$$$, e.g., for integer $$$p$$$ such that $$$2^p \leq n < 2^{p + 1}$$$, we can form an increasing array of $$$p$$$ elements to create $$$2^p$$$ subsequences (including the empty subsequence).

But what about the remaining $$$n - 2^p$$$ subsequences? Let's say the largest power of 2 you can fit in the remaining value is $$$2^q$$$, i.e., $$$2^q \leq n - 2^p < 2^{q + 1}$$$. Initially, I considered creating a separate subarray of $$$q$$$ elements, but having to do this with every power in the worst-case (e.g., if $$$n = 2^{59} - 1$$$) would exceed the 200-length limit (and we also have to avoid double-counting the empty subsequences).

Instead, however, we can generate $$$2^q$$$ new increasing subsequences by adding only one element to the end of the array: an element which is greater than the first $$$q$$$ elements of the original sequence (of $$$p$$$ elements) but smaller than the rest. The new subsequences generated involve the new element with any subset of the first $$$q$$$ elements, resulting in $$$2^q$$$ new subsequences (there are no empty subsequences here, since the new element is always included in these new subsequences).

This leads to the following algorithm: for the highest power $$$p$$$ of 2 that fits (i.e., leftmost 1 bit), prepare $$$p$$$ elements in strictly increasing order. This is the primary reference sequence. Then for the next power $$$q$$$ of 2 that fits, e.g., we simply add one extra element to the end whose value is between the $$$q$$$-th and the $$$(q + 1)$$$-th element of the primary reference sequence. Repeat for each power of $$$q$$$ that fits from the remnants of the previous step.

My submission: 242314370. The variable prm denotes $$$p$$$, the length of the primary sequence. I used multiples of 1000 for the primary sequence. Some of the code details overcomplicated this by considering when we might have multiple instances of the same $$$q$$$ value, but this is unnecessary with clear-headed hindsight, since we're basically just going through all the 1-bits in the binary representation from left to right. The __builtin_clz(n) function (count leading 0s) would likely have improved this, to quickly find the leftmost 1-bit each time.

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

    I was able to come up with something similar, but I thought there would be cases where overlaps would occur and didn't manage to come up with any way to resolve them. Your explanation provides oversight in my eyesight.

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

    Thanks I am stuck with the part of compressing the length of array. I might be able to do it now.

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

My submission to E 242474581. I got long long overflow when I had (1ll<<i) for calculating power of 2s (Specifically at i=59). However, it did not overflow when I calculated poweroftwos by arithmetic (as in submission, the dp array).

Any suggestions why there was an overflow for (1<<i) case? 242470568

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

    use (1LL<<i)

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

      Yep, I've used 1ll in my wrong submission

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

        Maybe your program may let i bigger than $$$64$$$ then it will cause an overflow. Check the variable i to fix this.

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

          I checked it on a debugger and i=59 is where it overflowed. Also the same code where I substituted (1ll<<i) to poweroftwo(i) gave me an AC, weird behaviour

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

            Because you increase i in either cases, so it may hit a value bigger than 62, and 1ll<<63 overflows, so it return negative value and code outputs -1.

            You can do ++i if the condition is true or check if i<63 before evaluating 1ll<<i.

            Here is the Accepted code

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

We can think of Problem-B in another way, we can assume that the three sides chosen by us are $$$(2^x, 2^{x+d_1}, 2^{x+d_1 + d_2})$$$ where $$$d_1, d_2 \geq 0$$$.

As mentioned in editorial in order to make a degenerate triangle we want $$$2^x + 2^{x + d_1} > 2^{x +d_1 + d_2}$$$ (Sum of two minimum is greater than maximum).

After simplfying above inequality we get $$$2^{d_1} \cdot (2^{d_2} - 1) < 1$$$, which is only possible when $$$d_2 = 0$$$, thus for each $$$a_i$$$ we just want to find out the number of $$$a_i's$$$ after it. As for the first side length i.e., $$$2^{x}$$$ it doesn't matter what we choose so our final answer is just $$$\sum_{i = 0}^{N - 1} i \cdot \text{count of}\ a_i\ \text{in range i + 1 to n - 1}$$$. (Note 0-indexing)

Here is my submission.

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

    Same idea but as a pure DP, without precomputed numbers count: 242489424. State is number of triangles with current element $$$a_i$$$ as longest edge.

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

why this code give wrong answer forn D question 242491110

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

Can anyone please explain how tester of E could have been written so that it checks the answer in polynomial time? I can't think of one.

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

    let dp[i] be number of increasing subsequences ending at position i, then it's O(n^2) to check. If we use sorting+fenwick to find dp starting from the lowest value, then it's O(nlogn).

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

    I've written a checker for myself while solving problem E. Here's how it works: — Iterate through the sequence from left to right, and compute how many subsequences end with this index, and we store this value in a bBST — We check which numbers are less than the current one in our bBST (so to the left), and add their values up, because for each of these subsequences we can append the current number to the end — Then we store this value + 1 (because this value itself is also a valid increasing subsequence) in the bBST — Finally, we add up all elements in the bBST and add 1, because an empty one is also valid Here's my implementation: https://pastebin.com/5RFbryrk

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

    Using number of occurrences of number in every sequence and calculating all subsequences.

    • [1,2,3,4,5] -> 2*2*2*2*2 — 1 + 1

    • [1,1,2,2,2,3,4,5,5] -> 3*4*2*2*3 — 1 + 1

    Is this correct ? Never mind

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

I feel like my D should get hacked. Can someone try? submission

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

why is my code for problem D 242468805 getting a time limit exceeded signal ? shouldn't it be faster than this approach using sets?

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

    Consider the case in which only 1 monster dies every round. In that case you will iterate $$$(n + 1 - i)$$$ times in round-$$$i$$$, which makes you solution $$$O(n^2)$$$.

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

      doesn't the approach provided here using tree also have to go through all the alive monsters for each of the round .Or have i misunderstood the solution provided here?

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

        They only consider monsters who can die in next round. See the use of set ncur.

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

For F, I feel like we don't need to precompute that much to eliminate cyclic dependencies. Instead, we consider two cases:

  1. ifa[l]==k: we calculatedp1[l][r][k]fromdp1[l+1][r][k] first, then calculatedp2[l][r][kk]fromdp1[l][r][k], where k!=kk.
  2. ifa[l]!=k: we calculatedp2[l][r][k]fromdp2[l+1][r][k] first, then calculatedp1[l][r][k]fromdp2[l][r][k].
My Code
→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution to D, what does prev(it) return in case "it" is the iterator pointing to the first element in the set?

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

    It points to the last element of container (here, std::set). Another example here

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

Wow, problem E is so creative, revolutionary and original — learned a lot about bitwise operation from that one!!!!! What inspired you to create such a ground-breaking, intuitive and simply perfect problem???.?!!!!!!

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

can someone explain problem D. I don't understand why the problem setter's claim is valid.

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

    Let's assume 3 monsters i-1, i, i+1 are alive after some round R. Then monster i will be be alive even after round R+1.

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

      Thanks a lot! I misinterpreted the question. I thought d[i] behaves like health and gets decreased by a[i — 1] + a[i + 1] every round.

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

Hey, could someone explain how removeing cyclic dependencies in problem F works. Is there a general approche or can we only do this for this spezific problem. Thanks!

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

Can somebody explain why my solution is getting TLE'D on test 15 for problem D 242631259

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

In problem E, it is written that : If we add a new maximum to the end of the array, the number of increasing subsequences in the new array equals 2x (since the new element forms increasing subsequences with any other elements).

I think this is not well explained. In fact, if we have x increasing sequences, there are x-1 non-empty sequences and 1 empty sequence. When we add a new maximum, there will be x new non-empty increasing sequences (x-1 from the previous sequences and 1 sequence composed only of the new element). if we count again the empty sequence, the total will be (x-1) + x + 1 = 2x.

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

I'm getting Memory Limit Exceeded in test 5 of Problem E, why is it so?

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

can anyone help me with the claim that when only the particular element is dead the suitable candidates would be its Neighbours ? in problem D

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

BledDest The editorial solution for D problem is a little bit wrong in the case where our i in cur is equal to 0 then the nxt and prev values give us the garbage value this is working because of the summation of the garbage values is always less than INT_MAX, but if we use long long vector to store the attack and defense value than the garbage value given will also be long long which will exceed the INT_MAX value so then it will give wrong answer. sorry for my bad English.

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

It was already mentioned, sorry.

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

Why somebody solve F so quickly?

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

    because it is a standard dp on ranges problem as long as you get the dp2 idea quickly. Their method of handling cyclic dependencies is very very unnecessary.

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

      how did you handled the cyclic dependencies ?

      Also I dont think it is that that bad , this was my solution after I read the editorial : https://codeforces.net/contest/1922/submission/242787688

      As you can see the only thing I did to get rid of cyclic dependencies was adding the 2 lines of code at the beginning of the function : 

      while(l < (n-1) and l < r and ((a[l] == value) ^ typ))l++;
while(r > 0 and r > l and ((a[r] == value) ^ typ))r--;

      Nonetheless I am still curious about how you handled because your approach is clearly faster than mine , and I couldnt really understand your logic from your submission

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

I shouldn't be able to understand problem F solution, why am I? :-)

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

can enyone help me with this problem? I am tring to solve it using Hash in c++ but can't

https://codeforces.net/contest/271/submission/243292259

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

Hello everyone, I am having some trouble with problem F. I solved it with the help of the code from Dominater069.

From what I understood. He did and I copied something like:

  1. Break dp2 subproblems and calculate (OK)
  2. Break dp subproblems and calculate (OK)
  3. dp[i][j][k] can be formed by 1 extra step after dp2[i][j][k]
  4. dp2[i][j][x] can be formed by any k other than x and we need the minimum one

Now the part where the part 3 and part 4 just relies on each other I want a closure of why this is not in recursion or recurance. I tried solving it like Bellmanford where if the weights stop relaxing we stop the algorithm between step 3 and 4 and it will work but it doesn't even matter. I', interested in the doesn't matter part. Can someone prove it.

Thank you for reading my comment and special thanks if you can shed some light on it. Thanks everyone.

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

The second question was very nice problem!!

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

Surprised that the editorial lists an $$$O(n^4)$$$ for problem F, when it can be done in $$$O(n^3)$$$, also surprised that no one has mentioned it in the comments.

243829676

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

for D: why if the neighbors of $$$i$$$-th monster are alive we don't have to check the $$$i$$$-th in the next round? Isn't it possible that the neighbors to kill it in the next round? UPD: I thought the defense (d) is being decreased each round

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

Is there an issue with codeforces's compiler ? I used unordered_map and ordered map in B and got different results whereas got same results with COdechef's ide

→ Reply