Блог пользователя crbonilha

UVa 10949 — Kids in a Grade — solution?
Автор crbonilha, 9 лет назад, По-английски

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?

Теги uva, lcs, dp, lis
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить