×

# XRMTRX - Editorial

Author: Alexey Zayakin
Tester: Pushkar Mishra
Editorialist: Florin Chirica

# PROBLEM

Let's define a matrix with lines from L to R and columns from L to R. An element (i, j) has value equal to i xor j. Let's define a walk by cells which have consecutive values and share a side. What's the maximum length of a walk and how many maximum length walks are there?

# CREDITS

Thanks to Alexey Zayakin for contributing in problem explanation.

# EXPLANATION

Brute force

Since the limits are so big, it's quite natural to start seeking patterns. For this, let's write a brute force (solving the first subtask) which will allow us to see patterns. Let ways[i][j] = in how many ways can I reach cell (i, j) and x[i][j] = value from the cell (i, j).

Then, let (i', j') a cell which shares a side with (i, j). We get ways[i][j] += ways[i'][j'], if x[i'][j'] + 1 = x[i][j].

Now let's run the brute force in order to start finding patterns.

Answer is a power of 2 minus 1

The maximal length is always of the form $2^k - 1$. Let's prove it.

If we have a walk of length at least $2^k$, then there exist two adjacent cells with numbers $2^k - 1$ and $2^k$. There are two cases:

Case 1 These cells are (x, y) and (x + 1, y).

$x$ xor $y$ = $2^k$ - 1

$(x + 1)$ xor $y$ = $2^k$

$x$ xor $(x + 1)$ = $2^{k+1}$ - 1

One can see that x = $A$ * $2^{k+1}$ + $2^k$ - 1

and we can conclude that y = $A$ * $2^{k+1}$

We get some necessarily conditions by saying that both cells (x, y) and (x + 1, y) must belong to the matrix.

$L \le x$

$x + 1 \le R$

$L \le y \le R$

It's enough to check that $L \le y$ and $x < R$.

$L \le A * 2^{k+1} \le R - 2^k$

$L \le R - 2^k - ( (R - 2^k) mod 2^{k+1} )$

(I) $R - L - 2^k >= (R - 2^k) mod 2^{k+1}$

Case 2 These cells are (x, y) and (x - 1, y)

$x$ xor $y$ = $2^k - 1$

$(x - 1)$ xor $y$ = $2^k$

$x$ xor $(x - 1)$ = $2^{k + 1} - 1$

One can see that x = $A * 2^{k + 1} + 2^k$

y = $A * 2^{k+1} + 2^{k+1} - 1$

Using the logic from the above we get that

(II) $R - L - 2^k \ge (R + 1) mod 2^{k+1}$

Let's find maximum $k$ that respects one of the inequalities. Then, the maximum walk length is equal to $2^{k+1} - 1$.

Finding the number of paths of maximum length

Here is the place where we use brute force. Let's run brute force for some small tests. Let's mark a cell (i,j) with 1 if it's reachable (there exists at least one path ending there) and it has maximum value obtained last step and 0 otherwise. We need, for each value of 1, to add ways[i][j] to the solution.

Let's print all ways[i][j] values. It's easy to notice all are equal and more - their value is $\frac{K + 1}{2}$. So, the answer is simply number of ones * $\frac{K + 1}{2}$. Let's focus on calculating number of ones from brute force construction.

Those ones are placed on at most two diagonals. Diagonals are perpendicular by main diagonal. More, each diagonal has one element on line 1, respectively column 1, and on line n, respectively column n.

# AUTHOR'S AND TESTER'S SOLUTIONS:

19.7k350498541
accept rate: 35%

 5 I found that if we start row and column index from 0, then there was a pattern if we first see the first 8 rows and first 8 columns. For this 8x8 matrix i first calculated the values K,C using brute force.Now what i observed that if we see the 64x64 matrix was essentially the same thing as the 8x8 matrix if we consider the 8x8 matrix as a single cell within the 64x64. That is, name the top left 8x8 matrix as 0, the matrix to the right of it would be 1 as so on. It is possible to go to the matrix numbered 1 from the matrix numbered 0 only. Basically the same pattern of 8x8 can be seen on 64x64 and we can go on mulitplying a factor of 8.So essentially whatever initial size of the matrix is given, we can consider it as 8x8 matrix where one cell of this matrix is a subproblem of the original problem.We can go on dividing the original problem size by a factor of 8 giving an O(log8(R)) solution. answered 16 Feb '15, 17:53 291●1●4 accept rate: 21%
 1 Excuse me! But One can see that x = A * 2^{k+1} + 2^{k - 1}..., May some one explain me what does the variable A mean? it is not defined at any place. It is a good custom to explain what a variable mean, independently its meaning seem obvious. Thanks! answered 16 Feb '15, 23:35 21●2 accept rate: 0%
 1 I thought this was a really beautiful problem. I wanted to share my approach for this problem, which was a highly visual approach. I approached it by drawing a picture. After drawing the picture, the pattern was fiarly obvious, and it took a little bit more work to get the code to work. Here is the picture I drew: http://pastebin.com/YymUk9Ds This picture has * for the cells, and an arrow pointing at cells which are exactly one greater than it. Also, the 0's mark the places where L=R (our starting positions). Of course, it still takes a bit of work from noticing the pattern to getting efficient code for large cases, but this picture definitely made the process much easier. answered 17 Feb '15, 02:34 7★lg5293 511●2●14 accept rate: 10%
 0 Can someone please tell me which test case would this solution fail? http://www.codechef.com/viewsolution/6292646 I am just checking for the value of k. (max length) answered 17 Feb '15, 00:06 4★aakashk9 0 accept rate: 0%
 0 Can someone tell me some testcase on which my brute force solution fails? It didnt pass the first subcase. http://www.codechef.com/viewplaintext/6267479 answered 17 Feb '15, 11:52 101●8 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,482
×1,237
×921
×196

question asked: 16 Feb '15, 15:29

question was seen: 4,201 times

last updated: 01 Jun '16, 20:13