Problem: CodeChef: Practical coding for everyone
My Solution (in simple python): It works for first 2 subtasks and also 5 out of 6 test files in subtask 3: CodeChef: Practical coding for everyone
If you see “Access Denied”, check my code here: G46A36 - Online IDE & Debugging Tool - Ideone.com
Logic: The above solution uses cyclic relationships between XOR results to find the original numbers. I found that these cyclic relationships exist for a group of 4, 5 and 7 numbers. E.g.: if I need to identify a group of 4 numbers say A, B, C and D, I can easily do that by asking 4 questions with each of A, B, C and D repeated atmost thrice.
For a group of 4 numbers the 4 questions will be:
A, B, C → XOR = X1
B, C, D → XOR = X2
C, D, A → XOR = X3
D, A, B → XOR = X4
then, A = X1 ^ X3 ^ X4, B = X1 ^ X2 ^ X4, C = X1 ^ X2 ^ X3, D = X2 ^ X3 ^ X4
Similarly I found such cyclic relationships for groups of 4, 5 and 7 elements (Not sure why group of 6 elements ends up with indeterminate equations). You can find those relationships in the above solution.
Now, given an array of size N, I break the given array into:
(i) (N/4) groups of 4 elements each if N mod 4 is zero.
(ii) (N-5)/4 groups of 4 elements each plus 1 group of 5 elements if N mod 4 = 1.
(iii) (N-10)/4 groups of 4 elements each plus 2 groups of 5 elements each if N mod 4 = 2
(iv) (N-7)/4 groups of 4 elements each plus 1 group of 7 elements if N mod 4 = 3.
Applying above cyclic relationships to all groups gives all elements of array. The above solution works for all N >=4 except N=6 but it shouldn’t be a problem since N>=8 in the problem.
The above solution has only one test file failing to get the correct result. I struggled to debug my solution but ultimately couldn’t find one failing test case.
Can anyone help me find one breaking test case? I know there could have been easier solutions but this is what came to my mind first and I stopped trying in the long contest once I couldn’t get even the second problem fully correct, out of frustration.