### pikmike's blog

By pikmike, history, 11 months ago, translation, 1260A - Heating

Tutorial

1260B - Obtain Two Zeroes

Idea: Roms

Tutorial
Solution (Roms)

1260C - Infinite Fence

Tutorial

1260D - A Game with Traps

Idea: BledDest

Tutorial
Solution (BledDest)

1260E - Tournament

Idea: Roms

Tutorial
Solution (Roms)

1260F - Colored Tree

Idea: RDDCCD

Tutorial
Solution (RDDCCD)  Comments (76)
 » I did not understand 1260C - Infinite Fence. Can anybody give me a detailed explanation?
•  » » Here for a nice explanation by iica
•  » » Search about diofantic equations.
•  » » 11 months ago, # ^ | ← Rev. 10 →   Goal : check if there is at least k red cells in between two consecutive blue cellsExtended Euclidean Algorithm : a*x + b*y = gcd(a,b)so , in our case we can write : r*x - b*y = g (say, g = gcd(r,b) )that is , r*x = b*y + gwhich implies , for any pos = b*y colored blue , we have (pos + g) colored red(here , two consecutive blue cells pos and pos+b) generally , we have to use color red for these (m+1) cells : pos+g ,pos+g+r , pos+g+2r , pos+g+3r , ....... (pos+g+m*r) where , m>=0 and (pos+g+m*r)<(pos+b) ==> (g+m*r)
•  » » » hey this may sound silly but can you please explain why in our case ax-by=gcd(a,b) works
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   say , we colored b*y blue. Now, smallest number greater than b*y that must be colored red is b*y+q. (q>0)so r*x = b*y+q; what will be the minimum positive value of q ?By extended euclidean we know that r*x - b*y = ? has smallest positive integer solution gcd(b,r)
•  » » » » » How do you get the idea of using Gcd?
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   Can you please explain, how can we say that the x and y obtained are positive? (Because for our requirement they must be positive, suppose x and y are both negative, then also rx -by = 1 will be satisfied, however this is not what we would like) Extended Euclidean states there exists integer x, y such that ax + by = gcd(a,b). I am not able to connect the dots in a proper way. Thanks!
•  » » » 4 months ago, # ^ | ← Rev. 2 →   You have explained very well but you haven't explained why are we dividing r and b with GCD(r,b) please reply i am very weak in GCD questions.
•  » » why are we diving r and b with GCD(r,b) somebody please explain in turorial its written very shortly someone plzz explain
 » For the problem C, should not we just check k*r>b. why do we check for (k-1)*r + 1 > b. can some explain this.
