### KAN's blog

By KAN, 18 months ago, translation, 1119A - Ilya and a Colorful Walk

Author, preparation: 300iq.

Editorial

1119B - Alyona and a Narrow Fridge

Author, preparation: KAN.

Editorial with bonuses

Aleks5d invites you to compete in the shortest solution challenge for this problem. His code (155 bytes):

Code
Authors during the contest

1119C - Ramesses and Corner Inversion

Author, preparation: 300iq.

Editorial

1119D - Frets On Fire

Author, preparation: cyand1317.

Editorial
Code

1119E - Pavel and Triangles

Author: gen, preparation: 300iq.

Editorial

1119F - Niyaz and Small Degrees

Author, preparation: 300iq.

Editorial

1119G - Get Ready for the Battle

Authors: Aleks5d, KAN; preparation: Aleks5d.

Editorial

1119H - Triple

Author, preparation: RDDCCD.

Editorial Tutorial of Codeforces Global Round 2  Comments (95)
 » Problem F: AC 4Problem G: AC 7Problem H: AC 5...
 » Thanks for the fast editorial!
 » Passed G with the following solution.Increase $hp_1$ such that $n$ is divisor of $\sum hp_i$. $m$ times choose greedily maximum group size such that it's possible to attack with this group without affecting the answer and then simulate this attacks randomly.Any idea why this solution works?
•  » »
 » It seems that someone is curious about what I've done on problem A. Let me describe what has happened.Contest starts ---> Open problem A ---> A little difficult? ---> I can solve it by binary search in O(nlogn) !===== One hour later =====Oh my god!!!
•  » » This look like funny What is your rank？I want to see your submission history
•  » » » You can get into his homepage and click the points on the rating graph. One point stands for one contest. Clicking one will lead you to his rank in that contest.
•  » » » » Finally i find it ，thank you
 » How to solve B in O(nlogn) or O(nlog^2 n)?
•  » » For $O(n\log^2 n)$, we can binary search the answer. For $O(n\log n)$...maybe some interesing sortings? (Radix sort?)
•  » » » I think, binary search gives $O(n \log n)$. Because $\sum^n i 2^i = O(n 2^n)$.
•  » » 18 months ago, # ^ | ← Rev. 2 →   You only need to sort the array once if you also keep the original indices of each bottle. Then binary search the answer.
•  » » » With binary search reducing the number of sorts does not seam to give advantage complexity-wise. It is $O(n \log n)$ regardless.
•  » » binary search + sort -> solved in O(n log^2 n)sort in decreasing order and record the position of each value , then do binary search -> solved in O(n log n)
•  » » » p_b_p_b Could you post the solution for O(n log n) approach to problem B?
•  » » Can you please explain I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct? Similarly in example 1 — suppose there are 2 shelves one shelf has a bottle of size 5 and 4-second shelf has a bottle of size 1 and 2 therefore answer would be 4?
•  » » » You cannot pick arbitrary bottles from the input. You need to pick k bottles from the beginning of the line. Therefore in example 1: "2 3 5" is ok, but "2 3 5 4" is too much, so the answer is 3. In example 2: "9 1 1 1" is ok, but "9 1 1 1 1" is too much, so the answer is 4.
•  » » » » Then why we are sorting in decreasing order...as written in editorial... sorting leads to derrangement of elements..from it's initial position..... please answer because i have literally spend 1 hour on thinking this only..
•  » » » » » The problem statement says at the end that you need to look for the largest k: "Alyona is interested in the largest integer k".The editorial says "just try all possible k".Therefore you need to consider the following cases separately (independent of each other): k=1 — you need to check if the first bottle fits k=2 — you need to check if the first 2 bottles fit k=3 — you need to check if the first 3 bottles fit etc.When you are checking for example k=3, take the first 3 bottles (from the input array that was not sorted yet), sort them, check if they fit in the fridge.When you are checking k=7 forget that you have sorted the 3 bottles for k=3 — start again from scratch: take the first 7 bottles (from the input array that was not sorted yet), sort them and check if they fit in the fridge.Does it make sense now?
•  » » » » » » yes..finally i understand..thanks for helping..
•  » » would anyone post O(nlogn) solution for me please?
•  » » »
•  » » we can use set instead of vector(or array) to solve in O(nlogn) as when we are inserting the elements they are inserted in a sorted manner and we continuosly subtract the height of the bottles ....when the result becomes negative we can just print the answer
•  » » » can u share your code with the following solution
 » I did problem B in 125 bytes (including an LF) in Ruby. I tried to squeeze author's Python solution and it became 125 bytes as well. So to me seems like a notorious coincidence. Ruby(n,k),a=\$<.map{|s|s.split.map &:to_i};p (1...n).find{|i|k
