### Lewin's blog

By Lewin, history, 9 months ago, ,

Here's the tutorial. Code can be found in this link (more will be added there soon): https://www.dropbox.com/sh/xwxn3zrl1icp3i2/AACtYSdYH0KlTEdVgCFFgPrYa?dl=0

Zoning Restrictions Again
Double Matrix
Hide and Seek
Thanos Nim
Palindrome XOR
Rainbow Coins
Zigzag Game

• +117

 » 9 months ago, # |   +9 Peace on you :) Thanks a lot for this Amazing contest ever at least for me :)
 » 9 months ago, # |   +71 E was cool, D was very easy (IMO).
•  » » 8 months ago, # ^ |   -16 what u think about hide and seek problem??was it easy for you??
•  » » » 8 months ago, # ^ |   +5 Man see his rating carefully. And then that of the question. You will get your answer.
•  » » » » 8 months ago, # ^ |   +4 How to code like them bro...I try a lot but still every time new question of dp and trees comes i cant think of any solution...
•  » » » » » 8 months ago, # ^ |   +11 Practice, practice, practice...
 » 9 months ago, # | ← Rev. 2 →   0 Nice Proof of Greedy Solution of B , how to solve B using dp (just for curiosity)
•  » » 9 months ago, # ^ |   0 My solution of B used DP: https://codeforces.com/contest/1162/submission/53752942
•  » » » 9 months ago, # ^ |   0 can you explain the recurrence relation
•  » » » » 9 months ago, # ^ |   0 We track partial solutions f[i][j] and g[i][j]. f[i][j] = true iff the solution exists and last elements (in position i and j) in both matrices ARE NOT swapped. g[i][j] = true iff the solution exists and last elements (in position i and j) in both matrices ARE swapped.How to calculate f[i][j] and g[i][j]? f[i][j] = true in a few cases: - f[i][j] may be based on f[i-1][j] and this means that a[i][j] > a[i-1][j] and b[i][j]>b[i-1][j] because we didn't swap elements in position i-1 and j. - f[i][j] may be based on g[i-1][j] and this means that a[i][j] > b[i-1][j] and b[i][j]>a[i-1][j] because we swapped elements in position i-1 and j (because we suppose g[i-1][j]). At least one of these conditions should hold, and we did a row check.The same two conditions for a column check: i and j-1 positions of elements.The same conditions should hold for g[i][j]: just swap a[i][j] and b[i][j] in conditions.Finally, f[n-1][m-1] or g[n-1][m-1] should be true for "Possible" answer.Please, let me know if you have any questions.
•  » » » » » 8 months ago, # ^ |   0 https://codeforces.com/problemset/submission/1162/54663882 can someone explain what i am doing wrong. i created 2 new arrays c and d. in c i place the min(a,b) provided it satisfies the increasing condition else i place the other one if it satisfies the increasing condition else the loop breaks. in short i have tried to make c by selecting the value given by above approach and placed the unselected value in d. at last i checked if d is increasing or not. It is showing error at 7th test case. Pls let me know if there is something wrong with the approch or the code.
•  » » » 8 months ago, # ^ |   0 Hello, can you tell me why normal checking and swapping i.e suppose a[i][j] >= a[i][j+1] then swap(a[i][j],b[i][j]) is not working ? or if a[i][j]>=a[i+1][j] then swap(a[i][j],b[i][j]) and then doing the same with matrix b? Code
•  » » 8 months ago, # ^ |   0 My solution by using DP: https://codeforces.com/contest/1162/submission/53754575
 » 9 months ago, # |   +19 The problems of this contest was good. :)
 » 9 months ago, # |   +19 Sadly I didnt do my best at this contest, but the problems were really good!
 » 9 months ago, # |   +21 My solution for E only used 4 queries.https://codeforces.com/contest/1161/submission/53759655
•  » » 9 months ago, # ^ |   +15 Interesting. 4 is also optimal for $n$ large enough, since 3 is impossible when $2^{1.5n} < 3^n/6$.
 » 9 months ago, # |   0 Can anyone help me with the B. If aij<=bij how does it ensure that there will always be a correct solution. Suppose aij<=bij and aij+1<=bij+1 but aij>aij+1 and bij>bij+1. Then even if the configuration is valid there can't be any solution.I couldn't understand it. Please help me with it.
