### vovuh's blog

By vovuh, history, 12 months ago,

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

• +74

 » 12 months ago, # |   0 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.
•  » » 12 months ago, # ^ |   0 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
•  » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   -29 @ZeroAmbition Definitely not your fault, there should be seperate editorialists for contests instead of using Tester's solution the editorialist should write the code !
•  » » » » » 12 months ago, # ^ |   +1 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
•  » » » » » » 12 months ago, # ^ |   -15 Maybe having bigger teams for contests could help... All this work should be done by multiple people.
 » 12 months ago, # |   -6 The tutorial of problem E1 is poorly written. Please review it.
•  » » 12 months ago, # ^ |   0 See if this explanation makes sense.
 » 12 months ago, # |   0 For problem D, can someone give a proper proof for why the solution is optimal?
•  » » 12 months ago, # ^ |   0 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.
•  » » 12 months ago, # ^ | ← Rev. 6 →   +9 Let the largest leftover pile be $max$, and smallest be $min$. We consider three cases — 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}}$. 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$. 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.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Shouldn't it be If q divides g'? Edit : My English is bad sorry :D
•  » » » 12 months ago, # ^ |   0 why g' | g ?????
•  » » » » 12 months ago, # ^ |   0 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$.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Why we can subtrack q? Is it because of it is constant and a multiple of g'?
•  » » » » 12 months ago, # ^ |   0 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.
•  » » » » » 12 months ago, # ^ |   +1 Ok that makes sense but how we can be sure that subtraction won't affect? I didn't get that. And thank you.
•  » » » » » » 12 months ago, # ^ |   0 An example: let ${a = [4, 8, 12]}$, so ${max = 12}$ and ${g = 4}$. If ${q = 1}$, ${x = 13}$, then ${g' = 1}$.If ${q = 2}$, ${x = 14}$, then ${g' = 2}$.If ${q = 4}$, ${x = 16}$, then ${g' = 4}$.If ${q = 6}$, ${x = 18}$, then ${g' = 2}$.If ${q = 7}$, ${x = 19}$, then ${g' = 1}$.If ${q = 8}$, ${x = 20}$, then ${g' = 4}$.As we can see, ${g'}$ is at most equal to $g$. Subtracting ${q}$ from ${x}$ makes us get ${g}$.
•  » » » » » » » 12 months ago, # ^ |   0 Thank you
•  » » » 12 months ago, # ^ |   0 This is awesome and You are awesome!!
 » 12 months ago, # |   -33 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.
•  » » 12 months ago, # ^ |   +4 Pretests were not meant to be complete, though.
•  » » » 12 months ago, # ^ |   -14 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.
•  » » » » 12 months ago, # ^ |   0 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 (Rated for Div. 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.
•  » » » » » 12 months ago, # ^ |   0 I know it's my friend's fault.I am not complaining. And I agree with you.I think there's a misunderstanding. I just think a good author should give a strong pretest. Perhaps his pretest can't predict all the possible mistakes. And it's not strange.After all,being hacked is not worth complaining. Maybe my words are not so appropriate so you guys misunderstood my meaning.I am just teasing the pretest and the solution of my friend.
 » 12 months ago, # |   0 I am not getting the solution to E1.Can someone explain it to me in easy language? Its poorly written
