Seif's blog

Help .. WA on an easy interesting GYM problem
By Seif, history, 11 years ago, In English

My solution in 100651A - ALPHACODE - Alphacode got WA on test 2 .. and this is my code : http://ideone.com/GwzmWe can anyone provide me a test case to drop this? thanks on advance.

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

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

Can you please explain your solution's logic? I know only another solution.

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

    Ok , now i got why it was WA , because of zeros like 101 , 100 . it's accepted now :)) actually My idea comes due to some observations ! if we have something like that 25925925 .. let's call the number of possible chars to get from a segment X .. now it's cleat that 25 gives us 2 different chars {2 5 , 25} .. so by combinations ans = X * 3 = 2 * 2 * 2 so what about that 1111 ? it's fib[5] why ? i don't know ! so for n consecutive chars you have X = fib[n+1] the result becomes X1 * X2 * ... I'm trying to find a proof for that ! :( final code : http://ideone.com/nkIXN5

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

      My solution is similar, may be it will help you to prove your:

      Let dp[i] be the answer for prefix of length i.

      At first dp[i] = 0. Then:

      if (a[i] > 0) dp[i] += dp[i - 1];;
if (10*a[i - 1] + a[i] <= 26 && ... > 0) dp[i] += dp[i - 2];

      You can see that this formulas has something similar to Fibbonacci numbers

      → Reply