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

Spoj- DP
Автор towhid1zaman, история, 5 лет назад, По-английски

Can anyone help me with this problem? COLORSEG — Coloring Segments

trying a long time didn't find any solution/hint.

Will be grateful if anyone can help. Thank You.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

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

The key is in your dp state to not just hold the color of your current segment, but of the current segment and previous segment.

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

This question can be solved easily using dp with states 1. index , colour of last segment, colour of last to last segment. And for each state you will need to run a loop from 1 to m too .

So eventually adding this to test cases will lead to a O(T*N*M*M*M) solution ,but here we notice that the test cases aren't actually till 2500, since we know that the values of m ranges from 1 to 50.

So if we precompute for all m from 1 to 50, we solve the test case issue.

Here is my working code . Although I am not sure about the exact time complexity due to the coprime thing.

→ Ответить