### antontrygubO_o's blog

By antontrygubO_o, 5 years ago, translation,
• +150

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   +43 My last hour of yellow name :(
 » 5 years ago, # |   +3 wow thank you for the fast editorial :D
 » 5 years ago, # | ← Rev. 7 →   +222 F can be solved in $O(n^4)$. And I guess it can be solved in $O(n^2)$ per test case.If $(a,b)$, then $(a+k-1, b+k)$ with $k\geq 4$ or $(a+k-1, b+k*(k+1)/2)$ with $k\geq 2$.There is a tree structure about the permutation, which is called 析合树 in Chinese, named or invented by CommonAnts. We can derive this result directly from the tree structure. You can see these two 1 2 in Chinese for details.And there are some similar problems with this combinatorial structure of the permutation, like NEERC 2018 I, and China Final 2018 B.
•  » » 5 years ago, # ^ |   +316 The Chinese have a Data structure for everything.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +51 Nobody:Chinese people: Let's make a Data Structure based on this problem.
•  » » 5 years ago, # ^ |   +23 I think it is PQ-tree?
•  » » » 5 years ago, # ^ |   0 no you can do it by segment tree
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +11 No, I think they look similar. PQ-tree tries to find a valid permutation with some given consecutive subsets, but “析合树” is to describe all consecutive subsegments of a permutation. The tree structure has two types of nodes, which are similar to Q-node and "P-node which is not Q-node" respectively. I mean, values of all sons of a first-type node (“合点”) are monotonic, and those of a second-type node (“析点”) form a simple permutation.I introduced the tree and an $O(n)$ algorithm to construct it for a given $n$-permutation on RAM (with linear RMQ). So that many such problems could be solved in linear time. For example, CF997E.In fact, this problem F could be solved in $O(n)$ time. We can make a valid permutation with at most $n$ items at first with greedy. After that, replace a leaf with remain items as a simple permutation. It's $O(n)$ by adjusting those conflicts of constant size (including corner cases of greedy, the extra one consecutive subsegment for the simple permutation and inexistence of a simple permutation of length $3$).Another similar structure I've ever seen is "separation tree for permutations". It only cares about the second-type nodes, and are for problems about simple permutations.A simple permutation is a permutation without consecutive subsegments.
•  » » » 5 years ago, # ^ |   +11 If a PQ-tree successfully constructs a permutation, it can be regarded as a virtual tree for a subset of nodes in the permutation's “析合树”, each Q-node is a first-type node “合点”, and each P-node can be either type, “析点” or “合点”, depending on which permutation you choose in construction.
•  » » 5 years ago, # ^ |   +23 Problem setter & tester be like
•  » » 5 years ago, # ^ |   +10 I also solved it with $O(n^4)$ preprocessing with $O(n^2)$ per test case — I know how to improve this to $O(n)$ but I didn't bother. This is my idea, I have no idea why but it seems to work:If there is a solution for some $n,k$ then there is also a solution such that you start from some "disorderly" permutation of length $m \leq n$, and then in $n-m$ steps you either append a new maximum element to the permutation or append the new minimum to the permutation. A permutation of length $m$ is "disorderly" if its beauty is exactly $m+1$. I used dynamic programming to track the longest "increasing subsegment" suffix of the permutation, this tells me how many new good subsegments are added when the new maximum is appended. Code: 59129441
•  » » 4 years ago, # ^ |   0 So my mans created his own data structure now
 » 5 years ago, # |   +8 Fastest Editorial I have seen in a while! Thanks :)
•  » » 5 years ago, # ^ |   +40 So fastest that it was pulished 2 days ago!
 » 5 years ago, # |   0 I was able to solve Div2: C with some example that I wrote in the paper. I was trying to understand the derivation of editorial, but I am not able to understand it. Can someone please elaborate it more like why n even always has no answer?
•  » » 5 years ago, # ^ |   +16 Consider taking some array from the circle. Then take next value and remove last value, on the same circle. The sum cannot stay the same, because that means what we removed and what we added is equal, and we cannot do that. So it either goes up or down by 1. Imagine sum increases by 1. We can write +1 near that number. After that, with same logic, next move has to decrease sum by 1, because increasing number twice gives us three numbers on blackboard: sum, sum + 1, sum + 2. So we can write -1 near that number. Now consider a circle with +1 and -1 instead of numbers. If it is odd, it starts and ends with same value — easy to see. And if it is even, is ends with different value and we are back at the sum. No two consecutive numbers (+1 or -1) must stay the same, as it is easy to see.
•  » » » 5 years ago, # ^ |   0 I didn't quite get the last paragraph of your answer, about the circle of -1 and +1. Can you elaborate a bit please? thanks in advance.
•  » » » » 5 years ago, # ^ |   0 Let's create second circle of the same size, but with +1 or -1 inside, instead of numbers we put in. If it has length of n, we can label its nodes from 1 to n inclusive. Even ones have same sign, and all odd — labeled ones have different sign. The only place when it could go wrong is connection of n'th node to the first one. If they are both odd, they will have the same value, and we don't want that, as we showed. So 1 is odd and n has to be even
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 but the question asked to check in 1 to 2n. it doesn't matter if n is even or odd the last node and first will have a different sign. please explain why the n even is not possible??
•  » » » » » » 5 years ago, # ^ |   +1 Yes, the borders work well since the circle is of even length. But there is another problem with even n.Consider doing one step around the circle I mentioned. Let's denote sum of all numbers on the circle S, and previous sum in our chosen interval A. The sum of elements we have not chosen will be B = S — A. If we get +1 as result, new sum is A + 1. What happens to B then? Since S stays constant, new B = B — 1. If we choose the second interval as initial one, we would have to write -1 on the next node. So if we have +1 on one side, then we need to have -1 on opposite side (and vice versa). If n is even, we get two sequences (+1 -1 +1 -1 ...) (+1 -1 +1 -1 ...) of length n each. Their first elements will have the same sign, which is contradictory
•  » » 5 years ago, # ^ |   0 Iv got a simple proof for that.If input is n we have 2n numbers to arrange .the sum of these 2n nos is s=2n*(2n+1)/2 =n*(2n+1).since 2n+1 is always odd,s depends on n.now if n is even ,s can be divided in two equal parts(eg 18+18 for n=4) which we dont want as sum of no two consecutive n nos can not be equal.so n is odd.
 » 5 years ago, # |   0 Is the answer to the bonus of Div1.A yes when k is odd
•  » » 5 years ago, # ^ |   -11 yes
•  » » 5 years ago, # ^ |   0 no. consider k=1
•  » » 5 years ago, # ^ |   0 When k=1,it is impossible to find such an answer
•  » » » 5 years ago, # ^ |   0 When $k=1, n=2$ it is possible
•  » » » » 5 years ago, # ^ |   0 You are right.I didn't think very carefully
 » 5 years ago, # |   -40 can someone please help me with my code. There is something strange.
•  » » 5 years ago, # ^ |   -20 Why downvote? I post it because I am not able to understand why it is not printing all the $n$ strings. I had run the last for loop n times. But in the output it is printing only 3 rows. If someone can help then Please help!
•  » » » 5 years ago, # ^ |   0 probably your code print something other than 0/1 (-1 or something)
 » 5 years ago, # |   0 Somebody pls check and tell what's wrong with my code for Div 2 problem B !! code
•  » » 5 years ago, # ^ |   +5 input : 3 -1 0 1 output: 1 yours: 3
•  » » 5 years ago, # ^ |   0 Currently, you are ALWAYS making 0 go to 1. However, 0 can also go to -1 for the same cost (1).
 » 5 years ago, # |   0 Can anyone explain how to solve problem Div2 D?? I am not able to understand the editorial...
•  » » 5 years ago, # ^ |   +1 I did it this way- The maximum number in the input is 10^18 which can be represented in 64 bits. The minimum possible cycle can be of length 3. If we have the xth bit set in any 3 numbers, then we are done! (all 3 will be mutually connected because of non zero "and") There are at max 64 bits. => If we have more than 128 non zero numbers (By PHP) in the array, then we will get a cycle of length 3.Now for <= 128 non zero numbers. We can check by actually making a graph. It will take O(m^2), which will be well within the bounds.
•  » » » 5 years ago, # ^ |   0 How do you come up with the "128 non-zero numbers" logic?
•  » » » » 5 years ago, # ^ |   +8 10^18 fits well inside 64 bits. We need a minimum of 3 set bits at any common position. By Pigeon Hole Principle if we have more than 64*2 = 128 numbers (non zero because zero has none of the bits set) then at least one of the position will have 3 set bits. (The bound of 128 can be made stricter if you calculate the exact number of bits needed to represent 10^18)
•  » » » » » 5 years ago, # ^ |   0 Thanks
•  » » » » » 5 years ago, # ^ |   0 how does having >128 numbers guarantee that there will be at least 3 numbers having set bit at the same position? (I'm not saying the answer is wrong, i wanted to know how php is used here)
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 in this problem Max(Ai) = 10^18 which has 60 bits, and as they said > 128 numbers guarantee that there will be at least 3 numbers having set bit at the same position.what if i change Max(Ai) = 7 then it only has 3 bits and > 7 numbers guarantee that there will be at least 3 numbers having set bit at the same position. how can it happen?here is the example N = 74 4 2 2 1 1 4and then i convert all of them to Binary Form100100010010001001100sum of column: 3 2 2as you can see, at the last input, no matter what number you add (as long it <= 7), the sum of column will be >= 3
•  » » » » » » » 5 years ago, # ^ |   0 i had already figured it out but thanks!
 » 5 years ago, # | ← Rev. 2 →   -8 For the problem, Shortest Cycle ,in the test case with n=10^5 and large numbers, making an adjacency list is causing Memory Limit Exceeded Error. How to prevent this?Edit: Just note if too many edges (thus giving memory limit exceeded) then there is a triangle.
 » 5 years ago, # |   0 div1 a. i noticed a beautiful pattern by connecting numbers on circle sequentially. my solution was 0 3 4 7 8..., i.e., +3 +1 under modulo 2*n,now join 0->1,1->2..2*n-1->1and so on it makes flower like pattern on paper.really amazed after seeing that.
 » 5 years ago, # |   +1 Thank you for your challenging problems and educative tutorials! But I was caught with some trouble at problem D... 59056716 I tested this submission with test 15 both on my local Windows machine and codeforces custom invocation. Both are resulted in 3. But every attempt to submit turned out to be Wrong answer on test 15...
•  » » 5 years ago, # ^ |   0 OH I thought I have made some mistakes...
•  » » 5 years ago, # ^ |   0 Maybe I pasted some other test data by mistake... Finally I found out my fault, then I formed a bfs tree, to judge the size of rings by LCA！[submission:59058541]
 » 5 years ago, # |   0 For 1206 D, 1205 B Another way, If the no. of non-zero elements > 120 ( 2*log2(10^18) ) then we must surely have a 3-cycle. Otherwise, for all vertices v, do BFS traversal to find length of shortest cycle through v and take minimum. This will be in O(V*(V+E)) time and O(V+E)(max O(V*V)) memory. Not much efficient though.
•  » » 5 years ago, # ^ |   0 My solution 59056716 is very close to that, but I strangely recieved a WA on test 15, while I surely got the correct answer in codeforces custom invocation...
•  » » » 5 years ago, # ^ |   0 Custom Invocation gives 5!=3.
•  » » » » 5 years ago, # ^ |   0 Awwww I see... I'm going to keep debugging...
•  » » » » 5 years ago, # ^ |   0 Thank you! Finally I formed a bfs tree and judge the size of rings by LCA！[submission:59058541]
 » 5 years ago, # |   0 Why am I getting WA on test 5 59056925 in problem D ? I think I misunderstood the problem. Can someone show me how the answer for test 5 is 4 ?
•  » » 5 years ago, # ^ |   +2 Your massive a is int, but should be ll.
•  » » » 5 years ago, # ^ |   0 Thanks. It worked.
 » 5 years ago, # | ← Rev. 3 →   0 In Div-2D, can someone explain why using set as Adjacency list gives AC int the following code 59059506 whereas using Vector as Adjacency list gives WA in this code 59057776
•  » » 5 years ago, # ^ |   +1 Given that you are getting WA on TC 14, it is probably because two values can share more than one bit, so the vector representation would have multiple edges going between the same two nodes, which would allow a cycle of length two.
•  » » » 5 years ago, # ^ |   0 Yeah, got it. Thanks.!!
 » 5 years ago, # |   +2 Finally I left div2.. Nice problems, but solving them from smartphone is incredible as usual :(
 » 5 years ago, # |   +25 For div2,D If the number of non_zero numbers is more than or equal to 119 ,we can just output 3.（Pigeonhole Principle,think of each bit as a pigeonhole,and think of each non_zero number as a pigeon） If it is less than 119,we can just use Floyd algorithm,we can solve it in O(n^3).This might be a little bit easier to understand.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I tried to implement Floyd in the contest but failed coz I discover a problem: say there's an edge u -> v, Floyd will find a cycle path of "u -> v -> u" coz this is an undirected graph. And I don't know how to counter this problem. Do you know if there's any tweak I can do to make Floyd work?
•  » » » 5 years ago, # ^ |   0 http://codeforces.com/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
•  » » » » 5 years ago, # ^ |   0 Thanks for the reply, is it ok for you explain these two lines of code?  for(int i = 0;i < k;i++) for(int j = 0;j < i;j++) 
•  » » » » » 5 years ago, # ^ |   0 It's not quite easy to explain. It's just a way to avoid the situation you said above.
•  » » » » » 5 years ago, # ^ |   0 Kindly explain the above lines if you have understood them!
•  » » » » » » 5 years ago, # ^ |   +1 This loop is essentially enumerating all the pairs that satisfies 0 <= i,j < k. The shortest path between any pair can only include Vertex 1 ... Vertex k — 1 according to the property of Floyd algo. So here we can enumerate all the cycles that contains Vertex 1 ... Vertex k. When k iterate from Vertex 0 to Vertex n, we basically covers all the possible cycles in the graph.
•  » » 5 years ago, # ^ |   0 Can you please explain how to use Floyd's algorithm for finding the shortest path? (I read somewhere it couldn't be used for undirected graphs). It would be of great help. Thank You.
•  » » » 5 years ago, # ^ |   0 http://codeforces.com/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
•  » » » » 5 years ago, # ^ |   0 What is the logic behind (mincircle = min(mincircle,d[i][j] + e[j][k] + e[k][i]) this line? and Thank You for your help.
 » 5 years ago, # |   0 Can someone explain me the proof of div2 C,i basically did some cases and realized that if the number is even there is no solution, but i cant prove it.
•  » » 5 years ago, # ^ |   0 "Now, if n is even, we get a contradiction, since ai+n−ai=−(a(i+n)+n−ai+n)ai+n−ai=−(a(i+n)+n−ai+n), but due to the alternating they must be equal."
 » 5 years ago, # |   +12 Problem B.Div2 is interesting.59065083 :D
 » 5 years ago, # |   0 Hi could someone tell me why this is failing for "Make Product Equal One" https://codeforces.com/contest/1206/submission/59025115 locally I'm getting correct answer for the same input, is it some IO issue with Golang?
•  » » 5 years ago, # ^ |   0 int -> long long ??
 » 5 years ago, # |   0 In Problem D, I first checked for the 3 length cycle case as given in editorial and then I'm finding the minimum length cycle for the other case by taking each vertex as root and seeing if it is in the cycle or not, cases with some non-zero inputs and n = 100000 are passing but the case with all zero inputs and n = 100000 is giving TLE. I'm unable to understand why in case of all zeros it is giving TLE.Submission — 59060203
•  » » 5 years ago, # ^ |   0 Instead of declaring vis and par vectors of size n every time in the loop, declare map of vis and par and for each iteration of loop, clear both the maps. Hope this helps.!
•  » » » 5 years ago, # ^ |   0 Yeah it helped, thanks. But yet I'm unable to understand why previous thing didn't worked.
 » 5 years ago, # |   +11 Can someone explain the first approach of div1C in more depth? Apart from the dp part. Thanks in advance.
 » 5 years ago, # |   0 Div1 D solution doesn't seem natural I think.
 » 5 years ago, # |   0 How can solve 1D in $O(n)$? I think "divide the subtrees of the childs into two groups" need $O(n\log n)$...
•  » » 5 years ago, # ^ |   0 Oh, I know...
 » 5 years ago, # |   +1 can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)
 » 5 years ago, # |   0 Many of you can't solve Div2 C. When you need to construct an array to solve a promblem,just construct it boldly. Don't be afraid.For this problem, let v be some number of the array(a[i]),let v' be the number opposite v(a[i+n]). Then the circle was cut into halves.let s1 = a[i+1] + ... + a[i+n-1],s2 = a[i+n+1] + a[i+n+2] + ... + a[i-1]. if n is an even number,it means that 2 is a divisor of the sum of all numbers,let it be 2k. The sum of any n consecutive numbers must be k.So,v + s1 = k,v' + s1 =k.v = v'!It's impossible.if n is an odd number,it means that the sum of all numbers can be written as 2k+1. Then |(v + s1) — (v' + s1)| must be 1.It means v — v' = 1 or -1. Just construct it boldly.I said to my self when I was trying solving this. What we want is for any i,s1 = k or k+1.Now we have n groups:(1,2)(3,4)...Why not let s1 for v = 1 1 + 4 + 5 + 8 + 9 + 12 + 13 + ... ? (We choose the first one in the first group,second one in the second group,first one in the third group...)It can be proved right.I won't write down the proof.(I didn't prove the algorithm at all when I was participating the contest,but luckily my thought was corret. :D )The proof was already given in the editorial.(I'm a Chinese student,there might be some grammar mistakes.Please forgive me for this and upvote for me.Thanks.)
 » 5 years ago, # | ← Rev. 4 →   +28 Div1 Problem E can be solved in the time complexity of O(n log n) with Möbius inversion formula : let define that $[ P ]= \begin{cases} 1, & \text {if P is true} \\ 0, & \text{if P is false} \end{cases}$try to enumerate i1,j1 , whose gcd is d , and simplify the formula it with Möbius inversion now we have $Answer=\sum_{i_1,j_1\in [1,n-1],d=gcd(i_1,j_1)}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$ $Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}[d=gcd(i_1,j_1)]([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$using the inversion: $[n=1]=\sum_{p|n}\mu(p)\ \ ,\mu(x)is\ Möbius\ function$ $gcd(a,b)=d\ <=>\ gcd(\frac ad,\frac bd)=1$we can derive that $Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})\sum_{p|gcd(i_1/d,j_1/d)}\mu(p)$ $\because p|gcd(i_1/d,j_1/d)<=>pd|i_1\ and\ pd|j_1$ $\therefore Answer=\sum_{d=1}^{n-1}\sum_{pd  » 5 years ago, # | 0 Can anyone pls prove this in Div1E?The case of i1+j1≤n is obvious: in this case, by subtracting and adding i1,j1 we can show that the string has period gcd(i1,j1), in this case comps=gcd(i1,j1). We now consider the case when i1+j1>n.  » 5 years ago, # | 0 Can someone help me figure out the complexity of D problem. There could be at max 60 edges and for each edge we perform a BFS to find the shortest distance between its end points. And there are n vertices, so total complexity of performing repeated bfs would be 60^2*(n+60). And in order to construct the graph the work would be n*(log10^18) so overall — n*(log10^18) + 60^2*(n+60). Could someone tell me if my analysis is correct. Thanks in advance. •  » » 5 years ago, # ^ | 0 No!! There are at most 60 edges in a graph and removing each edge and doing bfs would cost me at most 60 operations . so overall our complexity would be (60)^2. You could have also used bellman ford for this but there time complexity would have been (60)^3 in worst case. •  » » 5 years ago, # ^ | ← Rev. 4 → 0 60 edges can connect at most 120 vertices. So rest of the vertices have zero degree, you don't have to do BFS on them. For example, you can do BFS on the connected component of source only. So my guess is, depending on the implementation the complexity may vary.  » 5 years ago, # | 0 Can anyone please explain to me how to find the shortest cycle using the Floyd Warshall's algorithm?? •  » » 5 years ago, # ^ | ← Rev. 9 → 0 Define$dp[i][j][k]$as the shortest path from$i$to$j$using upto prefix$k$of vertices, then shortest cycle length is$dp[i][i][n]$.So basically you find the shortest path from vertex$i$to$i$itself. Make sure during initialization you set,$dp[i][i][k] = \infty, \forall k \in [0, n]$and during transitions, avoid going from$i$to$i$through$i$(Well, actually this happens automatically if you set$dp[i][i][0] = \infty$).(Prerequisite: Basic version of Floyd Warshall)Setting$dp[i][i][0] = \infty$is mathematical way of saying that there is no path from vertex$i$to$i$without going through any vertex.EDIT: This only works for Directed graphs, in undirected graphs, this won't work(Since each edge of Undirected Graph == 2-length cycle of Directed Graph), see explanation here, https://qr.ae/TWreWj •  » » » 5 years ago, # ^ | +6 I did not understand what did you mean by "upto prefix k of vertices", could you please explain that part in detail?. It would be of much help. Thank You. •  » » » » 5 years ago, # ^ | ← Rev. 3 → +1 Prefix$k$of vertices, means possibly using vertices from set {$\,1, 2, 3,..., k$}.Read more details from Wikipedia, https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm  » 5 years ago, # | +3 How does the checker work fast enough to determine whether there exists a palindromic path if I query distant points in Div.1 problem C? •  » » 5 years ago, # ^ | ← Rev. 2 → +10 I come up with an idea look at this :if dp[i][j][k][l]=1 means there is a Palindromic Paths from (i,j) to (k,l),0 otherwise.update: dp[i][j][i][j]=1,dp[i][j][i+1][j]=(a[i][j]==a[i+1][j]),dp[i][j][i][j+1]=(a[i][j]==a[i][j+1])if(a[i][j]=a[k][l]) dp[i][j][k][l]=dp[i+1][j][k-1][l]|dp[i+1][j][k][l-1]|dp[i][j+1][k-1][l]|dp[i][j+1][k][l-1];elsedp[i][j][k][l]=0;Do you think it's right? •  » » » 5 years ago, # ^ | 0 And complete is O(n^4),it's fast enough  » 5 years ago, # | 0 Could anyone please explain the second solution of Div.1 C more clearly?"Thus, the algorithm is as follows: choose any path between$(1,1)$and$(4,4)$, find on it four cells with a xor of numbers equal to$0$, and ask a question about it."Why does there exist a path from$(1,1)$to$(4,4)$such that the xor is equal to$0$? •  » » 16 months ago, # ^ | ← Rev. 2 → 0 I'm wonderig the same thing rn  » 5 years ago, # | 0 for B wouldnt the answer always be 2 since if a[i] & a[j] != 0, then in the graph there will be an edge of weight 1 from i to j. since a[j] & a[i] != 0 as well. we will get an edge from j to i, which is a back edge of weight 1. this would mean the shortest cycle is of weight 2 always? •  » » 5 years ago, # ^ | 0 In the announcement they mentioned this :Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices.  » 5 years ago, # | 0 Useful for 1206C/1205A  » 5 years ago, # | ← Rev. 3 → 0 Cool.  » 4 years ago, # | ← Rev. 2 → 0 For div1.B, why does this TLE give TLE for input with 1e5 0s, which forms an empty graph, while this gives AC.  » 3 years ago, # | 0 Could anyone prove an upper-bound of the answer to Div1D? Is$\frac{2}{9}n^2+O(n)$optimal?  » 16 months ago, # | ← Rev. 2 → 0 I did div2-E in the dp way, but I can't understand how there will always exist a path from (1, 1) to (4, 4) such that xor sum of 4 consecutive elements is 0. For example in the following matrix, there exists no such path from (1, 1) to (4, 4): 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 antontrygubO_o hate to ping you, but could you please clear this doubt. •  » » 16 months ago, # ^ | 0$n\$ is odd.
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 Oh I see, you have made a small typo in the last line of the editorial, you have written (4, 4) instead of (n, n). I was trying to prove that there doesn't necessarily exist such path from (1, 1) to (4, 4) xd.