•  » » 8 months ago, # ^ |   0 The configuration a[i][j]>a[i][j+1] and/or b[i][j]>b[i][j+1] is not valid. Therefore the existence of such a configuration would mean that there is no solution as per the proof which is given above. So output=>"Impossible"Basically, after all the swapping is done(i.e. a[i][j]<=b[i][j] for all i,j) and we still have any configuration with either a[i][j]>=a[i][j+1] or b[i][j]>=b[i][j+1], we can be sure that there is no possible solution.
 » 9 months ago, # |   +33 Great contest (Y)Wondering how everybody answered Thanos nim. Had a hard time figuring what was the insight for the game :)
•  » » 9 months ago, # ^ |   +13 I wrote a brute force for $n = 6$ and $0 \leq a_i \leq 5$ and outputted the positions where Bob wins. From those positions the solution is obvious.
 » 9 months ago, # | ← Rev. 3 →   +53 Lol, no test in div1b had n = 83160 or something close to a highly composite number. My code takes like 8 seconds on n = 83160, m = 200000 and random values of segments (this generator). The highest number of divisors seems to be 48 on 51450 when it could've been 128 on 83160.Maybe such a test could be added to a testset?
•  » » 9 months ago, # ^ |   +18 Maybe it didn't affect anybody but tests for 1161D - Палиндромный XOR seem weak too. Judging from prefixes of tests, all big tests are just random characters ?01. Maybe there is some smart pattern in some, but I don't see any test e.g. with just characters 1 or just ?`.
•  » » 8 months ago, # ^ |   +8 Thanks! arsijo added it to the tests yesterday. It's my bad T-T
•  » » » 8 months ago, # ^ |   0 Great, thanks!
 » 9 months ago, # |   +15 I didn't fully understand why in Div. 1 — B we can simply check for the divisors of n. Could someone try to explain it a bit better or with an example ?
•  » » 9 months ago, # ^ | ← Rev. 2 →   +7 Let's suppose that image is rotationally symmetrical and image consist of p identical blocks. Then every block has length of n/p. Then if we rotate image by n/p units, the new image will be the same as the original one. Now we can brute force the value p among the divisors of n and check if the rotation i + n/p is correct.
•  » » 8 months ago, # ^ | ← Rev. 3 →   +7 Let a segment be [a,b] when we rotate it by k it gets [a+k, b+k] to be symmetrical there should be a segment [a+k, b+k] which after rotating will move to [a+2k, b+2k] or we can say that all possible values can be [(a+xk)%n, (b+xk)%n].r = (a+xk)%n = a+xk-qnxk — qn = r — aUse bezout identity euqation has solution if r-a is c*gcd(k,n) or r = a+c*gcd(n,k).
 » 9 months ago, # |   +3 I recieved a system message that the solution of my first question Div2A Zoning Restrictions significantly matches with that of someone named MetaFish, but I even don't know the person and didn't use Ideone like things by which code can be shared. It may be just a pure coincidence as doing first question there are huge chances of matching the code, so I want to clarify this as it was written in message to comment on the post that I did code on my pc and then using browse submitted it.
 » 9 months ago, # |   +13 Actually KMP can solve D by regarding the original and rotated images as two strings and match them together. Time complexity can reach O(m) (use the correct way of vector comparison).
•  » » 8 months ago, # ^ |   0 Can you help me in a bit more explanation on what to store in the vectors of original and rotated images? Kindly reply.
 » 9 months ago, # | ← Rev. 4 →   +1 Can anyone explain E to me ? "The main claim is that if a player is forced to reduce the minimum number of stones over all piles, then they lose."
 » 9 months ago, # |   0 can you give idea for solving for Problem — A for 1<=n,h,m<=10^9
•  » » 8 months ago, # ^ |   0 hello programmer waiting for response
 » 9 months ago, # |   -11 I am not being able to understand the question of Div-2 (C) Hide and Seek... please someone explain me the question??
