PROBLEM LINK:
Author: Anil Kishore
Tester: Utkarsh Lath
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Meet in the middle, Tries
PROBLEM:
Given a n \times n grid with values in each cell, if the energy of going from top left corner to bottom right corner is the bitwise xor of all the values in path, find the maximum energy. From a cell, you can go to either right or down in a single step.
SHORT EXPLANATION
Use meet in the middle approach. Use the anti diagonal of the grid as the middle. From start cell, enumerate all possible ways to reaching an anti diagonal cell. Add the energy for the path to a trie corresponding to that anti diagonal cell. Do the same for all paths starting from the target cell. For each anti diagonal cell, calculate the maximum value of xor of a path through the cell using a trie. The answer is maximum among all the anti diagonal cells.
EXPLANATION:
Section 1
Enumerating all possible paths from start to the target cell will time out. So, we use a clever way of reducing the time complexity called meet in the middle.
Suppose for a particular cell, we know all the xor values possible by starting from the start cell and reaching the cell (include the value of the cell too in the xor). Also, we additionally know the xor values for all possible paths from target to the cell (excluding the value of the cell). Now we can calculate the maximum energy path going through this cell using the approach discussed in Section 2. For now let us focus on which cells we need to consider. We need to select a group of cells for which we want to apply this approach. This group needs to satisfy the following 2 criteria:
- All possible paths should go through at least one of the cells from the group
- The number of possible paths from start to this group and from target to this group should be equal (to minimize the amount of work done).
The anti diagonal i.e. all cells (i, j) satisfying i + j = n + 1 is perfect for this. As, 1. All paths from start to target has to go through an anti diagonal cell and 2. The path length of any path from start to the anti diagonal is n - 1 and from target to diagonal is also n - 1. So the amount of paths from start and target to the anti diagonal is equal. Note the forward diagonal (i = j) is also fine.
Section 2
So for each cell we want to find the maximum energy path through that cell. Let us solve the following equivalent problem:
We are given 2 groups of values of size n_1 and n_2. We need to find the maximum x_1 xor x_2 where x_1 is taken from the first group and x_2 is taken from the second group.
A bruteforce approach with complexity O(n_1 * n_2) will won’t do as this will mean the complexity of the above algorithm will not be better than the bruteforce one.
The solution to this problem uses tries. We won’t go into the details of what is trie. The following discussion assumes you know what a trie is and how to use it.
For one of the group we will build a trie by assuming the number as a fixed size bitstring of length 31. Insertions into the trie will proceed from the msb to lsb i.e. from bit #30 to bit #0.
So now we have a trie of one of the group. Now for each value in the other group, we will find what is the maximum xor value for this value.
Let us start from the msb. Now we want the msb to be 1 if possible. Xor of two bits is 1 if they are different. So, if the msb of the current number is 1, we will see if there is a 0 in the trie at the root. If the msb of the number is 0, we will look for 1 in the root. If the bit is present in the root i.e. there is a child node corresponding to that bit, then we will keep the msb bit of the answer as 1 and search recursively for the next bit. Otherwise, we can only have 0 in msb, so we keep the msb as 0 and search recursively for the next bit using the child of the root corresponding to the bit. We continue this till we reach bit #0 when we get the maximum value.
We do this for all n_2 values and return the maximum.
This takes O(n_1 + n_2) time which is much better than O(n_1 * n_2). This is the reason the meet in the middle approach will work within time limit.
We do the above procedure for all anti diagonal cells and the answer will be the maximum among them.
Time Complexity:
Note that all the paths are of length n from the diagonal. At each step we can go right or down. So there are 2^n paths. Finding the maximum takes O(1) time. So overall complexity is:
O(2^n)
