PROBLEM LINK:
Author: Akash Rakshit
Editorialist: Akash Rakshit
DIFFICULTY:
HARD.
PREREQUISITES:
Strings, Binary Search, Bitmasking
PROBLEM:
Step 1: Finding the minimum length substring which contains the given two strings for all queries. Let these minimum lengths be contained in an array.
Step 2: Divide the array into two subsets such that xor sum of both the sets is maximum.
EXPLANATION:
This problems contains two parts. First find the minimal length substring which contains both the query strings. And then divide the array containing all the answers obtained in first step, in such a way that xor sum of two subsets is maximum.
First part of the problem can be solved by storing the initial index of all the strings upto length 10 in a vector. We can use the map of string and vector to store the indexes. Then we can use binary search algorithm to find the minimum length. You can see the below given code for details.
Now for the second part of the problem, let X be the xor of all numbers in the array containing the solution obtained in first step. Also let P be the xor of all numbers in the first collection and Q be the xor of all numbers in the second collection. Note, if the i-th bit in X is equal to 1 then the same bit in numbers P and Q is either equal to ‘0 and 1’ or ‘1 and 0’, respectively. Analogically, if the i-th bit in X is equal to 0 then this bit in numbers P and Q is either equal ‘0 and 0’ or ‘1 and 1’, respectively. As we can see, if the i-th bit in X is equal to 1 then it doesn’t affect on the sum P+Q in any way. For now, let’s forget about the second condition in the statement which asks us to minimize P in case of tie.
In order to find the optimal value of P+Q we need to make one more observation. Let’s look at the most significant bit of number X which is equal to 0. If there exist such partitions of the initial collection in which this bit is equal to 1 in P then the optimal partition should be one of them. To prove this one should remember that the respective bit in number Q is also equal to 1. Let this bit correspond to 2L. If the bit we are looking at is equal to 1 in both P and Q then the smallest possible value of P+Q is 2L+1. On the other hand, if both P and Q have zero in this bit, then the maximal possible value of P+Q is 2L+1-2 which is strictly smaller than 2L+1.
We’ll be solving the initial problem with a greedy algorithm. Let’s iterate over all bits which are equal to 0 in number X from highest to lowest. We’ll try to put 1 to the number P in this position and then check if there exists at least one partition which satisfies the current condition together with all conditions we’ve already set up. If such partition exists, then we can leave our newly added condition and move to lower bits. If there is no such condition, then we need to move to lower bits without adding any new conditions. At the end we’ll find the maximal value of P+Q.
So, we have a set of conditions and we want to check if there exist at least one partition which satisfies all of them. For each condition for i-th bit we’ll create an equation over the field Z2 with n variables, where the coefficient at the j-th variable is equal to the i-th bit of the j-th number. If some variable is equal to one then we take the corresponding number into the first set, otherwise – into the second one. This system of equations can be solved with Gaussian elimination. Note that we don’t need to solve the complete system from scratch every time we add a new equation. It’s sufficient to recalculate the matrix from the previous state, which can be done in O(NK). Here K is the number of equations in the system.
Now we need to minimize P while keeping the value of P+Q unchanged. It can be done in the similar way as finding the optimal value of P+Q. We’ll iterate over all bits which are equal to 1 in number X starting from the highest one. For the current bit we’ll try to put 0 in the corresponding position of P. If after adding this condition our system of equations becomes incompatible, then we need to put 1 in this position of P.
The complexity of this algorithm is O(NL^2), where L – is the length of binary notation of the largest number.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.