crbonilha's blog

UVa 10949 — Kids in a Grade — solution?
By crbonilha, 9 years ago, In English

Statement link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1890

Brief: It's a LCS problem, but the constraints are too high for the DP approach (O(N * M), where N and M <= 20000). The conversion to a LIS, which could lead to a O(N * lg M), is impractical because both arrays contain repeated elements.,

Any suggestions?

Tags uva, lcs, dp, lis
  • Vote: I like it
  • +5
  • Vote: I do not like it

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

Looks like, you can just change elements to pair<element,number_of_this_type_of_elements>

For example, {1,2,3,3,2,3,2,4,1} will be {1(1),2(1),3(1),3(2),2(2),3(3),2(3),4(1),1(2)} and use standard pair comporator when counting LIS

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't really like this problem. It is standard LCS, but you need to translate the algorithm into bitwise operations to make it fit within time limit.

See here for a more precise description on how to do it and here for some AC code.

→ Reply