•  » » 11 months ago, # ^ | ← Rev. 2 →   You know, if b is very large, the answer is REBEL, because there are too many planks between plank pos and plank pos+b. And if b is small enough, you have to paint only few planks between pos and pos+b, then the answer is OBEY.As editorial says, what we are concerned about is whether it will happen or not that there are too many planks between pos and pos+b. Here "too many" means "if you paint pos+1 in red, your k'th red plank comes before next blue plank pos+b".This is like, if a=3 and k=5, red planks are [pos+1, pos+4, pos+7, pos+10, pos+13]. Thus you must worry if pos+13 < pos+b or not. This "13" comes from (5-1)*3+1 (see this figure below). 1 2 3 4 5 #..#..#..#..# In general, if (k-1)*r+1 < b, it means in the worst case (like above) you will have k (or more) red planks between blue planks, then the answer is REBEL. If not, it means in any cases next blue plank comes before your k'th red plank, then the answer is OBEY.
•  » » » Assume R<=B If ( (k-1)*R + 1
•  » » » » I guess your R and B happen to have gcd > 1, don't they?You had to assume gcd(a, b) = 1 ....
•  » » » » » 7 months ago, # ^ | ← Rev. 4 →   What is wrong in the following approach ? Assume (r < b) We start putting red from index pos+gcd(r, b), and we check if we can put more than k red till pos+b. It is equivalent to we have b-1 places, we start marking from index gcd(b, r) and mark each rth index. If we mark >= k index, answer is RABEL. which translates to (b-1)-(g-1) >= k*r : RABELUpd: Figured out. The equation translates to 1 + ((b-1)-(g-1)-1)/r < k.
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   Then what will be answer if GCD(r,b) > 1 and in tutorial why there the asking to consider separately if GCD is not 1
 » Here I provide another solution for F. Colored Tree.Suppose that there are $c_{max}$ moments and each node appears at some moment $t$ if and only if $l_i\le t\le r_i$.At each moment there appears several nodes on the tree, and each pair of these nodes $(x,y)$ at this moment makes contribution of $\prod_{i=1}^n (r_i-l_i+1)\times \frac{1}{r_x-l_x+1}\times \frac{1}{r_y-l_y+1}$ to the answer.We "add" and "delete" the nodes base on moments they "appear" and "disappear" one by one and there are only $O(n)$ such events. For each event we calculate the changes of the contribution among the current nodes. This can be done in $O(\log n)$ doing divide-and-conquer on the tree. Specifically, let $w_x$ be $\frac{1}{r_x-l_x+1}$, and if $(x,y)$ meet at node $z$, the contribution they make is $(dis_{x,z}+dis_{y,z})\times w_x\times w_y=dis_{x,z}\times w_x\times w_y+dis_{y,z}\times w_x\times w_y$, where $\prod_{i=1}^n (r_i-l_i+1)$ will be calculated later. Each half can be calculated independently as we can maintain $\sum w_x\times dis_{x,i}$ and $\sum w_x$ on each node $i$. As we know, this can be done in $O(n\log n)$.After those events taking place at moment $t$, we add up the current contribution to the answer. Don't forget that in the end the real answer should be $ans\times\prod_{i=1}^n (r_i-l_i+1)$.View code to see details.Code1 ($O(c_{max}+n \log n$): 65904158Code2 ($O(c_{max}+n \log^2 n)$ with a smaller constant): 65902583
 » Why a+b mod 3 is zero in Problem B. Would someone please explain the idea
•  » » Because, at every step we select some random integer x. Then either we subtract x from a and 2x from b or vice versa. So at every step we are subtracting (x + 2x) or 3x from a + b. So, at some step to get both values of a and b to be zero we have to have sum of initial value of a and b a multiple of 3 otherwise it won't happen. Thats why (a + b) mod 3 must be 0.
•  » » Let x be number of times we subtract 1 from a and y be number of times we subtract 1 from b.If solution exists then following equations hold true: $a - x - 2y = 0$ $b - 2x - y = 0$Adding these two equations we get: $a + b = 3(x + y)$So, $a + b$ is a multiple of 3. Therefore $(a + b) \bmod 3 = 0$
 » In the tutorial of problem B, why a.2 >= b. Please someone explain.
•  » » My solution. Denote x as the number of time to subtract 2 from a and subtract 1 from b, y as the number of time to subtract 2 from b and subtract 1 from a, then: $\left\{ \begin{array}{lcr} a-2x-y&=&0\\ b-2y-x&=&0 \end{array} \right.$It's easy to make it simple: $\left\{ \begin{array}{lcr} 3x&=&2a-b\\ 3y&=&2b-a \end{array} \right.$Because $x\geq 0$ and $y\geq 0$, so we should have $2a-b\geq 0$ and $2b-a\geq 0$
•  » » » Thanks. I got it.
•  » » » This solution must be in the tutorials.
•  » » mathematically we can prove this as: we are given two numbers a and b,lets assume a2a, so let b=2a+1; substituting in the equation above,we get: (2a+1)-2x=2t or 2(a-x)+1=2t or 2t+1=2t (substituting a-x=t from 1st eq) which is not possible, thus the maximum possible value of b should be 2a. The logical explanation for this can be that while reducing a and b to t and 2t form, the highest possible value of t would be min(a,b)=a, but for obtaining its corresponding 2t value from b, we need to reduce b further keeping a constant, since b>2a. Thus b always needs to be reduced by an additional (b-2a) value every time while trying to obtain results. You can try this using an example where a=12 and b=34
•  » » » How did you get the intuition that we should also check for b >= 2a along with (a+b) mod 3 condition? I am new to problem solving , just asking so that I can improve
 » IN Q-2...why 2a>b...this condition is required? plz tell me the idea
•  » » if 2*a >= b is false, then b is more than twice as big as a, even if you always remove 2x from b until it is zero then you must subtract half of b from a, which would make a negative (b>2*a => b/2>a). In the editorial the author swaps a and b so that b is always the biggest number, this way he just has to check for 2*a > b, and not 2*b > a as well.
•  » » Let $x_1, x_2, ..., x_k$ be the numbers you use so $a := a - x$ and $b := b - 2x$ was done some time in the "process" of turning $a$ to $0$ and $b$ to $0$. Also, let $y_1, y_2, ..., y_m$ be the numbers you use so $a := a - 2y$ and $b := b - y$ was done some time in the "process" of turning $a$ to $0$ and $b$ to $0$.Notice that at the end we get: $a - x_1 - x_2 - ... - x_k - 2y_1 - 2y_2 - ... - 2y_m = 0$ $b - 2x_1 - 2x_2 - ... - 2x_k - y_1 - y_2 - ... - y_m = 0$Or... $a - (x_1 + x_2 + ... + x_k) - 2(y_1 + y_2 + ... + y_m) = 0$ $b - 2(x_1 + x_2 + ... + x_k) - (y_1 + y_2 + ... + y_m) = 0$Let $X = x_1 + x_2 + ... + x_k$ and $Y = y_1 + y_2 + ... + y_m$. Interesting observation: this means that you only need to do at most one operation of the first or second type, with the number used being the sum of all the other numbers. Then: $a = X + 2Y$ $b = 2X + Y$Substituting $X = a - 2Y$ from the first into the second equation and simplifying, we get: $b = 2(a - 2Y) + Y$ $b = 2a - 3Y$ $3Y = 2a - b$ $Y = (2a - b) / 3$Since $Y \geq 0$, $2a - b \geq 0$, so $2a \geq b$. Also, from here, you can get $X$. You only need to check that $X \geq 0$ and $Y \geq 0$.
 » This contest is so great!I love it!
 » PikMike E is a simple greedy. Look at the solution. 2 line logic. 65862147
•  » » and me being an absolute non java coder — which are the two lines to read ?
•  » » » ritesh1340  for (int i = n - 1; i >= 0; i--) { if (ar[i] == -1) break; smaller.insert(ar[i]); if (Integer.bitCount(i + 1) == 1) { ans += (smaller.getLowest()); smaller.remove(smaller.getLowest(), 1); } } It's just that whenever i is power of 2, remove the smallest element and add it into answer. You can use priority queue.
•  » » Can you please explain the reasoning behind this approach ? How does this greedy work ?
 » Can somebody explain the formula of 1260A — Heating to me....I am so confused..d = sum / c; rem = sum % c; answer = rem * (d + 1) * (d + 1) + (c — rem) * d * d <----- this formulaI don't understand even read the editorial...
•  » » Anyone explain A
•  » » » I explained it here.
•  » » 11 months ago, # ^ | ← Rev. 4 →   Think of the problem this way. You have some numbers $a_1, a_2, \ldots, a_c$, where $a_i \geq 0$, and $a_1 + a_2 + \ldots + a_c = sum$. You need to minimize $a_1^2 + a_2^2 + \ldots + a_c^2$.If $c \geq sum$ then you can just use $sum$ ones, and the rest are zeros. The cost would be $1^2 + \ldots + 1^2 + 0^2 + \ldots + 0^2 = sum \cdot 1^2 + (c-sum) \cdot 0^2 = sum$.Now, let's consider the case when $c \lt sum$. It can be proven that it's optimal for all the numbers to be as close as possible (this is done in the editorial).So, how to make them as close as possible? If $sum$ is divisible by $c$, we can do $a_i = sum/c$. But most of the time it won't be, and we can't have decimal numbers, only integers.To get the intuition for how to make them as close as possible, let's see an example. $sum = 17, c = 4$. So we need to split $17$ into $4$ parts that sum back to $17$, and the parts are as close as possible. We can do $4, 4, 4, 5$. If we had $sum = 18, c = 4$, we'd get $4, 4, 5, 5$. If we had $sum = 19, c = 4$, we'd get $4, 5, 5, 5$. If we had $sum = 20, c = 4$, we'd get $5, 5, 5, 5$. If we had $sum = 21, c = 4$, we'd get $5, 5, 5, 6$. And so on. How do we do this generally?Set $a_i = \lfloor sum/c \rfloor$. But now the total sum is too small, because we are rounding down the numbers. So, to make it big enough, we will add $1$ to some of the numbers. From number theory we know: $sum = \lfloor sum/c \rfloor \cdot c + (sum \ mod \ c)$, and also $(sum \ mod \ c) \lt c$, so we can just add $1$ to exactly $sum \ mod \ c$ of the numbers.In the end, we have $sum \ mod \ c$ numbers with value $\lfloor sum/c \rfloor + 1$, and the rest, exactly $c - (sum \ mod \ c)$, are $\lfloor sum/c \rfloor$. The total cost will be: ${\lfloor sum/c \rfloor}^2 \cdot (c - (sum \ mod \ c)) + (\lfloor sum/c \rfloor + 1)^2 \cdot (sum \ mod \ c)$$\lfloor x \rfloor$ is the floor function. $a \ mod \ b$ is the modulo operation. You should understand these before trying to solve this problem, probably.Let's see an example. $sum = 6, c = 4$. We have $4$ numbers, we need their sum to be $6$, and we need to minimize the sum of their squares. $\lfloor sum/c \rfloor = \lfloor 6/4 \rfloor = 1$, So initially we have $1, 1, 1, 1$. $sum \ mod \ c = 6 \ mod \ 4 = 2$, so we need to add $1$ to exactly $2$ of the numbers. So we get $1, 1, 2, 2$, which is indeed optimal.Another example. $sum = 11, c = 4$. $\lfloor sum/c \rfloor = 2$, so initially we have $2, 2, 2, 2$. $sum \ mod \ c = 3$, so we need to add $1$ to $3$ of the numbers. So we get $2, 3, 3, 3$, which is optimal.
•  » » » Thank you so much !!
•  » » » Hey can you explain the proof given in the editorial?
 » ＂ All of this can be done with HLD＂　What's the meaning of HLD?
•  » » Heavy-Light Decomposition
•  » » » Thanks, cool.
 » Can anyone help me as to why do we need to do a * 2 >= b for problem B? I didn't really get it :(
•  » » Suppose that a is the minimum of both So obviously we have to decrease b, minimum value of x we can choose is 1 ,keep doing this until a becomes 0 ,b=b-2*a,so if b>2*a not possible
•  » » I explained it here.
 » Excuse me, what are event processing algorithms ?
 » 11 months ago, # | ← Rev. 4 →   Task E, why this approach is incorrect? This our array:...-1(i).........a(n)For the first round a(n) plays with max on [i+1, n-1]If a(n-1) is free it plays with next max on [i+1, n-2]And so on...If there is last free player on [i+1, n] (let it be j) it plays with the first free player from the beginningIf the first free player from the beginning is out i, than ans+=a(j)Next round...And so on until only player i stays My code: https://codeforces.com/contest/1260/submission/66071106
•  » » My first approach was same as the one you described.I am also still unable to figure out why this is incorrect.
 » 11 months ago, # | ← Rev. 2 →   Problem E: My approach is this: I want my friend boxer to face the boxers with lower strength so that there is no need to pay bribe. So,I match my friend with a less strength boxer. Also, i try to match less strength boxers among themselves so that more of them remain till the end. Also,I make the strongest boxer match with the one that takes most bribe. Then match the next strongest unmatched boxer to the next unmatched boxer who takes the most bribe and so on....I repeat the process log n times. I am getting wrong answer on test case 6. Can anybody point out the mistake in this approach. Thanks in advance.
 » 11 months ago, # | ← Rev. 2 →   Problem EPlease help me find why this approach is incorrect ?Why can't we greedily make the strongest boxer defeat n/2-1 boxers which demand the highest bribe and our stronger than our friend boxer ?Then we repeat for the remaining boxers ?
•  » » 11 months ago, # ^ | ← Rev. 2 →   What will your algo output here? (ans is 23)161 2 3 4 5 -1 9 10 11 12 7 8 13 14 15 16
•  » » » My algo outputs 24.But can you give me a tournament with ans 23 ?? (Tried a lot to come up with an example)
•  » » » » Okay found one, (1,2)(3,4)(5,-1)(12,7)(9,10)(11,8)(13,14)(15,16)(2,4)(-1,7)(10,8)(14,16)(4,-1)(8,16)...............pay 7 bribe(-1,16)-1.............pay 16 bribeTotal 23
 » How to solve B using binary search?
 » Why problem D,we should use this greedy strategy ？If two trap have union,we needn't return. orz~~
 » I did not understand In problem D req_time += s.y - s.x + 1; lastr = s.y; Why we should do (s.y — s.x +1) ?I thought req_time +=(s.y — lastr); lastr = s.y;So I wrong answer!Could you explain this problem ?
•  » » same doubt as we just need to find the max r value in those selected segments and that should give the req_time but that's now what is being done here..don't understand why
•  » » If a trap (s.x,s.y) is after lastr, fully, then the part from lastr to s.x is not traversed thrice, and thus isn't needed to be included into req_time.
 » Someone, Please Explain how to solve E?
• »
»

In brief, let f be the position of my friend. If f!=n, use then n must be bribed. Since 1) n can win [n/2+1, n] and become the top while [n/2, n-1] each has a sure win in the segment of [n/4+1,n/2], then we find the cheapest in [n/2, n-1] to bribe to win [n/4+1,n/2] for our friend f — throw out the one bribed. Then consider [n/8+1,n/4] segment in a similar way, bribe the cheapest one in [n/4, n-2] until we have covered everyone stronger than f.

The code is as follows.

# include<bits/stdc++.h>

using namespace std;

using ll=long long; // #define _debug

vector a; int s, t, n, f, r; ll cost = 0; vector h;

struct greaters{ bool operator()(const int& a,const int& b) const{ return a>b; } };

int main(){

# endif

cin >> n;
a.resize(n + 2);
h.resize(n + 2);

for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == -1) f = i;
}

