nightwing123's blog

SPOJ dp problem COLORSEG
By nightwing123, history, 7 years ago, In English

Can anyone help me with this problem? http://www.spoj.com/problems/COLORSEG/

It seems it requires some state space reduction/some clever optimisation or an entirely different approach.Have been trying this for quite a long time and no solution/hints are available anywhere.Would be grateful if anyone can help

Tags dp, spoj
  • Vote: I like it
  • +3
  • Vote: I do not like it

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

What's wrong with dp(i, c1, c2) equals number of ways to properly assign colors to the first i segments in such a way that i - 2-th segment will receive color c2 and i - 1-th segment — color c1.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Also note that there are t <  = 2500 test cases and time limit is 1 second. Each case runs in O(50 * 50 * 50) = O(1.25 * 1005), so solving all test cases should lead to TLE with that dp recurrence.

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

      There is only 50 different test cases each with his own value of M, but N is meaningless since we can make precalc with N = 50.

      → Reply