vovuh's blog

Codeforces Round #587 (Div. 3) Editorial
By vovuh, history, 5 years ago, In English

All problems except the problem F are invented by fcspartakm. The problem F idea belongs to BledDest.

1216A - Prefixes

Tutorial
Solution

1216B - Shooting

Tutorial
Solution

1216C - White Sheet

Tutorial
Solution 1
Solution 2

1216D - Swords

Tutorial
Solution

1216E1 - Numerical Sequence (easy version)

Tutorial
Solution

1216E2 - Numerical Sequence (hard version)

Tutorial
Solution

1216F - Wi-Fi

Tutorial
Solution
  • Vote: I like it
  • +74
  • Vote: I do not like it

Comments Comments (51)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, everything is amazing. But if this is an editorial, why can't you paste clean code?

I mean without shitty part: unnecessary code, too many defines, etc... __ __ __ Thanks for being patient.

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

    Agree with you, I struggle understanding the code with these many defines alot, I prefer writing everything inside the main and without all these defines, It makes the code unreadable for me at least

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

      You can look at the situation from the other side. Some of the solutions that you see in the editorial were written by testers. In this editorial one of such solutions with "all these defines" was written by me, but when I solved these problems, I could not even imagine that my solutions would be published in the editorial, so I did it in the way that was usual and convenient for me. Sorry for this. Perhaps next time I will try to write more understandable and beautiful solutions. And, as you can see, vovuh's solutions (for example, problem F) do not contain unnecessary code and look quite understandable

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

        @nooinenoojno Definitely not your fault, there should be seperate editorialists for contests instead of using Tester's solution the editorialist should write the code !

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

          Editorial authors do not always have enough time to write their own solutions for editorials, they already spend a lot of time thinking up problems, preparing statements, checkers, tests, answering questions and writing explanations for editorial. It is especially difficult when, in addition to preparing a contest, you have to study and work

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

            Maybe having bigger teams for contests could help... All this work should be done by multiple people.

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

The tutorial of problem E1 is poorly written. Please review it.

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

