damn_me's blog

SPOJ PROBLEM LIS2
By damn_me, 10 years ago, In English

Can someone provide some hint for solving this prbolem of spoj www.spoj.com/problems/LIS2/. The approach I am trying is very similar to the LIS dp solution(O(Nlogn)). But my solution doesnot give correct answer for all cases I am testing upon.

Here is the rough idea of what I am doing : http://ideone.com/kyIJMf

Tags spoj, dp
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So I'm not the only one... I've tried it too, but also haven't got AC yet. Looks like the standard LIS problem modified by only int pairs due to the condition "A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2." So if it couldn't be handled like the standard LIS, I'm really out of ideas.

→ Reply