CAC1 - EDITORIAL

PROBLEM LINK:

Practice Link
Cook-a-bit

Author: Ishank Soni
Editorialist: Ishank Soni
Tester: hellb0y_suru

PROBLEM:

A string S is converted to string cipher according to the following algorithm :

Encryption (S, N )
{
   cipher = S
   for i β†’ 1 to N : 
       j = ( i == N ) ? 1 : i+1
       if ( S[i] == '1' and S[j] == '0' ) :
           cipher[i] = '0'
           cipher[j] = '1'

   return cipher        
}

You are given a cipher string. Find the number of S that will generate the given cipher string.

PREREQUISITES:

  • Dynamic Programming

DIFFICULTY:

MEDIUM

EXPLANATION:

Brutally we can try all possible combinations of strings with β€˜1’ and β€˜0’ and check how many of them give cipher text :slight_smile: Unfortunately, we can’t do this with a string of large size.

So another less intuitive solution uses dynamic programming as follows.

(Take a pen and paper, things can be a little messy down there. :wink:)

  • Note: I have used 0 based indexing below.

We start with adding the first character of the given string to the string as the last character. i.e. cipher += cipher[0]. This will ensure that the string becomes cyclic.

First observation is that at position i in cipher string, if cipher[i] is β€˜1’. Then in the original string either S[i] =1 and S[i+1] =1 or S[i -1] = 1 and S[i] = 0. Similary if cipher[i] is β€˜0’. Then in the original string either S[i-1] =0 and S[i] =0 or S[i] = 1 and S[i+1] = 0. The key point here to observe is that 0 in original string may only change depanding upon previous character. While 1 in original string may only change depending upon next character.

We define a dp state dp[i][0] as the number of strings S with length i+1 and last bit β€˜0’ such that S gives C, and dp[i][1] as the number of strings S with length i+1 and last bit β€˜1’ such that S_{i-1} gives C_{i-1}. Here we take S_{i-1} because last bit β€˜1’ may or maynot change, it depnads on β€˜i+1 -th’ bit.

According to above dp[n][0] ( n is size of given string) should give total number of strings S such that size is n+1, ends at β€˜0’ and S give cipher. Also note that S[n], which is last charecter must be equal to first character so, S[0] must be β€˜0’. Thus dp[n][0] is the total possible strings that starts with β€˜0’ and generate given cipher text.

Now dp[n][1] gives the number strings S of length n+1 such that it ends with β€˜1’ and S_{n-1} give Cipher_{n-1} (which is given cipher). Also Adding or removing last β€˜1’ doesn’t affect conversion of S_{n-1} to Cipher_{n-1}. Thus dp[n][1] is the total possible strings that starts with β€˜1’ and generate given cipher text.

Below is how the transition in dp states could be done.
For simplicity let,
dp[i][0] = n0
dp[i][1] = n1
n0 and n1 are according to above rule.

If cipher [i] = 1, then we can add 1 to all strings i.e all n1 and n0 strings, as for n0 the last character is β€˜0’ and they all already give cipher_{i} so adding β€˜1’ would not affect. For n1 strings ,we can surely add β€˜1’ as we want last bit of all n1 string to not change (S[i] = cipher [i] =1). Thus dp[i+1][1] = n0 + n1. Now come to adding β€˜0’ at (i+1) position. We can only add β€˜0’ to n0 strings only when if cipher[i+1] is β€˜0’, because we can’t get β€˜1’ at cipher[i+1] in given conditions. Ofcourse we can’t add β€˜0’ to n1 as, this will swap last β€˜1’ in n1 with 0 and we can’t get cipher[i] as 1. So if cipher [i+1] is β€˜0’ dp[i+1][0] = dp[i][0] else dp[i+1][0] will be 0.

Similarly,
If cipher[i] =0 , Then we can add β€˜1’ to only n0 strings, because in n1 strings last bit β€˜1’ ( S[i] ) can’t change to 0. if we add β€˜1’. so dp[i+1][1] = dp[i][0].Now We want to add 0, If we add β€˜0’ to n1 string, then last β€˜1’ at pos i will swap to pos i+1, so we must have cipher[i+1] = , And if we add β€˜0’ to n1 strings then cipher[i+1] must be β€˜0’. Thus if cipher[i+1] =1 then dp[i+1][0] = dp[i][1], if cipher[i+1] = 0, then dp[i+1][0] = dp[i][0].

Let β€˜Ans’ be the total number of all possible original strings. β€˜Ans’ may have some string that starts with β€˜0’ and some string that starts with β€˜1’. We can calculate them separately with base case dp[0][1] =1 for the first bit as 1 and dp[0][0] =1 for first bit as 0, finally add them together.

