Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

amolsharma99's blog

Special String :Spoj
By amolsharma99, 15 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?
15 years ago, hide # |
 
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
15 years ago, hide # |
 
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
»
10 years ago, hide # |
← 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
  • »
    »
    10 years ago, hide # ^ |
     
    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