seif's blog

By seif, history, 4 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

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

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

  • »
    »
    4 years ago, # ^ |
      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

    • »
      »
      »
      4 years ago, # ^ |
      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

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

        Thanks a lot , it helps me