For problem D, can someone give a proper proof for why the solution is optimal?

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

    The initial number of Swords is the same. Obviously, the maximum of the stolen swords is the optimal number of swords. If the minimum number of Swords is guaranteed, then the maximum number of swords taken by each person is the largest. That is to find the maximum common factor of the difference between the ai and the maximum except the maximum value.

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

    Let the largest leftover pile be $$$max$$$, and smallest be $$$min$$$. We consider three cases —

    1. The thieves leave at least one pile untouched, and $$$max > min$$$. In this case, $$$x = max$$$, and the number stolen from each pile is $$$x - a_i = max - a_i$$$. To minimize the number of thieves, we want that each one steals as much as possible, and since they all steal the same number of swords, $$$z$$$ must divide all $$$x - a_i$$$ and be as large as possible — meaning $$$z = gcd\ (max - a_1, max - a_2, \dots, max-a_n) = g$$$, and $$$y = \sum_i {\dfrac{max - a_i}{g}}$$$.

    2. The thieves steal from all piles, and $$$max > min$$$. Let the amount stolen from the largest pile $$$max$$$ be $$$q$$$, i.e. $$$x = max + q$$$; and the new gcd of the $$$x-a_i$$$ is $$$g'$$$. If $$$g'$$$ divides $$$q$$$, then we can take away $$$q$$$ from all $$$x - a_i$$$ and the resultant gcd will be $$$g$$$, a multiple of $$$g'$$$. $$$g' = {gcd}_i (x - a_i) \mid {gcd}_i (x - q - a_i) = {gcd}_i\ (max - a_i) = g$$$. By doing this operation, we revert to case 1 and not only get a possibly bigger gcd but also a smaller $$$\sum_i {x - a_i}$$$, which means smaller new $$$y = \frac{1}{g}\sum_i {max - a_i} < \frac{1}{g'}\sum_i {max + q - a_i}$$$. So this case can be omitted from consideration. The only remaining case is when $$$g'$$$ does not divide $$$q$$$, but this is impossible as $$$g'$$$ divides all $$$x - a_i$$$, so it must divide $$$x - max = q$$$.

    3. There is one case when $$$max = min$$$. For case 1, $$$y = 0$$$ and $$$z$$$ is undefined. But for case 2, for any $$$q > 0$$$, $$$z = q > 0$$$ and $$$y = n > 0$$$, so case 1 is still better than case 2.

    So in any case, best case scenario will always be in case 1.

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

      why g' | g ?????

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

        Because $$$g' \mid q$$$, and $$$g' |\ (x - a_i)\ \forall i$$$ , so $$$g' |\ (x - q - a_i)\ \forall i$$$, so $$$g' |\ {gcd}_i(x-q-a_i) = {gcd}_i(mx-a_i) = g$$$.

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

      Why we can subtrack q? Is it because of it is constant and a multiple of g'?

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

        Yes. Also, because we want to compare with case 1, and subtracting $$$q$$$ from all $$$x - a_i$$$ make it the same as case 1.

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

          Ok that makes sense but how we can be sure that subtraction won't affect? I didn't get that. And thank you.

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

Even though I gained rating,but I have to blame this round. For Problem C,my friend write a wrong solution and submit his code. But he passed all the pretests!!! Do you know why he was wrong? We know that we need to consider all the edges of the white rectangle. But he only considered the rows of the white rectangle,and he passed all the pretests!!!! Why?This is amazing,man. What a shame of the pretests.

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

    Pretests were not meant to be complete, though.

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

      But it's really amazing.There's one-half chance of error. The author of this problem let him passed his pretests. I think the author is to blame.

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

        Before blaming the author, consider that he can't add an unlimited number of pretests. Imagine how long solutions will be tested during the round, if each of them will have to go through 100 pretests instead of 30 (the total number of tests for task C is 134). Now imagine the following situation: you are the author and you must predict all the possible mistakes of the participants in order to add 30 pretests that can catch all these mistakes. Is it possible? I highly doubt it. I know how disappointing it is to get the verdict “solution is hacked” (look at my last round (Educational Codeforces Round 67 (рейтинговый для Див. 2)), two of my solutions were hacked). But at the same time, I understand that it is my fault, because I should come up with my own strong tests for my solution before submiting it. Yes, sometimes there are rounds with very really bad pretests (more than 1000 hacks for one problem), but this doesn't mean that it is worth talking about “weak pretests” every time you or your friend have a hacked solution.

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

I am not getting the solution to E1.

Can someone explain it to me in easy language? Its poorly written

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

    Yes plz explain E1 it's quite unclear from editorial

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

      Check out my solution here — Solution

      Essentially we are successively narrowing down in what part of the infinite sequence we are in currently. For each integer $$$i \in \mathbb{N}$$$ we write their decimal representations from $$$1$$$ to $$$i$$$ and then start the process again for $$$i+1$$$.Let us call this process the "run" of $$$i$$$, i.e. the for each $$$i$$$ we are writing the string $$$run(i)$$$. $$$run(1) = \texttt{1}$$$, $$$run(10) = \texttt{12345678910}$$$ and so on. Appending number representations in order gives us a run, and appending these "runs" in the order they are produced gives us the infinite string.

      Let $$$len(run(i)) = r_i$$$, and the length of the sequence ending with the $$$i$$$-th run as $$$s_i$$$. If the number of digits in $$$i$$$ is $$$dig_i$$$, we have $$$r_i = r_{i-1} + dig_i$$$. The number $$$dig$$$ stays the same for $$$i$$$ from $$$10^{k}$$$ to $$$10^{k+1} - 1$$$. So we keep the run length $$$r$$$ as an accumulator for $$$dig$$$ ( incrementing $$$dig$$$ at every power of 10 ), and the sequence length $$$s$$$ so far as an accumulator for $$$r_i$$$, i.e. $$$s_i = s_{i-1} + r_i$$$. When $$$s_i \geq k$$$, we now know we want the digit at $$$k - s_{i-1} = l$$$ in $$$run(i)$$$.

      We do a similar procedure within $$$run(i)$$$ (we no longer need the accumulator $$$s_i$$$), and when $$$r_j \geq l$$$ we want the digit at position $$$l - r_{j-1} = d$$$ from the left in the representation of the number $$$j$$$. Calculating this, we get the answer.

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

        thanks a ton !.......ur submission is so good as if it is a sculpture

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

    I solved E1 moments ago.It looks very complex but it is just brute force.It's proved to be O(sqrt(k))....much easier than C which I did with implements.if I knew E1 could be brute force in the contest....

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

    I think the code below the tutorial is more comprehensible. I will try to explain it from the perspective of implementation. It is given that the $$$i$$$ th block consists of numbers from $$$1$$$ to $$$i$$$. So the $$$i-1$$$ th block consists of numbers from $$$1$$$ to $$$i-1$$$. Let $$$L_i$$$ be the length of block $$$i$$$. Clearly we have $$$L_i=L_{i-1}+\text{len}(i)$$$, where $$$\text{len}(i)$$$ is the length of number $$$i$$$. So we can set variable $$$lst$$$(presented in code from the solution) to track the length of current block. Note that $$$\text{len}(i)=1, i\in [0,9]$$$ and $$$\text{len}(i)=2, i\in [10,99]$$$, etc. We can find that $$$\text{len}(i)$$$ increases at the positions $$${10,100,1000,...}$$$. So we can use variable $$$nxtpw$$$ as the position where $$$\text{len}(i)$$$ is going to change.So far for each block $$$i$$$, we can get its block length as $$$lst += numlen$$$. Next we are going to find whether the query $$$k$$$ belongs to the current block. We achieve this by judging whether $$$k>=lst$$$ (if true, subtract $$$k$$$ by $$$lst$$$ so that $$$k$$$ is always the relative position of target character with respect to the next block). Once we get some $$$k$$$ such that $$$k<lst$$$, we use the same policy to decide which number in the block position $$$k$$$ belongs to.

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

orz cmz

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

I'm very unhappy to know I get a WA on the test31 on C.In the contest I passed all the pretests so I thought I would get an AC but things went wrong anyway.I thought I might be 1500+ rating but today when I got up I found my rating up but my rank in the contest down,so werid but I had to accept the truth.I recommended C to my friends who didn't attend this contest and I was proud to say I passed the pretests.No matter what,it was my fault.I wrote a program which was not to be so acceptable,but I don't want to taste the feeling of getting an WA in the System Test anymore.So could please strengthen the pretests in the next contest?

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

For problem F, my solution achieved $$$O(n)$$$ through simple approaches.

Let $$$f_i$$$ denote the minimum cost to make rooms from $$$1$$$ to $$$i$$$ to be connected. In this case, $$$f_i$$$ should be non-decreasing. So for each $$$i$$$, the optimal result of $$$f_i$$$ is: 1. install a router in the first room in $$$[i-k, i)$$$ which can be equipped with a router; 2. link directly; 3. wait for the first router after $$$i$$$ to cover this room.

So we can use $$$dp_i$$$ to compute $$$f_i$$$ for the first 2 choices. When dealing with a router, we use current $$$dp$$$ value to update backwards all $$$dp_i$$$ in the segment between last router and current router, to apply the choice 3.

My Submission: 61007600

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

    When you are updating the $$$dp$$$ backwards, shouldn't the condition be $$$j >= i - k$$$ instead of $$$ j >= 0$$$?

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

      It's also right, because router $$$i$$$ can only affect rooms $$$[i-k, i]$$$.

      But writing $$$j>=0$$$ can already achieve linear time complexity.

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +45 Vote: I do not like it

Linear solution for F:

Let's construct the answer from right to left. We denote the minimum cost to connect all rooms, starting from $$$i$$$, as $$$dp_i$$$ (in my solution, rooms are $$$0$$$-indexed, so $$$dp_0$$$ is the answer, and initially $$$dp_n = 0$$$).

Let's suppose we have calculated $$$dp_i$$$, and now we want to update other states using it. If we have already connected all rooms from $$$i$$$ to $$$n - 1$$$, the next room we will have to connect is room $$$i - 1$$$.

There are two ways to connect it. The first is easy — just connect it without any router, so $$$dp_{i - 1} = min(dp_{i - 1}, dp_i + i)$$$.

The second way is to use a router. Which one should we use? First of all, the cost of installing a router and connecting it decreases when we go from right to left, so, to minimize the cost of connecting this room to the Internet, we should choose the leftmost room where a router can be installed that is not too far from the current room. Furthermore, if all rooms from $$$i$$$ to $$$n - 1$$$ were connected and we choose to connect room $$$i - 1$$$ using a router in room $$$x$$$, then afterwards all rooms from $$$x - k$$$ to $$$n - 1$$$ will be connected. So choosing the leftmost router that covers the current room is always beneficial.

So there are only two types of transitions in this dynamic programming:

1) If we have calculated $$$dp_i$$$, update $$$dp_{i - 1} = min(dp_{i - 1}, dp_i + i)$$$;

