amolsharma99's blog

Special String :Spoj
By amolsharma99, 14 years ago, In English

Plz help me in solving  a simple problem on spoj http://www.spoj.pl/problems/MAIN113/

i am not able to conclude a general formula for any 'n'........i derived one but found it wrong...plz some one guide !!

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

Comments Comments (5)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think there is no general formula, at least I didn't find one at OEIS.

This is a typical dynamic programming problem however.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How is this a dp problem...what will be the substructure....i'm not able to figure out...plz help !!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Look at the example case, and think what happens if you add a letter.
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The total number of string that are speacial will always be 6 ?? since the number of ways to select 1st character are 3 and for 2nd 2 and 3rd 1 and once we select a letter then the letter on i+3th position should be the same as ith letter.so what I'm doing is, calculating the number of total strings of length n made using X,Y,Z ,. 3^n and substracting it from 6.But i'm getting wrong answer.Here is the code http://ideone.com/UuTLaj .Pls tell me where I'm wrong in this approach.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, is not always 6.

    Why i+3th position should be the same as ith letter? YZXXYY is special

    → Reply