Do checkout the below code for better understanding.

SOLUTION:

Commented and easy code in C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
#define inf 1e17
#define _fast_ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll _power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll _power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1;a *= a; a %= mod;} return p % mod;}
ll _gcd(ll a,ll b) { return b?_gcd(b,a%b):a;}
ll _max(ll a,ll b){ if(a>b){return a;}else{ return b;}}
ll _modI(ll a, ll m){ return _power(a, m - 2, m);}
void _out(vector<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
void _out(vector<pair<ll,ll>> par ){for(auto i:par){cout<<i.first<<" "<<i.second<<"\n";}}
void _out(set<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}

///////////////////////////////////////////////////////////////////////////////////////////
// Main code------------------------------

// ll mod = 998244353;
ll mod = 1000000007;
const ll N = 100000;


ll dp[N][2];

// This code will not give AC, as modulo operation is not performed.
// Only to understand easily.

void solve(){
   int n;
   string cipher;
   ll ans = 0;

   cin>>cipher;
   n = cipher.size();
   cipher += cipher[0];

   for(int firstBit = 0; firstBit <= 1; firstBit++){

       memset(dp, 0, sizeof(dp));

       // Set First bit to 'firstBit' {0 or 1}.
       dp[0][firstBit] = 1;

       // Now calculate dp[n][firstBit] and add it to ans.
       for(int i = 0; i < n; i++){

           // if cipher[i] is 1 we can add '1' to all previous string Else only to string ending at 0
           if (cipher[i] == '1')  //11 - > 11
               dp[i+1][1] += dp[i][1];

           dp[i+1][1] += dp[i][0]; //01 - > 01


           // Condition for adding 0.

           // If cipher[i] = 1 or 0 and cipher[i+1] is 0.
           if (cipher[i+1] == '0')
               dp[i +1 ][0] += dp[i][0]; //00 -> 00


           // If cipher[i] is 0 and cipher[i+1] is 1.
           else if (cipher[i] == '0') // 10 -> 01
               dp[i+1][0] += dp[i][1];
           
       }
       ans += dp[n][firstBit];
   }

   cout << ans << "\n";
}

int main()
{
   int t;
   cin>>t;
   while(t--){
       solve();
   }

}


setter's AC code in C++
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f(n) for(ll i=0;i<n;i++)
#define inf 1e17
#define _fast_ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll _power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll _power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1;a *= a; a %= mod;} return p % mod;}
ll _gcd(ll a,ll b) { return b?_gcd(b,a%b):a;}
ll _max(ll a,ll b){ if(a>b){return a;}else{ return b;}}
ll _modI(ll a, ll m){ return _power(a, m - 2, m);}
void _out(vector<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}
void _out(vector<pair<ll,ll>> par ){for(auto i:par){cout<<i.first<<" "<<i.second<<"\n";}}
void _out(set<ll> arr){ for(auto i:arr){cout<<i<<' ';}cout<<"\n";}

// ll mod = 998244353;
ll mod = 1000000007;
const ll N = 100000;

ll dp[N][2];

void solve(){
   int n;
   string s;
   ll ans = 0;
   memset(dp,0,sizeof(dp));
   cin>>s;
   n = s.size();
   s+= s[0];
   dp[0][1] = 1;

   f(n){

       if(s[i] == '1')
           dp[i+1][0] = dp[i][0] + dp[i][1];
       else
           dp[i+1][0] = dp[i][1];

       if (s[i] =='0' && s[i+1] == '1')
           dp[i+1][1] = dp[i][0];

       else if (s[i+1] == '0')
           dp[i+1][1] = dp[i][1];

       dp[i+1][0] %= mod;
       dp[i+1][1] %= mod;
   }
   ans += dp[n][1];


   memset(dp, 0, sizeof(dp));
   dp[0][0] = 1;
   // cout<<ans<<"\n";

   f(n){
       if (s[i]=='1')
           dp[i+1][0] = dp[i][0] + dp[i][1];
       else
           dp[i+1][0] = dp[i][1];
       if (s[i] == '0' && s[i+1] == '1')
           dp[i+1][1] = dp[i][0];
       else if (s[i+1] == '0')
           dp[i+1][1] = dp[i][1];

       dp[i+1][0] %= mod;
       dp[i+1][1] %= mod;
   }
   ans += dp[n][0];

   ans %= mod;
   cout<<ans<<"\n";
   return;
}

int main()
{
   int t;
   cin>>t;
   while(t--){
       solve();
   }

}


:grin: Feel free to ask any query. If the given explanation is confusing we can discuss it :slightly_smiling_face: Hope you like the Problem and editorial.

2 Likes