•  » » 18 months ago, # ^ | ← Rev. 2 →   I can do like this. It's 109 bytes Pythonf=lambda:map(int,input().split());n,k=f();a=[*f()] while(n>0)&(sum(sorted(a[:n])[-1::-2])>k):n-=1 print(n) 
•  » » » Ok. Now it's 102 bytes. Pythonf=lambda:map(int,input().split());n,k=f();a=[*f()] while sum(sorted(a[:n])[-1::-2])>k:n-=1 print(n) 
•  » » » » By my count your solution is 99 bytes. Do you count 2 characters for newlines?Also, you can remove 3 additional bytes, giving 96 bytes: PythonSubmission: 52431059 f=lambda:map(int,input().split());n,k=f();a=*f(), while sum(sorted(a[:n])[::-2])>k:n-=1 print(n) 
•  » » » » » Oh nice! Guess I was too obsessed with functional programming when doing code golf.
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   By using exec, we can achieve a significant 3 bytes improvement!make it only 93 bytes :) Python52473099 exec('n,k,*a='+'*map(int,input().split()),'*2) while sum(sorted(a[:n])[::-2])>k:n-=1 print(n) 
 » 18 months ago, # | ← Rev. 2 →   Why this is correct for C — If number of cells where A and B doesn't match in every row and column is even then answer is 'Yes' else it's 'No'?
•  » » The tutorial says that if the parity in each row and column remains the same, then the answer is yes. We can see that for every position where A and B doesn't match, we try to change it. If we change an even amount of positions in each row and column, then the parity in each row and column remains the same.
 » Can someone explain the proof of problem C?
•  » » 18 months ago, # ^ | ← Rev. 2 →   tutorial means we always choose to operate (1,1,x,y) , every two element in one column can be change in one turn, because one column has (0 or 2 or 4 or 6 or num in odd),one column can be obviously set to the goal via some operations.imagine we have done every column except the first column,because for the sake of setting other column to the goal, and each row also has(0 or 2 or 4...) difference,the element in the first column also must be changed (0 or 2 or 4...)times, whether there exist difference in the first column doesn't change the result , if there exist difference in the first column, it just changed(2-1,4-1,6-1..)times.
•  » » » Thanks for the effort!
 » 18 months ago, # | ← Rev. 2 →   Simple DP solution for E: 52420096
•  » » lol that is not dp
•  » » » why?
•  » » » » he is just running the greedy algo, right?
•  » » » » » Yes. But why greedy algo != dp? Task tags contains dp and greedy algo.
•  » » Can you explain solution? please
•  » » » 18 months ago, # ^ | ← Rev. 3 →   dp[i] means what is the answer for a,a...,a[i] sticks.using this dp we can calculate remaining sticks that we didn't use themin any triangle before. for update dp[i] we have dp[i-1] triangle beforeplus with any 2 sticks of a[i] and any stick of j (j < i) that we didn't usethat in any triangle before we can make a new triangle. after it if remaining sticksfrom a to a[i — 1] over, we can use 3 remaining sticks of a[i] and make a new triangle.sorry for bad English .
•  » » » » Это нормально, я тоже не очень хорошо знаю англ. Спасибо за обьяснение.
•  » » » » » Пожалуйста :)
 » IN problem B I was using the greedy approach. My logic:: I was adding all the numbers from 0 to n till the value of h is greater than the current element if not I check for the smallest number taken before this number with which the current element can be paired.can anyone tell me where my logic is getting wrong? Link to my solution : https://codeforces.com/contest/1119/submission/52409993
 » 18 months ago, # | ← Rev. 3 →   I have slightly different approach on problem E. Don't know why it is true but it passed the systests. If the number of ones in the initial array is 0 then the answer is $sum of all elements / 3$(somehow we can take almost everything). If there are ones then we should compute the minimum possible amount of unused ones. Go from the end to the begginng of the array storing current amount of tiles we can use with the ones. If current $a_i$ is even the we increase this amount by $a_i / 2$, otherwise, we take one triangle from three tiles of this type and take the rest increasing amount by $(a_i - 3)/2$. Then the answer if $((sum of all elements) - (minimum number of unused ones)) / 3$.Here's my code : 52409622
 » Here's a 112 byte solution to B: 52424010
 » 18 months ago, # | ← Rev. 2 →   The editorial for problem H is little unclear.