2) If we have calculated $$$dp_i$$$, find the leftmost room $$$x$$$ such that a router can be installed in this room, and this router will cover room $$$i - 1$$$. Install a router in that room and update $$$dp_{max(0, x - k)} = min(dp_{max(0, x - k)}, dp_i + (x + 1))$$$.

If we precalculate the leftmost router that can affect each room, this solution will work in $$$O(n)$$$. Solution code

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

In Problem B: For input : 3 20 10 20

output: 43 2 3 1 Is Wrong.Why? We can select any 20, first or last.

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

    because right answer is 3 1 2 or 1 3 2. You need to sort Ai by descending

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

O(1) solution for E2: http://codeforces.com/contest/1216/submission/61064504

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

Can some one tell me how to prove this thought is wrong: if the swords in each room before hand is bigger than max(a), so you may have a lagger gcd as a result, and (k1 + k2 + ... + kn) which is y could be smaller.

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

    No, if there are more swords in each room originally than $$$max(a)$$$ then the new gcd must be less than the old gcd (unless all rooms have the same number of swords). Check out this explanation.

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

My alternate solution to F. Lets create a segment tree with lazy updates. The tree basically allows us to perform range updates on an imaginary array v[] in which the i th position stores the cost of connecting the first i rooms to the internet. Now lets iterate from 0 to n — 1. Let s be the inputted string. If s[i] is 0, then update v[i] with min(v[i], v[i — 1] + i + 1) else range update on the segment tree. This does not require any complicated transitions or complicated data structures. Complexity is O(nlogn).

