CCHO- Editorial

editorial
, , ,
1

PROBLEM LINK:

Code Battle: Holi Edition

Author: Aniket Sood
Tester: Rahul Sharma
Editorialist: Saksham Aggarwal

DIFFICULTY:

MEDIUM

PREREQUISITES:

Recursion, DP

PROBLEM:

Given a string s of digits from 1 to 9, in which digits 4 and 9 are replaced by 22 and 33 respectively, so find the number of combinations which can result in the formation of the given string by changing the digits 4(9) to 22(33) or leave it as 4(9).

QUICK EXPLANATION:

Apply DP in a bottom up manner to store possible number of strings.

EXPLANATION:

  1. First thing to notice is that if the string contains 4 or 9, then the answer is 0, because the manipulated string cannot contain these digits.

  2. Then consider the string. If there are 2(or more) consecutive 2s or 3s, then one possible original string is obtained by replacing 2 of those strings by their square, another possible original string by keeping them in same form, i.e., 22 or 33. Thus we get 2 possibilities for each such 2 consecutive 2s or 3s.

  3. Then, store the number of these possibilities in a DP array. Create a DP array with all elements as 1. In a loop, check the elements in the string. Each time there are 2 consecutive 2s or 3s, then DP[i]=DP[i-1]+DP[i-2]. Else, DP[i]=DP[i-1].

  4. The total possible strings will be the DP[n], where n is the size of string.

ALTERNATE EXPLANATION:

Alternatively, this can also be done by making groups of consecutive 2s and 3s. count the number of 2s and 3s in each group and use counting principle. Further implementation is left to reader for the sake of exploring.

COMPLEXITIES:

TIME: O(N) ,where N is the size of string.

SPACE: O(N), where N is the size of string.

SOLUTIONS:

Setter's Solution 
//Author:- algokiller**
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define set(x) memset(x, 0, sizeof(x))
#define iter(it, a) for (auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef pair<int, int> pii;
typedef pair<int, int> pl;
typedef vector<int> vi;
typedef vector<int> vl;
typedef vector<pii> vpii;
const long long INF=1e18;
const long long MOD = 1e9+7;

void solve(){
    string s;
    cin >> s;    
    for (char x : s)
    {
        if (x == '4' || x == '9')
        {
            cout << 0 << '\n';
            return ;
        }
    }
    
    int n = s.size();
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = dp[i - 1];
        if (s[i - 1] == s[i - 2] && (s[i - 1] == '2' || s[i - 1] == '3'))
            dp[i] = (dp[i] + dp[i - 2]) % MOD;
    }
    
    cout << dp[n] << '\n';
}
int32_t main()
{
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r", stdin);
//	freopen("output.txt","w",stdout);
//#endif
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}
Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
bool check(string str)
{
	for (int i = 0; i < str.length(); ++i)
		if(str[i] == '4' || str[i] == '9')
			return false;
	return true;
}
long long int countStringsIterative(string str)
{
	long long int n = str.length();
	long long int dp[n] = {0};
	dp[0] = dp[1] = 1;
	if((str[0] == '2' && str[1] =='2') || (str[0] == '3' && str[1] == '3'))
		dp[1] += 1;
	for(int i = 2; i < n; ++i)
	{
		dp[i] = dp[i-1];
		if((str[i] == '2' && str[i-1] =='2') || (str[i] == '3' && str[i-1] == '3'))
			dp[i] = (dp[i] % mod + dp[i-2] % mod) % mod;
	}
	return dp[n-1];
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string str;
		cin >> str;
		if(check(str))
			cout << countStringsIterative(str) << endl;
		else
			cout << 0 << endl;
	}
	return 0;
}
3 Likes