Doubt in SPOJ - ACODE

help
,
1

Ques : ACODE
I am a beginner and I tried to solve this ques using DP .It shows correct results for the testcases not involving zeroes in between the i/p number.
For example)
It fails when i/p is:
310
(shows: 2,but ans should be: 1)
10110
(shows:6,but ans should be:1)

And on submission (when I hadn’t thought about the above test cases) shows TLE.
Please help!

My code:

#include <iostream>
#include <string.h>
#define ll long long
using namespace std;

ll l; //the size of i/p array

ll func(int *a, int s, int *dp)
{
    //Base Case:
    if (s >= l)
    {
        return 1;
    }
    //DP Case:
    if (dp[s] != 0)
    {
        return dp[s];
    }
    //Recursive Case:
    ll ans = 0;
    if (s != l - 1)
    {
        int dig = a[s] * 10 + a[s + 1];
        if (dig > 9 && dig <= 26)
        {
            ans += func(a, s + 2, dp);
            dp[s] = ans;
        }
    }

    ans += func(a, s + 1, dp);
    dp[s] = ans;
    return ans;
}

int main()
{
    string n;
    cin >> n;
    while (n != "0")
    {
        l = n.size();
        int *a = new int[l];
        for (int i = 0; i < l; i++)
        {
            a[i] = n[i] - '0';
        }
        int *dp = new int[l]{0};
        cout << func(a, 0, dp) << endl;
        delete[] dp;
        delete[] a;
        cin >> n;
    }
    return 0;
}
2

:pray: Please help…:pray:

3

@ssrivastava990 @ssjgz @cubefreak777 plzz look into this question

4

There’s one video for this on Youtube by pepcoding in their dp series
You can refer Decode Ways Dynamic Programming | Total Ways to Decode a String | Count Encodings - YouTube
But their solution is bottom up
but still for intuition you can refer that .

5

DP state

DP_i \rightarrow \text{Number of interpretations for a prefix of length $i$}

Base Case

→ DP_0=DP_1=1 since there is only one interpretation for prefix of length 1& 0)
→ Question asks us to find DP_N (N is length of string)

Transitions

DP_i=[S_i \neq0]\times DP_{i-1}+[S_{i-1}S_i \le26 \ \text{and} \ S_{i-1}\neq0]\times DP_{i-2}

CODE LINK

1 Like
6

The code inside for loop is complicated!.. :sweat_smile:
Please explain…

7
Code 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

lld n;
lld dp[5001];
string s;
//-4%3=-1


lld fun(int i)
{
    int c=(s[i-1]-'0')*10+(s[i]-'0');
    if(s[i]!='0')
    dp[i]=1;
    if(c<=26&&c>9)
    dp[i]+=1;
    
    for(int i=2;i<n;i++)
    {
        c=(s[i-1]-'0')*10+(s[i]-'0');
        if(s[i]!='0')
        dp[i]+=dp[i-1];
        if(c<=26&&c>9)
        dp[i]+=dp[i-2];
    }
    return dp[n-1];
}

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    //cin>>t;
    string s1="0";
    while(1)
    {
        cin>>s;
        if(s==s1)
        break;
        memset(dp,0,sizeof(dp));
        n=s.size();
        dp[0]=1;
        int res;
        if(s.size()>1)
        res=fun(1);
        cout<<dp[n-1]<<"\n";
        //for(int i=0;i<n;i++)
        //cout<<dp[i]<<" ";
    }
}
8

Oh…Got it!..Thanks :grin:

9

I think this idea is clear that for each i we have two choices, i.e. either we club up the last 2 indices (i & i-1) and treat them as a single character or we consider only the last letter as a single entity hence DP_i=DP_{i-1}+DP_{i-2} but there are a few edge cases that we need to cover.

  1. If S_{i-1}S_i is greater than 26 then we can’t include DP_{i-2} as there’s no character that is assigned a value of 26
  2. if S_i=0 then we know that there’s no character which is assigned a value of 0 hence this zero is bound to be used in conjunction with S_{i-1} character to give S_{i-1}S_i=10 or 20 hence we won’t include DP_{i-1} and only include DP_{i-2} (After checking if the value is less than 26 of course)
  3. If S_{i-1}=0 then we know that that we must have included S_{i-1} in conjunction with S_{i-2} to make 10 or 20 as discussed in the above point. So we cannot club up S_{i-1} & S_i to make a number like 07 or 08 etc… hence we don’t include DP_{i-2}.
code 
#include "bits/stdc++.h"
using namespace std ;

int main(){
  string s   ;
  cin>>s  ;
  while(s!="0"){
  	int n = s.size() ;
  	vector<int>dp(n+1) ;
  	dp[0]=dp[1]=1;
    for(int i=2;i<n+1;i++){
        int d = 10*(s[i-2]-'0')+s[i-1]-'0' ; // S_{i-1}S_i
        if(s[i-1]!='0')
	    dp[i]+=dp[i-1] ;
        if(d<=26&&s[i-2]!='0')
	    dp[i]+=dp[i-2] ;
     }
     cout << dp[n] << '\n' ;
     cin>>s  ;
  }
}
10

Nicely explained!..Thanks :smile: