Help In DP Problem

Revision en1, by harshraj22, 2019-06-05 12:24:23

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.

Tags #dp, #codechef, #easy, #sorting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English harshraj22 2019-06-05 12:24:23 831 Initial revision (published)