shuprog1's blog

By shuprog1, 10 years ago, In English

Two letter strings are the strings consisting of only two letters "X" and "Y". A string is "super two letter string" if

a) It does not have leading "X" letters. b) It does not contain P consecutive "X" letters. Your task is to find total number of Super two letter strings of length N.

How to identify the states of dynamic programming for the above problem? Problem Link: Super two letter strings

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

let ind : the current index we are in at this state

let con : number of consecutive "X" characters we had in our state

let f(ind, con) be our answer

of-course we will put "Y" in index 1

f(ind, con >= p) = 0

f(N, con) = 1 + (con < p — 1)

f(ind, con) = f(ind + 1, con + 1) + f(ind + 1, 0)

our answer would be f(2, 0)

also don't forget to mod after each operation

UPD : updated the basecases

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

Consider the process of creating the sequence. There are many ways to define states however you like. Here is one way: Let cnt(N) be the number of string with the properties mentioned above. The recurence looks as follows:

cnt(N) = cnt(N - 1) + cnt(N - 2) + ... + cnt(N - P)

Why so you may ask. First we consider that we place and Y on position N, then we just need to consider cnt(N - 1)-the strings of length N - 1. Now consider placing a continuous seqence of X of length L = 1, 2, ..., P - 1. We place a sequence of length L on position N, so we are left with a string of length N - L. Now we place an Y on position N - L and we add to cnt(N) the value of cnt(N - L - 1), of course only if N - L - 1 ≥ 0.

Why is this correct? Because in this way we "cover" the set of all possible solutions by considering such a construction process. I like to view this as a bijection from the set of all possible strings that hold a certain property to the set of all possible constructions.(each string from the set of solution has an unique representation with the operations we used in the recurence above)

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

Can you please explain what is happening in this solution (Link)?