towhid1zaman's blog

Spoj- DP
By towhid1zaman, history, 4 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

»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    How to solve this if we have only one condition (i < j < k)?

    → Reply
»
4 years ago, # |
  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