XRMTRX - Editorial

ad-hoc
editorial
feb15
medium-hard

#1

PROBLEM LINK:

Practice
Contest

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*[j] = in how many ways can I reach cell (i, j) and x*[j] = value from the cell (i, j).

Then, let (i’, j’) a cell which shares a side with (i, j). We get ways*[j] += ways[i’][j’], if x[i’][j’] + 1 = x*[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*[j] to the solution.

Let’s print all ways*[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:

Tester’s solution

Setter’s solution


#2

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®) solution.


#3

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!


#4

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)


#5

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.


#6

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