fiwisr's blog

Help needed with this Atcoder problem
By fiwisr, history, 6 years ago, In English

Problem:- https://atcoder.jp/contests/abc122/tasks/abc122_d

I can't figure out what is wrong with my DP solution.

https://p.ip.fi/dn_u

The DP state dp[i][j][k] represents number of strings of length i with last letters j and k. The letters A,G,C and T are 0,1,2 and 3 respectively. It doesn't work from n=4.

Thank you.

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

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

Auto comment: topic has been updated by fiwisr (previous revision, new revision, compare).

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

I don't read your code, but i think 2 last character state is not enough, consider when you want to insert 'C', you need 3 last character to check when the new string is ...A_GC or ...AG_C, for example when n = 4 you will miss this unsatisfied strings: AGGC, AGTC, ATGC.

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

If in case you would like to do it for a larger n you can use matrix exponentiation which gives us a complexity of O(64 * 64 * logn) where 64 x 64 corresponds to a matrix for all possible 3 letter transitions (4^3 as you can fill each position with any of the 4 letters(A, C, G, T)) to all the 3 letter possibilities.

In case if you would like to take a look at the code Solution

→ Reply