### kostka's blog

By kostka, 12 months ago,

You've got only one more chance to participate in Google Kick Start 2019, so don't miss it!

Round H will start this Sunday (November 17) at 05:00 UTC and will last 3 hours.

Get ready and register now at g.co/kickstart.

.

• +51

 » 12 months ago, # |   +21 The contest starts in just 10 hours!
•  » » 12 months ago, # ^ |   +8 Editorials are available (click on the problem statement and click on the analysis tab).
 » 12 months ago, # |   +6 Maybe this was already asked, but where can I see test cases? No idea where my solutions go wrong
 » 12 months ago, # |   +13 How to solve 3rd problem-elevanagram?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +11 i just made the constraints smaller i.e. if ai>20 make ai=20 or 21 depending on ai-20 is even or odd respectively. rest is just digit dp
•  » » » 12 months ago, # ^ | ← Rev. 3 →   +2 I too solved it the same way. Now the question boils down to finding if the array elements can be divided into two subsets whose size is either equal(if total elements are even) or differ by 1(if total elements are odd) and their difference is divisble by 11.(Here array is formed by appending a digit as many times as it's frequency in input).
•  » » » 12 months ago, # ^ |   0 why we need to reduce a[i] and how it is always correct.
•  » » » » 12 months ago, # ^ |   +8 "Why" is clear. We can't do a dp on 10^9. I am not very sure but the proof of correctness relates to this case:11..111 21 times leads to divisibility by 11.Other occurrences of 1 can simply be reduced as two 1s can be put at places of different parity.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 Please elaborate.Not able to figure out the logic of writing down 22!
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 ankit_btech actually 111..11 22 times is divisible by 11. so what you mean is, suppose we have 30 one's. so we can make it 20 and use 10 ones of + and — parity each which will cancel out. and suppose we have 31 one's, we replace it by 21 and use 10 ones of + and — parity each to cancel out each other. this way we reduced larger test data to smaller one, and do the same just what we did for test set 1. Am i right.
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   +3 Let's say we put digits which will be added on the left side, and the ones which will be subtracted on the right side. Now, for any i in [1, 9], given a[i] is greater than or equal to 20, we generate a list sums using i only.By placing some i's on the (+)left side and others on the (-)right side. For example i = 2, and a[i] = 3. Sums list will be as follows: | 2 2 2 -> -2 -2 -2 = -6 2 | 2 2 -> +2 -2 -2 = -2 2 2 | 2 -> +2 +2 -2 = +2 2 2 2 | 0 -> +2 +2 +2 = +6 Now, if a[i] >= 20, then for each j in [0, 10] there will exist a value in sums such that value%11 == j. And, [0, 10] is nothing but range of (any number)%11.Let's take an example where i = 1, and a[i] = 20.Sums will be: [0, 2, 4, 8, 10, 12, 14, 16, 18, 20]Sums%11: [0, 2, 4, 8, 10, 1, 3, 5, 7, 9], which basically covers all numbers in range [0, 10].And, since we only care about sums modulo 11, we therefore have covered all the possible sums. Hence we can reduce a[i] to 20 or 21 on the basis of their parity
•  » » » » » 12 months ago, # ^ |   0 Thanks a lot, very well explained. :)
•  » » » » » 12 months ago, # ^ |   0 What if i equals 11 and assume ai as 20? then sum % 11 will be always 0.
•  » » » » » » 12 months ago, # ^ |   +3 i ranges from [1, 9], and 11 is not a digit
•  » » » 12 months ago, # ^ |   0 How will this always be correct, it there any property or some observation I missed out on?
•  » » » 12 months ago, # ^ |   0 Can anyone please give a proof why it is correct (taking modulo with 22). Thank You
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 you can simply use this, no need to take mod, i submitted it. now the problem reduce to test set 1  if(a[i] >= 22){ if(a[i] % 2 == 0){ a[i] = 20 ; } else a[i] = 21; } 
•  » » 12 months ago, # ^ |   +8 The intended solution should be DP, but I get it passed by randomly generating numbers and check whether it is divisible... (The order doesn't matter so I only generate the frequency of each number in odd/even positions)Anyone wants to hack?
•  » » » 12 months ago, # ^ |   +5 How you generated them randomly?
 » 12 months ago, # |   +14 How to solve the 2nd Problem fully?