•  » » 9 months ago, # ^ |   -11 Same bro
•  » » » 9 months ago, # ^ |   -11 how much you understand?
•  » » » » 9 months ago, # ^ |   -11 Nohing...It's showing difficulities level only 1500..But sorry for me
•  » » » » » 9 months ago, # ^ |   -11 sorry for us
•  » » » » » » 9 months ago, # ^ |   -11 Hope somebody will help ...
•  » » » » » » » 9 months ago, # ^ |   -8 Hmmm..
•  » » 8 months ago, # ^ |   0 I have modified a question a little bit.Alice and Bob are playing a game on a line with n cells. There are n cells labeled from 1 through n. For each i from 1 to n−1, cells i and i+1 are adjacent.Alice initially has a token on some cell on the line, and Bob tries to guess where it is.Bob guesses a sequence of line cell numbers x1,x2,…,xk in order. In the i-th question, Bob asks Alice if her token is currently on cell xi. That is, Alice can answer either "YES" or "NO" to each Bob's question.At most one time in this process, before or after answering a question, Alice is allowed to move her token from her current cell to some adjacent cell. Alice acted in such a way that she was able to answer "NO" to all of Bob's questions.Note that Alice can even move her token before answering the first question or after answering the last question. Alice can also choose to not move at all.You are given n and Bob's questions x1,…,xk. Lets say p1 is cell where token placed before starting game. and p2 is a cell where token is placed after the game. note that (1 <= p1 <= p2 <= n).and a pair (p1,p2) is valid, if Bob answers 'No' for all questions when alice choose this pair. and you have to count no of pairs, which are valid.
 » 9 months ago, # |   0 There is a bruteforce solution for B that works in O(nm * nm) time https://codeforces.com/contest/1162/submission/53760985
•  » » 9 months ago, # ^ |   0 why so hard? my solution works in O(n*m) time and it is much easier http://codeforces.com/contest/1162/submission/53747942
•  » » » 9 months ago, # ^ |   0 It's clear that the greedy solution works but the tutorial says that brute force doesn't, so I sent this. Could be interesting to smb
•  » » » » 9 months ago, # ^ |   0 can you explain your bruteforce approach , code is hard to understand without knowing the approach
•  » » » » » 9 months ago, # ^ |   0 If we have an inversion in a matrix, e.g. a[i][j] >= a[i][j + 1], we can either swap a[i][j] & b[i][j], or a[i][j + 1] & b[i][j + 1]. After we make a swap, new inversions may appear in adjacent cells, so then we try to get rid of them the same way. That's how the recursive function works. We just need to launch it from each cell, and during one launch we never visit one cell twice, so it's O((nm)^2)
 » 9 months ago, # |   0 SolutionIf we are at a winning position, there are at least n/2 piles that have strictly more than m stones, so we can choose any arbitrary subset of them and reduce them to m stones. This is now a losing position.I didn't get this, suppose the piles are 1,4,4,4 how can we reduce (n/2 = 2 among 4,4,4 piles) to 1,1, It's said that they must be reduced by a different amount??
•  » » 9 months ago, # ^ |   +3 It says you can but not you must .
 » 8 months ago, # |   +16 Can someone provide proof in Problem D that k must be a divisor of n?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 [Deleted]
