# CAC1 - EDITORIAL

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

MEDIUM

# EXPLANATION:

Brutally we can try all possible combinations of strings with β1β and β0β and check how many of them give cipher text 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. )

• 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();
}

}

``````

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

2 Likes