Can anyone explain me the solution of XOMMON problem from codechef. I looked at many successful submissions, though don't understand why we sort the pair of int, pair and then do dp calculations. Also, I wonder why my approach is incorrect .
My approach: for every index,store the max length of subseq and corresponding xor val. To find the same for any index(say i), loop through each index less than the current one (say j), and see if the xor of two,is >= the xor stored at the lower index(j). If it is, look if length of subseq formed exceeds the length stored at i, if yes update xor val and len at i, if it is same, see if xor of two numbers is less than that stored at i, if yes again update. finally the answer should be the max element of the array len.
I guess it's not enough to just store the answer of maximum length for each index. The reason is that if we take the number at position i to our answer, it doesnt mean that our subsequence must also contain the best answer's elements of index i(I mean it is not always that i-th number is the dp[i]-th element in our answer, where dp[i] is the maximum length of subsequence for position i, as you described above). Maybe you should keep kinda 2 dimensional dynamic array (like dp[i][j] = minimum xor of the last element of the subsequence , which length is i and its last element is a[j]) ?
your logic fails on this test case n=4 array= 5 24 24 1 answer should be 3 but your output will be 2.