Need help on an USACO 2021 problem

Revision en2, by arius1408, 2021-10-07 12:56:51

Well, I've been trying to solve this problem from USACO January Bronze Division. I think this is a LIS-related problem, so I tried using Dilworth's theorem. The thing is, even if I can calculate the length of the longest anti-chain according to the Cowphabet sequence (using binary search like any other LIS problem), I keep getting these annoying Wrong Answers ... Can you tell me where did a make a mistake ? I can't even figure out under what circumstance my approach would fail, but apparently it seem to be a false solution. P/S : Yep, this problem can be solved using an O(N^2) approach, but I'm trying to do it with a O(NlogN) ... Anyway, help pls.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English arius1408 2021-10-07 13:05:05 84 Tiny change: 'elp pls.\nEDIT: Uh' -> 'elp pls.\n\nEDIT: Uh'
en2 English arius1408 2021-10-07 12:56:51 127
en1 English arius1408 2021-10-07 12:47:38 679 Initial revision (published)