•  » » 12 months ago, # ^ |   +11 Create a graph where each node is a diagonal. See the problem as coloring the nodes with black and white (Black means we are using the diagonal. White means not using.) Then we want the graph to have a minimum number of black nodes.Suppose we have a grid that is black, and it can be changed by two diagonals $A$ and $B$. Then in the final coloring $A$ and $B$ should be in the same color. If the grid is white, then $A$ and $B$ should be in different color. Then we can do something similar to bipartite graph checking to color the graph, and take the minimum of two colors in each connected component.
•  » » » 12 months ago, # ^ |   0 Can you please explain the bipartite check part a little more?
•  » » » » 12 months ago, # ^ |   +3 I guess my code can explain it better than myself: code
•  » » » » » 12 months ago, # ^ |   0 In line 31 of your code can you explain the formula you used..... int u = i + j, v = 2 * n — 1 + (i + (n — 1) — j);
•  » » 12 months ago, # ^ |   0 although I didn't solve it, I think below solution is right. since till the end I found the bug that doesn't separate odd/even two part.first separate graph into odd/even diag-part, i.e. (i+j)&1?note for one graph, there are exactly two ways to flip, since once some diag decided, can deduce others. so you can use dfs or two_sat to get the cnt(=how many diags choosen to flip), then result = min(cnt, N-cnt). where N=#diags of that part graph.final result is sum of two part.
•  » » 12 months ago, # ^ |   0 I just brute forced for diagonals of the same length (starting with the longest) with bitmasks and then recursed. There is always some field that is not touched by smaller length diagonals, so one can prune some states early.
•  » » 12 months ago, # ^ |   0 I did it like this: brute-force whether to "flip" values at 2 upper-left "/-diagonals": 1st diagonal is (0,0), 2nd diagonal is (1,0) and (0,1) (there will be 2*2==4 choices). Depending on cell (0,0), flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal) Depending on cell (1,0), flip "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal). Depending on other cells (not (0,0) or (1,0)) cells, flip "/-diagonal" that contains (i, i) or (i+1, i). Depending on values in (2, 0), (3, 0), ... (N-1, 0), flip "\-diagonals" that contain (i+2, 0) (below 1-below main diagonals) Depending on values in (0, 1), (0, 2), ..., flip "\-diagonals" that contain (0, i+1) (above main diagonals) Check that you have all '#'s, update result Overall complexity: $O(4\times N^2) = O(N^2)$ However, I've seen other simpler solution: brute-force whether to flip "\-diagonal" (0,0), (1,1), ... , (N-1, N-1) (main diagonal) and "\-diagonal" (1,0), (2,1), ... , (N-1, N-2) (1-below main diagonal) (still 2*2 == 4 choices) Depending on value in cell (i, i) or (i+1, i), flip "/-diagonal" that contains this cell Either flip or don't flip all other "\-diagonals" (just like steps 4., 5. in previous solution). Check that you have all '#'s, update result. Complexity: still $O(N^2)$
 » 12 months ago, # | ← Rev. 2 →   +6 why 3rd was easier than 2nd. 2nd was quite hard. it should be 3rd. wated a lot of time. tried with queue but it gave MLE.
•  » » 12 months ago, # ^ |   0 i used masking for one direction diagonal and after applying operations in one direction,check for other direction diagonal whether it is possible to do operations to make grid complete black.As for one diagonal we can do operations either 0 or 1 time that's why masking
 » 12 months ago, # | ← Rev. 3 →   +16 When will they enable submit button for practice?Edit : It's working now.
•  » » 12 months ago, # ^ | ← Rev. 2 →   -22 Soon
 » 12 months ago, # | ← Rev. 2 →   0 In the second problem by reducing the frequency of digit how we are making sure that the number of terms going to even side and the odd side are the same or (odd — 1 == even)?
 » 12 months ago, # | ← Rev. 3 →   +3 The Analysis of Problem 2 (Diagonal Puzzle) says the following: One interesting observation is that if we decide whether we would flip the two largest diagonals or not, we can pick all other diagonals to flip deterministically. There are four choices for flipping/not flipping the largest two diagonals. And for each of these choices, we can go through all other diagonals in the grid. For each of these other diagonals, we can check if the cell where it intersected with one of the largest diagonals is white. If it's white, we need to flip this diagonal, otherwise not. For each of those four combinations of the largest diagonal flips, if after all the flips(both largest two diagonals and others), the final state has all black cells, then we have a possible answer, otherwise not. We take the minimum flips of the four possible choices. I am assuming that the two longest diagonals are Major and Minor. So, there will be diagonals which won't intersect with both major and minor diagonals at a particular cell. For example take the following grid: 3 .*. *.. ... Here, the diagonal in *[(0, 1), (1, 0)], neither intersects with the major diagonal or the minor diagonal, at a particular cell. Although, it does intersect with the major diagonal but not at a particular cell.And, the analysis clearly mentions, the following:  For each of these other diagonals, we can check if the cell where it intersected with one of the largest diagonals is white  But, it is clear from the above example, that there will be some diagonals which won't have a common cell of intersection.Therefore, I am not sure as to how will the above approach work.