s = n;
t = n + 1;

r = n - f;

while (r > 0){
make_heap(begin(a) + s, begin(a) + t, greaters());
//cout << a[s] << endl;
cost += a[s];
t--;
a[s] = a[t];
n /= 2;
s -= n;
r -= n;
}
cout << cost;


}

 » How to solve D in O(nα(n)) ?
 » Assume R<=B If ( (k-1)*R + 1
 » Can someone please explain the solution for E? I don't get how the strongest player can defeat 'n/2-1 other players' which is written in the editorial. He will participate in log2(n) games at most, how can he defeat n/2-1 others? If someone can also explain the greedy approach to this problem, it would be highly appreciated by everyone who has been searching for it
•  » » Here's my greedy, it's super simple: Replace all numbers to the left of $-1$ by zero and remove $-1$ from the array. Now you can imagine that you are the weakest boxer and the only way to win is by bribing. Obviously you must bribe the strongest boxer, so add the last element of the array to the solution. The second boxer you must bribe must be among the strongest $n/2$ remaining boxers, so pick the smallest number among those. The next boxer you must bribe has to be among the strongest $n/2 + n/4 - 1$ remaining boxers, and so on.Code: 79663574
•  » » » Hi, thank you for replying. I get the point that the last player (nth one) must be bribed, as otherwise our player would never win. But why should we chose the best among the n/2 strongest for our second bribe? Isn't it possible that one of n/2 strongest was defeated in previous rounds?
•  » » » » Because the strongest boxer cannot beat all $n/2$ of them you have to bribe at least one. The strongest boxer can only beat $n/2-1$ other boxers.
•  » » 4 months ago, # ^ | ← Rev. 2 →   The strongest player defeats $\log{n} - 1$ players directly. Now we can think that all players, who were defeated by our player are free and we can use these $\log{n} - 1$ players to defeat others. Those players also defeat some players directly continuing this recurrent process. So, after some thinking we can get recurrent formula: $f(x) = x - 1 + f(x - 1) + f(x - 2) + ... + f(1)$ where $x = \log{n}$. Let's try to calculate some first values of $f$:$f(1) = 0$ $f(2) = 1$ $f(3) = 3$ $f(4) = 7$ $f(5) = 15$Now we can notice that $f(x) = 2^{x-1} - 1$. Let's prove this by induction. This formula obviosly holds for $x = 1$, so let's prove the formula if we know that it holds for $f(1), f(2), ..., f(x - 1)$.$f(x) = x - 1 + f(x-1) + ... + f(1) = x - 1 + 2^{x-2} - 1 + ... + 2^0 - 1 = x - 1 + 2^{x-1} - 1 - (x - 1) = 2^{x-1} - 1$. So it is $n / 2 - 1$. Then we have $n / 2$ players left and for them it will be $n / 4 - 1$ and so on.
 » prob -- infinite fence can anybody explain why are we taking GCD of r and b.. like can you explain me with an example where i will get an wrong answer if i did not take the gcd..
•  » » same i am also not getting and nobody is willing to answer
•  » » » In case you still need helphttps://codeforces.com/blog/entry/71755?#comment-560847
 » 4 months ago, # | ← Rev. 2 →   I am not able to spot the mistake in my code 84677601 for D. Can someone give me a small testcase on which it fails.
 » Can someone explain how to apply binary search in problem B. I came to this question by seeing the binary tag but here's no sign of that. Someone please explain it by binary search.
 » Somebody please help me with F question ... I have done centroid decomposition and its giving TLE and the complexity if nlog2n in that case which seems correct .. https://codeforces.com/contest/1260/submission/92880641