•  » » I try to explain from another aspect. Take the polynomial ring $Z[a, b, c, d]$. For the individual $i$, let $F_i$ be the vector of length $2^k$ where $F_i = a$, $F_i[b_i] = b$, $F_i[c_i] = c$, $F_i[b_i \oplus c_i] = d$. We can verify $\mathrm{FWT}(F_i)$ contains only $4$ elements $(a+b+c+d)$, $(a+b-c-d)$, $(a-b+c-d)$, $(a-b-c+d)$ in the specified ring. Suppose that we have $x$, $y$, $z$, $w$ copies of each elements for $\mathrm{FWT}(F_i)[k]$. Since FWT is a linear transformation, $\mathrm{FWT}(\sum_{i} F_i)[k] = (x+y+z+w) a + (x+y-z-w) b + (x-y+z-w) c + (x-y-z+w) d$. Thus, we can obtain the value of $x$, $y$, $z$ and $w$ from $\mathrm{FWT}(\sum_{i} F_i)$ directly.
 » I think editorial proof for problem G is wrong. It states "This way the first $i$ groups will have size $k_i$", but that would require the first group to atack every enemy in different steps, which is impossible if the final answer is less than $m$.I submitted a solution (52431440) that greedily chooses the biggest possible size for a group that doesn't waste soldiers in any atack (after incrementing the first enemy group health so that total enemy health is a multiple of $n$). It passes system tests, but I couldn't come up with a proof of its correctness yet.
•  » » Well, I think editorial proof can be fixed this way:Instead of considering $k_1, k_2, ..., k_{m-1}$, we should split them in $k_{1,1}, k_{1,2}, ..., k_{1, r_1}$ and $k_{2,1}, k_{2,2}, ..., k_{2, r_2}$ and so on $k_{z,1}, k_{z,2}, ..., k_{z, r_z}$, where for each $i$, numbers $k_{i,1}, ..., k_{i, r_i}$ are remaining health points in consecutive enemy groups that are attacked without using all $n$ soldiers in between. So, we have $k_{i,1} + ... + k_{i, j} < n$ for every $j <= r_i$ and now we can proceed with the same idea of the editorial taking numbers: $k_{1,1},\quad k_{1,1} + k_{1,2},\ ...\ ,\quad k_{1,1} + ... + k_{1,r_1}$ $...$ $k_{z,1},\quad k_{z,1} + k_{z,2},\ ...\ ,\quad k_{z,1} + ... + k_{z,r_z}$
•  » » And here is a counterexample for my solution: 12 2 15 21 It seems tests weren't strong enough as one of the 7 AC solutions for G fails this test.
•  » » So I think G is not a good problem.Lots of wrong lemmas of this problem are 'seems corrected and hard to hack'.We need a convincing lemma and natural proof.
•  » » Of course we meant $k_i$ after sorting, this will be clarified soon.
•  » » » 18 months ago, # ^ | ← Rev. 4 →   Maybe I wasn't clear. It has nothing to do with sorting, but with the restrictions imposed in the construction of the solution.As stated in the editorial, these ' $m-1$ assumptions of type "some of our groups have total size $k_i$" ' should instead be $z$ assumptions (for each $i$ between $1$ and $z$, considering the same notation of my previous comment) of type:"Some of our groups have total size $k_{i,1}$, some of our groups have total size $k_{i,2}$, ... , some of our groups have total size $k_{i,r_i}$, and all these $r_i$ sets of groups should be pairwise disjoint."Then we can take the partial sums of the $k_{i,j}$ 's as in my previous comment, sort everything and get the distribution like in the editorial.Anyway, nice problem, I really enjoyed it! :-)
•  » » » » Ok, you're right that there are cases when more than one group of enemy soldiers are destroyed on the same step; then we should modify the assumptions to yours or just directly replace the subsets of groups with prefixes.I intentionally didn't dive into these details in the editorial because they can hide the main idea on one hand and because these cases are easy to cover once you get the main idea on the other hand. Probably I should mention them after the solution, though.
 » For the problem D .I just dont udersand why any integer that appers int row i also appers in row i+1.
 » Why when i choose Solution(Rus) it shows Solution(Eng)
 » Still can't understand the C solution/proof !and what's the meaning of the "parity of the matrix" ?
