### PikMike's blog

By PikMike, history, 12 days 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 (52)
 » 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 days 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 days 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?
 » 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 days 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.
 » 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.
•  » » 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.
•  » » 10 days 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 !!
 » ＂ 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 ?
 » 10 days 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.
 » 9 days 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.
 » 9 days 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 ?
•  » » 9 days 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 ?
 » 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;
`

}