towhid1zaman's blog

Spoj- DP
By towhid1zaman, history, 6 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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.

→ Reply