•  » » 18 months ago, # ^ | ← Rev. 2 →   it means no. of 1's in matrix is even or odd like in this 01110 it is odd parity because number of 1's are 3.
•  » » » Is it a known concept or just coined for this problem?
•  » » » » it's a known concept
•  » » » » » So how do we define the parity of a matrix?
•  » » » » » » count the number of 1's in matrix if it is odd then it's odd parity otherwise even
 » Why can't the editorial be made easier to understand? Look at the number of people solving problems F,G and H, its hardly 20 people.
 » I have a doubt in Problem B. Example 2 Can anybody please explain? If there an arbitrary number of shelves then in example 2 then we can install 9 shelves and thus I will be to keep all 9 bottles of height 1 unit but not the bottle of 9 units. Then our answer will be 9...Isn't it correct?
•  » » You have to install the first k bottles, so you have to install the first bottle (the one with height 9) and, if you install it, you cannot install more than 4 bottles.
 » I think the explianation of the problem D has someting wrong. Notice that " any integer that appears in row i also appears in row i+1." has ambiguity,because "any integer" euqal to "all integer".Maybe it can be changed into "some integer".Do you think that it is right????????????????????
 » lovely contest <3
 » From problem D code, I am unable to understand the purpose of "t" array and how is it helping in calculate the result. Can anyone please help me in understanding the code or suggest a simpler solution?
•  » » If you understand everything upto the use of the array t in the tutorial's code, then this submission may help you.What I did is that I kept the highest possible unique contribution of the rows (except the last row, it can contribute upto the entire length), sorted them (same as the tutorial). Then, for a specific query of length = r-l+1 (say), all I needed was the total contribution. And that is (the summation of all the contributions that were $\leq$ length) + (rest of the elements in the "contributions" array and the last additional row will only contribute length amount). Binary search on the contributions array (basically std::upper) and cumulative sum upto that position will give you the first term. I hope this helps. And I am also trying to figure out what the array t does in the tutorial. :(
•  » » » Your solution was much easier to understand and was very helpful. Thanks.
•  » » » » I'm glad I could help.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   i am unable to understand how did u found out the contribution of each elelment in range . Please help me understand. cout << summ[ind]+(sz-1-ind)*cov+cov summ[ind]= (max diffrence of s[ind]-s among all rows) +(sz-1-ind)*cov . WHY?? +cov. WHY add cov at last??
•  » » » » By finding the differences of the elements (you need to sort them first) given in the problem.
•  » » » » » i edited please look
•  » » » » » » for the last element which can contribute the entire length no matter what. ( cov means length in my code, just saying in case it confused you.)
 » quick question about C i just wrote a python code for make A to B but it doesn't work like i thought. def op(grid, sy, sx, ey, ex): grid[sy][sx] = 1-grid[sy][sx] grid[ey][ex] = 1-grid[ey][ex] grid[sy][ex] = 1-grid[sy][ex] grid[ey][sx] = 1-grid[ey][sx] n, m = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(n)] B = [list(map(int, input().split())) for _ in range(n)] while A!=B: for y in range(1, n): for x in range(1, m): if A != B or A[y][x] != B[y][x] or A[y] != B[y] or B[x] != A[x]: op(A, 0, 0, y, x) 
 » Here's a simple (?) general approach of solving H for $m$-tuples (instead of triples) in $O(n2^m + (m + k)2^{m + k})$. As explained above it suffices to solve the following problem: consider a set $t_1, \ldots, t_n$ of $m$-tuples of $k$-bit numbers. For a $k$-bit number $x$, say that the mask $y$ induced by $x$ for a tuple $t_i$ consists of all indices $j \in {0, \ldots, m - 1}$ such that $x$ and $t_{i, j}$ have an odd number of common bits. For each $k$-bit number $x$ and each mask $y$ of size $m$, we have to find how many tuples have mask $y$ induced by $x$.Recall that multiplication of monomials in $\mathbb{Z}[x_0, \ldots, x_{k - 1}]$ with relations $x_i^2 = 1$ behaves the same way as xoring $k$-bit numbers. Further, WHT of an array $A = (a_0, \ldots, a_{2^k - 1})$ is the same as $k$-dimensional Fourier-transform of $P_A(x_0, \ldots, x_{k - 1}) = \sum_{i = 0}^{2^k - 1}a_i X(i)$, where $X(i)$ is the product of $x_j$ such that $j$-th bit is set in $i$. In simpler terms, we substitute all combinations $1$'s and $-1$'s into $P_A(\ldots)$ to obtain $2^k$ numbers; for the $j$-th number, the value of $x_i$ is $1$ if the $i$-th bit in $j$ is $0$, and $-1$ otherwise. Finally, recall that WHT is linear, and WHT of a product of two functions is the element-wise product of their WHT's (since WHT is basically FFT).Consider a set of $k + m$ variables $x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}$. For a tuple $t_i = (t_{i, 0}, \ldots, t_{i, m - 1})$, consider a polynomial $Q_t(x_0, \ldots, x_{k - 1}, y_0, \ldots, y_{m - 1}) = \prod_{j = 0}^{m - 1}(1 + X(t_{i, j})y_j)$. What are the values of WHT of $Q_t$? Let's say that values of $x_i$ correspond to $k$ bits of a number $x$, and $y_j$ determine whether each index $j$ is included into the mask $y$. Then, one can observe that $1 + X(t_{i, j})y_j$ is equal to $2$ when $y_j$ matches the parity of the number of common bits of $x$ and $t_{i, j}$ (that is, $j$ is in the mask induced by $x$). Consequently, $Q(t)$ is equal to $2^m$ when $y$ is induced by $x$, and $0$ otherwise. By linearity, the WHT of $\sum_{i = 1}^n Q_{t_i}$ contains the exact values we wanted to obtain (after division by $2^m$).
