KAN's blog

Editorial of Codeforces Round 687 (Technocup 2021 — Elimitation Round 2)
By KAN, 4 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +182
  • Vote: I do not like it

Comments Comments (53)
| Write comment?
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Good!

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

For problem Div2 E, 99886275 is just so cool.

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

Thank You.

Nice Problemset — problems were to the point and good.

I really liked it.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I used dictionary tree to passed the div2 D, I can guarantee its correctness, but I can't guarantee its time complexity,can anyone hack my solutions? https://codeforces.me/contest/1457/submission/99900717

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div2D, why is n<=60 if the given condition is true?

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

    Because if n>60 , We can always find a contiguous triplet (a,b,c) such that a > b^c.

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

      Why we can always find that?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +9 Vote: I do not like it

        In case $$$n > 60$$$ There will be three numbers $$$(a, b, c)$$$ all having the same msb (Most Significant Bit) set to 1. You can do one operation with numbers $$$b, c$$$ this will turn off the msb therefore $$$ a > (b \oplus c)$$$.

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

        Because a_i <= 10^9 ~ 2^30. So of numbers which are k digits long in binary, we can have at most 2 to not get a triplet. And there are only 30 different sizes before we hit the cap of 10^9.

        edit: I may have answered the wrong question

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

        Because these three numbers share the same highest bit $$$1$$$. And $$$1 \oplus 1=0$$$. Let's consider these three numbers as $$$a,b,c$$$ where $$$a<b<c$$$ , then the highest bit will become $$$0$$$ after we do $$$b \oplus c$$$, so $$$a > b \oplus c$$$ holds. Then we can always find that.

        → Reply
»
4 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Me when doing normal rounds: So I will try to do problems in order, if I can't do A in 30 minutes then I will consider B...

Me when doing russian rounds:

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem B, n is <=10^5, test cases are <=10^4 and no. of colours are <=100. How is 10^11 (that's what I can interpret) solution works??

If some one has any explanation and would like to correct where I am wrong, it will be great :)

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

    It is guaranteed that the sum of n over all test cases does not exceed 10^5.

    So when value of n is 10^5 then no. of test cases will definitely be 1. When test cases are 10^4, then value of n in all test cases are such that their sum will be atmost 10^5.

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

    There is a statement, "Sum of $$$n$$$ over all test cases doesn't exeeds $$$10^5$$$". That basically means $$$t*n<=10^5$$$. So, overall operations doesn't exeed $$$100*10^5=10^7$$$ which is acceptable in the given time limit.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not see that B had only 100 colors :/

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am still confused in Div 2D.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

plzz anyone can explain div2 D. why n<=60

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

    For n <= 1e9, There can be atmost two numbers having same most significant bit. Therefore the bound will be atmost twice the number of bits i.e. 2 * log2(1e9) which is 60.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for detailed explanation of Div2E!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div 2 Problem A, this is my code

Code

I have calculated the Manhattan Distance of the cell (r, c) from each of the corner cells, and printed the max distance. My code is giving wrong answer on test 2. Can anyone tell what's wrong in my code?

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

    abs(a — b) + abs(c — d) is not equal to abs((a+c) — (b+d)).They both are different.

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

    find abs of (row) and col seperate for all four corner

    int ans=Math.max(row-1+col-1, Math.abs(n-row)+Math.abs(m-col));

           ans=Math.max(ans, row-1+Math.abs(m-col));
       ans=Math.max(ans, col-1+Math.abs(n-row));
    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

for D, I brute forced subarrays of size <= 31, then brute forced again on the "split point". for example, if i have a subarray i...j and a split point of k, we xor the range from i...k and k+1..j. then, we check if the sequence we made decreases at any point. why does this work? I used the claim that there does not exist a construction where we have to make > 29 moves.

https://codeforces.me/contest/1457/submission/99871104

→ Reply
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Nobody found the $$$O(N)$$$ for div1D?

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

    how to solve div1D in $$$O(N)$$$ ?

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

      For each situation where you just took the $$$i$$$-th thing, find the set of positions of the clone. For each situation where the clone just took the $$$i$$$-th thing, find the set of your positions. In the first case, it's a contiguous range, which means it has to be up to 2 contiguous ranges in the second case. There's a lot of possible transitions from $$$i$$$ to $$$i+1$$$ but it's a constant number and each takes constant time.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain the prefix suffix method used in division 2 in D-problem?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it only me or Div1 E editorial is cryptic.

"Let call low bits that we don't need to care free bits." — can you maybe give an example.

What is A there?

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

    For example, assume you have segment $$$(10, 20)$$$ and you set your number $$$011??$$$, your number will be in the segment whatever you set two lowest bits, then they are free.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in div2C,why the answer of 2 2 1 10 11 1 is 11,if i make the 0 to 1,it just take 1 second

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

    This is your test case:

    n = 2, p = 2, k = 1; s = "10"; x = 11, y = 1.

    x is the cost of adding a platform, y is the cost of removing the first cell. In your case, there is only 1 option: that is to add a platform at position 2, giving 11 as your answer.

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

KAN For div2 D, the editorial states the following:

Indeed, there are no two integers with the same highest bit set. It is much easier to solve the problem in such constraints.

I think it should be stated as: there are at most two integers with the same highest bit set. Right? Because for input [1, 6, 7], the highest set bit of all numbers are different but 6 and 7 have the same highest set bit.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is the space complexity for div2B O(N) ?

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

    You are essentially keeping a separate index list for each possible color. The total houses is N, so the total entries in all index lists sum up to N.

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

It is good tutorial.

Kindly do mention the code also. Sometime explanation is not sufficient

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain the dp approach to div2 C?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    https://codeforces.me/blog/entry/85081#comment-727466

    Spoiler
    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It seems that the standard program to the Div.1 D has something wrong
https://codeforces.ml/contest/1456/hacks

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

    Fixed, some testers' solution got hacked too.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What would be the difficulty level of XOR gun?

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Sorry for my stupid, it's a little hard for me to understand Div1E solution, can someone explain it easily? thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1415B - Repainting Street

Can somebody explain why test case 3 in test 2 (below) says right answer is 2 days? If we choose any color (e.g. 1), there are only 6 houses, which are not this color. So, with capacity k=6 one day should be enough to paint. Looks I am missing something, but don't get what.

9 6
1 2 3 1 2 3 1 2 3
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$K$$$ means a range that must be consecutive.

    So in the test,you can choose [1,6] or [2,7] or [3,8] or [4,9] to change the color.

    → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hey guys, here is my video proof for "Genius Greedy" in Problem E using induction hypothesis. Anyone who is interested can take a look

→ Reply