•  » » 8 months ago, # ^ | ← Rev. 2 →   +5 Well, I used two facts to prove it. turning by $k$ will yield the same result as $2k$, $3k$ and so on; turning by $n$ will obviously put the circle in the same position it was initially. Thus there exists some $t$ such that $tk = n$, $k$ is a divisor of $n$.
•  » » » 8 months ago, # ^ |   0 By your logic 2k, 3k, ... must all divide n.
•  » » » » 8 months ago, # ^ |   +2 I can't see how to come to this conclusion.
•  » » » » » 8 months ago, # ^ |   0 Substitute k for 2k and apply the same logic.
•  » » » » » » 8 months ago, # ^ |   0 Well, it becomes $2k$, $4k$, $6k$ and so on. If there still exists some integer $t$ so that $2tk = n$, why not?I don't get what can be unclear, sorry. Maybe try marking the $0$ point and checking where will it end after some turns. $k$, $2k$, $3k$, $\dots$ will be its position at each next move. Also it'll return to 0 (which is equal to position $n$) after $t$ moves.
•  » » » » 8 months ago, # ^ |   0 i don't think the statement is valid. he said the k,2k,3k... will yeild same result and doesn't mean it will divide 15. lets i have an image, where n = 15, and k = 5. it will work when k = 5, k = 10. but when 10 wont divide 15.
•  » » 8 months ago, # ^ |   +6 Let the minimum value to do a symmetrical rotation be $k$.Then for any $t$, such that $t \% k == 0$, $t$ will produce a symmetrical rotation too, and generally rotating by $t$ is the same as rotating by $t\%k$.It's obvious that turning by $n$ produces a symmetrical rotation.Let $n \% k != 0$, then that means that $n \% k$ produces a symmetrical rotation. But $n\%k < k$, hence this statement contradicts the first one.
•  » » » 8 months ago, # ^ |   0 Thanks a lot!!!! Very clear
•  » » 3 months ago, # ^ |   0 Start numbering from zero,instead of 1If a,b moves to (a+k)%n,(b+k)%n.Then (a+k)%n,(b+k)%n will move to (a+2*k)%n,(b+2*k)%n and so on,but there should be a (a+k(q-1))%n,(b+k(q-1))%n,which will move to a,b in next step.so, (a+kq)%n=aa+kq=dn+akq=dnif k is not divisible by n,then it should definitely be divisible by nd.q can be at max n.SO,d cannot be greater than k.So if k divides nd,then k/d should divide n.In short if there is a solution with k not divisible by n,then there will definitely be another solution with k1 less than k and k1 divisible by n.Try this test case7 70 21 32 43 54 65 06 1K=2 is a solution,but k=1 is also a solution
 » 8 months ago, # |   0 Guys please can someone help me? I can't access the Dropbox solutions, it returns an error saying "server IP address could not be found".
•  » » 8 months ago, # ^ |   0 The link is working for me at the minute. Try again?
•  » » » 8 months ago, # ^ |   0 Tried again, as before, the link works fine but same error when accessing the solutions themselves. I tried different browsers and incognito mode but it didn't work. Jonny and others can you access the solutions?
•  » » » » 8 months ago, # ^ |   0 Yeah, I can access each one (Chrome, non-incognito mode, not signed into dropbox). So don't know what to suggest :S
•  » » » » » 8 months ago, # ^ |   0 Cool, thanks for trying to help man
 » 8 months ago, # |   +2 Can someone please explain 1147B — Chladni Figure string solution.
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 If for some k, you rotate all segments by k units and you get the same figure back then it is also possible for 2*k, 3*k ......so on. Now you can get the same figure back when k=n. So k must be a divisor of n. Any number under 10^5 has around 100 divisors at max, so you have to check for them only if such a k exists or not
 » 8 months ago, # | ← Rev. 2 →   0 Problem B DIV 1"We can do this by iterating through all segments (a,b), and checking that (a+k,b+k) is a segment (the endpoints taken modulo n if needed)."How can we check that (a+k,b+k) is a segment in o(1)? Tutorial says that "this gives an O(nm) solution".
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Since there are no perfectly overlapping segments maybe we can do something like — Transform a segment [x,y] into [x%k, y%k] and check final counts of segments appearing in the first block because [(a+k)%k, (b+k)%k] = [a,b].
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 By keeping the pair in a unordered_set or hashset. Or you could just use set or treeset with o(logn) complexity. It will still get accepted, I submitted this way
 » 8 months ago, # |   -8 Can anyone help me? I'm trying to implement a z-algorithm on 'Chladni Figure' problem and i get wrong answer on test 3 saying the output was "yes" and the correct answer is "no" and when i try it myself it shows the correct answer. What is the problem?
 » 8 months ago, # |   0 I am not getting the tutorial of Chladni Figure with fastest approach. please help!
•  » » 8 months ago, # ^ |   0 lets you have only one segment. try thinking when that segment becomes rotationally symmetric ( try for k = 1, .. think when you two segments try thinking when that segment becomes rotationally symmetric ( try for k = 1, .. think when you three segments try thinking when that segment becomes rotationally symmetric ( try for k = 1, .. think when you have n segments. try thinking when that segment becomes rotationally symmetric ( try for k = 1, .. now you will understand when those segments becomes rotationally symmetric. if you wont get anything try for k = 1.. n and think about why k should be a factor of n.