terserah's blog

LIS problem
By terserah, 11 years ago, In English

Is it possible to solve Uva 11790 using O(n log k) LIS? I kept getting WA using O(n log K) LIS, so i change to O(n^2) and get accepted. The problem's constraint is not clear though :(

Link : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2890

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

If you have a correct solution, you can make a stress test and find a test where it's wrong.

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It is possible to solve problem in N Log N using segment tree with queries Add(left = X, right = n, value = DX) and GetMax(left = 0, right = X). You don't need LIS.

→ Reply