### seif's blog

By seif, history, 4 years ago, , 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.  Comments (4)
 » Can you please explain your solution's logic? I know only another solution.
•  » » 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 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 →   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
•  » » » » Thanks a lot , it helps me