•  » » 12 months ago, # ^ |   0 Yes plz explain E1 it's quite unclear from editorial
•  » » » 12 months ago, # ^ |   +2 Check out my solution here — SolutionEssentially 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.
•  » » » » 4 months ago, # ^ |   +1 thanks a ton !.......ur submission is so good as if it is a sculpture
•  » » 12 months ago, # ^ |   0 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....
•  » » 12 months ago, # ^ |   +2 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  » 12 months ago, # | 0 orz cmz  » 12 months ago, # | -35 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?  » 12 months ago, # | 0 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 •  » » 12 months ago, # ^ | 0 When you are updating the$dp$backwards, shouldn't the condition be$j >= i - k$instead of$ j >= 0$? •  » » » 12 months ago, # ^ | +1 It's also right, because router$i$can only affect rooms$[i-k, i]$.But writing$j>=0$can already achieve linear time complexity.  » 12 months ago, # | ← Rev. 3 → +45 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 •  » » 12 months ago, # ^ | 0 Nicely Written..!! •  » » 12 months ago, # ^ | 0 very clear •  » » 12 months ago, # ^ | ← Rev. 2 → 0 I used dp in a simillar way but getting wrong answer on Test case 26, here is my submission •  » » 12 months ago, # ^ | 0 Thanks BledDest, you made solution crystal clear. :) •  » » 3 months ago, # ^ | ← Rev. 2 → 0 Thanks BledDest, very nice explanation!!  » 12 months ago, # | 0 How can there be half-integer solution in first solution of C? Can someone give an example?  » 12 months ago, # | 0 In Problem B: For input : 3 20 10 20output: 43 2 3 1 Is Wrong.Why? We can select any 20, first or last. •  » » 12 months ago, # ^ | 0 because right answer is 3 1 2 or 1 3 2. You need to sort Ai by descending  » 12 months ago, # | 0 Not getting the editorial solution of problem F. Please someone explain more. Thanks in advance.  » 12 months ago, # | +7 O(1) solution for E2: http://codeforces.com/contest/1216/submission/61064504 •  » » 12 months ago, # ^ | 0 explain please  » 12 months ago, # | 0 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. •  » » 12 months ago, # ^ | 0 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. •  » » » 12 months ago, # ^ | 0 Excellent work! thank u sir :)  » 12 months ago, # | 0 in problem b, tutorial solution for first case != announcement solution???  » 12 months ago, # | 0 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 •  » » 6 months ago, # ^ | 0 wow..nice approach  » 12 months ago, # | 0 In E1's solution, "...and carry the length of the last block." what does this mean ?  » 12 months ago, # | 0 In case you got confused reading E2 editorial here: Let's add add⋅cnt+cnt(cnt+1)/2⋅cntI 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.  » 12 months ago, # | 0 my problem c solution: https://codeforces.com/contest/1216/submission/61159190First 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.  » 12 months ago, # | 0 I got confused in the E2 tutorial. Can anyone better clarify what is 'add' and 'cnt'?  » 12 months ago, # | 0 In rectangle problem first tutorial with time complexity O(N), why is this answer possible. I two rectangles cover white rectangle such that first black cover all x and second y. then how is it correct?  » 12 months ago, # | 0 please tell the algorithm for F question to solve in linear time. if possible please elaborate the editorial given too.  » 12 months ago, # | 0 Can someone explain the solution to problem C clearly? •  » » 11 months ago, # ^ | 0 If you try to analyse the problem, there are only a few cases by which you can completely cover the while paper. They are as follows: Cover partially or fully the left part of the paper by either of the black papers. Note that in this case, the height of the black paper$>=$height of the white paper. Now cover the remaining right portion with other paper if required. Cover partially or fully the top part of the paper by either of the black papers. Note that in this case, the breadth of the black paper$>=$breadth of the white paper. Now cover the remaining bottom portion with other paper if required. Now you can easily check these conditions if they are true or not, in$O(1)$. Hope that helps. •  » » 11 months ago, # ^ | 0 https://codeforces.com/contest/1216/submission/63695932Check This It's Full Of Comments and follows a very basic brute force approach.  » 12 months ago, # | 0 there is a typo in tutorial of Number Sequence(Hard version) the formula should be add * cnt + cnt * ((cnt+1)) / 2 * len not add * cnt + cnt * ((cnt+1)) / 2 * cnt   » 12 months ago, # | ← Rev. 2 → 0 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)   » 5 months ago, # | ← Rev. 4 → 0 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})\$.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I had the same doubt, actually, you can but the problem asks minimum now if you see we are calculating gcd of positive numbers, which guarantees that maximum can always be achieved, like in worst case gcd could be 1, but the number of people broke into will increase but can surely achieve the maximum for each which is less than the maximum. so we just find the maximum gcd which satisfies all conditions hence reduce the number of people broke into minimum.
 » 5 months ago, # |   0 Solution to C can be simplified if we consider the cases where both rectangles could possibly cover the white rectangle : This leads us to 3 cases : 1. Either one of the black rectangle could completely cover the white rectangle 2. If there is a common border in the black rectangles, then they will cover up the white rectangle if their y range is at least [y1,y2] and their combined x range covers [x1,x2]. 3. If there is no common edge then they can cover only if both of their y range is from y1 to y2 and their combined x range cover [x1,x2]. The same check function could be called to check for x range by interchanging respective x's and y's . Here's the link to my solution
•  » » 5 months ago, # ^ |   0 *case 2 could be included in case 3 itself !