Sunday 5 July 2015

ACODE

ALPHACODE

Link to the question : ACODE 

HINT :

We solve the question using dynamic programming. Lets say we check for the string {1,2,3}. We create a array b[] such that b[i] denotes the decryption of the string from (0 to i). For example b[0] denotes the decryption of {1} while b[1] denotes the decryption of {1,2}. We assign b[0] = 1 as it is very clear that the first element can be written in 1 way. Now for the rest of the string we assign b[i]= b[i-1] and we check with the previous element. If the previous and current element both can form a valid character, i.e, if x > 9 & x<27 we add b[i-2] to b[i]. This is done because if we know that we can directly from i-2th position to i-th as i-1 th and i-2 th both can form a character together.

SOURCE CODE:

/* Alphacode */
/* Sushant Gupta */

#include<stdio.h>
#include<string.h>
int main()
{
    char a[5010];
    int i,j;
    scanf("%s",a);
    while(a[0]!='0')
    {

        int n= strlen(a);
        long long int b[n];
        for(i=0;i<n;i++)
            b[i]= 0;
        b[0]= 1;
        for(i=1;i<n;i++)
        {

            j= (a[i-1] - '0') * 10 + (a[i] - '0');
            if(a[i]- '0')
                b[i]= b[i-1];
             if(j>9 && j<27)
             {
                 if(i==1)
                    b[i]= b[i] + 1;
                 else
                    b[i]= b[i] + b[i-2];
             }

        }
        printf("%lld\n",b[n-1]);
        scanf("%s",a);
    }
    if(a[0]=='0')
        return 0;
}

8 comments:

  1. Can you please explain how to do it in top down approach

    ReplyDelete
  2. Wrong solution few test cases are not running

    ReplyDelete
  3. wrong solution

    ReplyDelete
  4. Use 1000000007 to pass all the case. Use the formula (a+b)%m=(a%m+b%m)%m

    ReplyDelete
  5. Can you please share how did you get to the logic? I am new to dynamic programming,any suggestions?

    ReplyDelete
    Replies
    1. lets say, ans[i] stores the final answer that can be obtained till ith index. So ans[0] = 1. Now for other index first calculate manually and then try to come up with a formula such that the ans for index i is dependent on i-1.

      Delete