•  » » is this algorithmic round or International maths olympiad !
•  » » » If there weren't problems as hard as these then people like Endagorion and tourist would finish all the problems in under 30 minutes, and where's the fun in that ?
•  » » » » first increase ur rating then give knowledge to otheres .
•  » » » » » My rating is low because I spend more time watching other people code than actually learning how to code.
•  » » » » » » then stop looking other's code , try on ur own ,
•  » » » » » » » Thanks, all my problems fixed.
•  » » » » » » » » good , now u should reach the level of petr mitrichev .
 » 18 months ago, # | ← Rev. 2 →   would you translate following line into more easier english please? i trying to understand this line for like 30hours... but i cannot understand... 'the line starts from anoter perspective...'  Now come the queries. Given a fixed value of w, we need to quickly compute (∑n=1i=1min{di,w})+w. From another perspective, this equals the sum of value times the number of occurrences, namely (∑wk=0k⋅count(k))+(∑∞k=w+1w⋅count(k))+w, where count(k) denotes the number of times that integer k occurs in d1…n−1.
 » 17 months ago, # | ← Rev. 2 →   why did the contest problem's rating not show in the problemset
 » Problem H. How do I prove $x-y-z+w=p$?
•  » » I got it. Just needed to verify that every element after WHT looks like that. Basically, to prove that one needs to know that WHT is matrix-vector multiplication with matrix element $(i, j)$ being equal to $(-1)^{ij}$. After that, it is straightforward to show that $d$ is positive when $b, c$ have equal sign and negative otherwise ($(-1)^{ij}$ and $(-1)^{ik}$ have different signs if $j, k$ have different parity and then $(-1)^{i(j \oplus k)}$ is negative).
 » How to apply FFT in 1119E - Павел и треугольники ? I saw FFT tag in this problem
 » Another approach for C: Note that the problem can be restricted to only needing to perform the operation on a $2 \times 2$ submatrix, as any instance of the operation on bigger submatrices can be reduced to some number of the $2 \times 2$ operations. Proof: if we denote performing the operation on a $2 \times 2$ submatrix by the coordinates of its top left cell, performing all operations $(i, j)$ where $i \in [x, x+n-1)$ and $j \in [y, y+m-1)$ is equivalent to performing a single operation on submatrix of size $n \times m$ with top-left corner $(x, y)$.With the problem thus reduced, an easy greedy solution emerges: Compare every position in the two grids in reading order. When encountering any position where $A$ and $B$ differ, perform the operation on $A$ with top-left corner at that position. If that's not possible because the position is on the last column or row, the answer is No.
 » 5 months ago, # | ← Rev. 2 →   In problem ELet's take 3 numbers i, j, k such that i < j < k.Then why taking (i, k, k) and (j, j, j) is giving WA but taking (i, j, j) and (j, k, k) don't? 300iq
 » 4 months ago, # | ← Rev. 2 →   I believe 1119B — Alyona and a Narrow Fridge is wrong. For example for the input 8 18  1 2 3 4 5 6 7 8 The correct answer would be 8. But with your code/technique it will be 7.