I have spent a long time trying to find the best solution in all cases for OPTSET, but I still get failures in test cases 0 7 8 10. Given these test case numbers, can anyone suggest any examples of where I may have gone wrong?
It would be nice if you could link your submission to this problem. Only after seeing your code, can someone try to help
In writing up my approach for this task I found a mistake. With this corrected, my code passes all tests except test 0. You can find my submission at Solution: 47886971 | CodeChef
Here is my approach to solving the problem. Define P as the largest power of 2 less than or equal to N, and Q as the next power of 2 above N. It is obvious that the largest possible XOR of a collection of numbers up to N is Q - 1, which I call the target T.
For K = N we have no choice but to use all the numbers, whatever the result.
For K = 1 the best result is achieved by using just N, to give a result of N.
For K = 2 we can achieve the target by using P - 1 and P.
Before going further, we can easily verify that for any range of numbers from 2^J to 2^(J+1)-1 where J >= 2, the XOR of all numbers in the range = 0. Also 2 xor 3 = 1and 1 xor 2 xor 3 = 0. So if we output all the numbers in the range 1 to P-1 the total XOR is 0. If we omit any single number M from the numbers in this range the total XOR is M.
So for values of K < P we can adopt the following strategy.
First include P itself in the output, to set the first bit. Decrease K to define only how many are still required, as we go.
Subsequent steps down to 4 add multiples of 4 numbers to the output, so we need to make sure that we can handle the last few K mod 4 to reach the target exactly. We can make a table to what combinations of H = K mod 4 and X = the remaining number required to reach the target are possible. In this table F indicates failure, an impossible combination.
H 0 1 2 3 X 0 - F F 1, 2, 3 1 F 1 2, 3 F 2 F 2 1, 3 F 3 F 3 1, 2 F
So if K < P/2 we need to output a number leaving something that is possible at the end. As we are about to output one number which we would like to be P - 1, if the remaining H = (K - 1) mod 4 is 0 or 3 it will all work out correctly if we leave nothing. Otherwise we need to leave a single number to be output at the end, by adding P - 2 to the output at this stage instead of P - 1.
If K >= P / 2, we will output all numbers in the range P/2 to (P - 1) except one. After this the remaining H will be (K + 1) mod 4, so the choice of whether to leave nothing or 1 is reversed.
Then work down through remaining powers of 2, considering ranges as above. If a range covers at least the remaining K, add all the numbers in the range to the output. Else go on to the next range. We end up with 0 <= K <= 3 and 0 <= X <= 3, from which we choose the combination as in the table above. Because of all the earlier checks we ensure that we always have a valid combination to reach the target.
Now consider the case where K >= P. Start by expecting to use all numbers from 1 to K + 1 except a number yet to be determined, and modify the result from there. Remembering that the XOR of all numbers from 1 to P-1 is 0, we need to evaluate the XOR of numbers from P to K + 1 inclusive. X = The XOR of this with the target could be the number to exclude.
If the result of all the operation above is at least P, then we have an even number from P to K + 1 inclusive, and must exclude one of them. If X is in the range P to N, simply exclude that number. If K + 1 = N we must choose to exclude either N or N - 1 to get the best result. In other cases we can also choose to exclude 2 further numbers less than P. I won’t go into all the details here, but you can find them in the code.
When we have an odd number from P to K + 1, first check if we can simply output the numbers from 1 to K. If this does not reach the target, and X is within range (not 0) simply exclude X. When X is 0, we exclude 1, and miss the target. There are special cases when N = 7 and K = 4 or 5.