Here is my code: Code

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

In case you got confused reading E2 editorial here: Let's add add⋅cnt+cnt(cnt+1)/2⋅cnt

I think the second summand is cnt(cnt+1)/2 . len I mean its pretty logical I don't get why the editorial says to multiply by cnt.

Also, I think the time complexity is O(log n) for each query. well with some constant of course if optimally implemented.

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

my problem c solution: https://codeforces.com/contest/1216/submission/61159190

First we check if any corner is outside of both black rectangles, if it is -- then white is visible if all corners are inside black areas, then I check if projection to x is inside black fully and projection to y is inside black fully. if it's not -- then white is visible. If both: horizontal and vertical projections are covered with black projections -- then white is invisible. I believe it is more intuitive.

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

please tell the algorithm for F question to solve in linear time. if possible please elaborate the editorial given too.

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

In E2, add * cnt + ((cnt * (cnt + 1)) / 2) * len should be added to the total sum of lengths, not add * cnt + ((cnt * (cnt + 1)) / 2) * cnt Since, for numbers with length equal to len, number of new digits added to the current string of digits will be (1 * len) + (2 * len) + (3 * len) + ... + (cnt * len) ``

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

In Problem-D, how does one prove that there exists an optimal solution $$$y=\dfrac{\sum_{i = 0}^{n-1}(x-a_{i})}{g}$$$ for $$$x=a_{max}$$$ — as in why doesn't one have to check for $$$x>a_{max}$$$? Note that $$$g = gcd(x-a_{0}, x-a_{1}, ..., x-a_{n-1})$$$.

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

my O(n) solution to F with dp and monotonic stack (actually deque) 211377823

→ Reply