Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and Two String CodeChef Solution
Problem – Chef and Two String CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Chef and Two String CodeChef Solution in C++17
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define rsrt(v) sort(v.begin(), v.end(), greater<int>())
#define srt(v) sort(v.begin(),v.end())
#define all(x) (x).begin(),(x).end()
#define ll long long
#define int long long
ll md = 1000000007;
int inf = 1e18;
using namespace std;
template <typename T>
T pw(T a, T b) {T c = 1, m = a;while(b) {if (b & 1) c=(c*m); m=(m*m); b/=2;} return c;}
template <typename T>
T ceel(T a, T b){if (a%b==0) return a/b; else return a/b + 1;}
template <typename T>
T gcd(T a, T b) {return b == 0 ? a : gcd(b, a % b);}
ll pwmd(ll a, ll b) {ll c = 1, m = a%md;while(b) {if (b & 1) c=(c*m)%md; m=(m*m)%md; b/=2;} return c;}
ll modinv(ll n){return pwmd(n, md - 2);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r){ // gives random number in [l,r]
return uniform_int_distribution<ll>(l, r)(rng);
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '{' << p.first << ", " << p.second << '}';
}
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
os << '[';
for (auto it = c.begin(); it != c.end(); ++it)
os << &", "[2 * (it == c.begin())] << *it;
return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...) \
_NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0) \
(MACRO, ##__VA_ARGS__)
// #ifdef LOCAL
#define out(x) #x " = " << x << "; "
#define dbg(...) \
cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"
// #else
// #define debug(...) 42
// #endif
//--------------------------------theartofwar-------------------------------------------//
bool check(int j, int k, char c1, char c2) {
return !((c1 == '1' && j == 1) || (c1 == '2' && j == 2) || (c2 == '1' && k == 1) || (c2 == '2' && k == 2));
}
int go(string a, string b) {
int n = a.length();
if (n < 2) return 2;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(3)));
dp[0][a[0] == '2'][b[0] == '2']++;
swap(a[0], b[0]);
dp[0][a[0] == '2'][b[0] == '2']++;
for (int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (check(j, k, a[i], b[i])) {
auto &temp = dp[i][(a[i] == '2' ? j + 1 : 0)][(b[i] == '2') ? k + 1 : 0];
if (i < n - 1 || !((a[i] == '1' && j != 0) || (b[i] == '1' && k != 0))) temp += dp[i - 1][j][k];
if (temp >= md) temp -= md;
}
if (check(j, k, b[i], a[i])) {
auto &tmp = dp[i][(b[i] == '2') ? j + 1 : 0][(a[i] == '2') ? k + 1 : 0];
if (i < n - 1 || !((b[i] == '1' && j != 0) || (a[i] == '1' && k != 0))) tmp += dp[i - 1][j][k];
if (tmp >= md) tmp -= md;
}
}
}
}
int ans = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) ans = (ans + dp[n - 1][i][j]) % md;
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t; cin >> t;
while (t--) {
string a, b; cin >> a >> b;
cout << go(a, b) << "\n";
}
}
// 11, 12, 21, 22Chef and Two String CodeChef Solution in C++14
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define double long double
#define F first
#define S second
#define pb push_back
#define ll long long int
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vd vector<double>
#define vvi vector<vector<int>>
#define vvd vector<vector<double>>
#define vii vector<pair<int, int>>
#define vvb vector<vector<bool>>
#define print(x) (cout << x << endl)
#define all(v) v.begin(), v.end()
#define mod 1000000007
#define mod1 1000000009
#define mod2 998244353
#define pii pair<int, int>
#define setbits(x) __builtin_popcountll(x) // count set bits(1)
#define zerobits(x) __builtin_ctzll(x) // 1010000 (ans=4) because 4 zeros after 1st one
#define endl "\n"
#define sz(a) (int)a.size()
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = a; i >= b; i--)
#define INF 9e18
#define nINF -9e17
#define INTMAX 1e9 + 10
// const int N = 2000005;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
for (int i = 0; i < v.size(); ++i)
{
os << v[i] << " ";
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
for (int i = 0; i < v.size(); ++i)
{
for (int j = 0; j < v[i].size(); j++)
os << v[i][j] << " ";
cout << endl;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<pair<T, T>> &v)
{
for (int i = 0; i < v.size(); ++i)
{
os << v[i].F << " " << v[i].S << endl;
}
return os;
}
/* end of template */
// **---__________________________________________________________________---** //
// 679
// global round 11
// 672
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
int dp[(int)1e5][3][3];
int fin(int i, int cnt2a, int cnt2b, string &a, string &b, int n)
{
if (i == n - 1)
{
if (cnt2a > 0 || cnt2b > 0)
{
return 0;
}
return 2;
}
if (dp[i][cnt2a][cnt2b] != -1)
return dp[i][cnt2a][cnt2b];
int ret = 0;
if (a[i] == '1' && b[i] == '1')
{
if (cnt2a == 1 || cnt2b == 1)
{
ret += 0;
}
else
{
ret = (2ll * fin(i + 1, 0, 0, a, b, n)) % mod;
}
}
else if(a[i] == '2' && b[i] == '2'){
if (cnt2a == 2 || cnt2b == 2)
{
ret += 0;
}
else
{
ret = (ret + 2ll * fin(i + 1, cnt2a + 1, cnt2b + 1, a, b, n)) % mod;
}
}
else
{
if (cnt2a == 1 || cnt2b == 2)
{
ret += 0;
}
else
{
ret = (ret + fin(i + 1, 0, cnt2b + 1, a, b, n)) % mod;
}
if (cnt2a == 2 || cnt2b == 1)
{
ret += 0;
}
else
{
ret = (ret + fin(i + 1, cnt2a + 1, 0, a, b, n)) % mod;
}
}
// else if (a[i] == '2' && b[i] == '1')
// {
// if (cnt2a == 2 || cnt2b == 1)
// {
// ret += 0;
// }
// else
// ret = (ret + fin(i + 1, cnt2a + 1, 0, a, b, n)) % mod;
// if (cnt2a == 1 || cnt2b == 2)
// {
// ret += 0;
// }
// else
// {
// ret = (ret + fin(i + 1, 0, cnt2b + 1, a, b, n)) % mod;
// }
// }
return dp[i][cnt2a][cnt2b] = ret;
}
void solve()
{
string a, b;
cin >> a >> b;
memset(dp, -1, sizeof(dp));
int n = a.length();
int ans = fin(0, 0, 0, a, b, n) % mod; // ind,cnt2a,cnt2b
cout << ans << endl;
}
/*
abbacca
abcbacbca
*/
// **---__________________________________________________________________---** //
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
clock_t begin = clock();
#endif
int T = 1;
// factorial();
cin >> T;
// //
for (int x = 0; x < T; x++)
{
// if (x <= 4)
solve();
// else
// {
// string s;
// cin >> s;
// if (x == 865)
// {
// cout << s << endl;
// }
// }
}
#ifndef ONLINE_JUDGE
clock_t end = clock();
cerr << "Time : " << (double)(end - begin) / CLOCKS_PER_SEC << "s\n";
#endif
return 0;
}Chef and Two String CodeChef Solution in PYTH 3
t=int(input())
x=1000000007
i=0
flag=1
count1,count2=0,0
val=1
while(t):
t-=1
a=input()
b=input()
n=len(a)
if(n==1):
print ("2")
if(n>=2):
if( a[n-2]=="2" or b[n-2]=="2"):
print ("0")
else:
i=0
while(i<=n-2):
if(count1==0 and count2==0):
if(a[i]==b[i]):
if(a[i]=="2"):
if(a[i+1]=="2" and a[i+2]=="1" and b[i+1]=="2" and b[i+2]=="1"):
val=(8*val)%x;
i=i+2;
else:
print ("0")
flag=0
break
elif(a[i]=="1"):
val=(2*val)%x;
elif(a[i]=="1" and b[i]=="2"):
count2+=1;
val=(2*val)%x;
elif(a[i]=="2" and b[i]=="1"):
count1+=1;
val=(2*val)%x;
elif(count1==0 and count2 ==1):
if(a[i]=="1" and b[i]=="1"):
print ("0")
flag=0
break
elif(b[i]=="2" and a[i]=="2"):
count2+=1;
count1+=1;
val=(2*val)%x;
else:
count2+=1
elif(count1==0 and count2==2):
if(a[i]=="1" and b[i]=="1"):
val=(2*val)%x;
count2=0;
elif(a[i]=="2" and b[i]=="2"):
print ("0")
flag=0
break
else:
count2=0;
count1+=1;
elif(count1==1 and count2==0):
if(a[i]=="1" and b[i]=="1"):
print ("0")
flag=0
break
elif(a[i]=="2" and b[i]=="2"):
count2+=1;
count1+=1;
val=(2*val)%x;
else:
count1+=1
elif(count1==1 and count2==2):
if(a[i]==b[i]):
print ("0")
flag=0
break
else:
count1+=1;
count2=0;
elif(count1==2 and count2==0):
if(a[i]=="1" and b[i]=="1"):
val=(2*val)%x;
count1=0;
elif(a[i]=="2" and b[i]=="2"):
print ("0")
flag=0
break
else:
count1=0;
count2+=1;
elif(count1==2 and count2==1):
if(a[i]==b[i]):
print ("0")
flag=0
break
else:
count2+=1;
count1=0;
elif(count1==2 and count2==2):
if(a[i]==b[i] and a[i]=="1"):
val=(2*val)%x;
count1=0;
count2=0;
else:
print ("0")
flag=0
break
i+=1
if(flag!=0):
print ((val*2)%x)
val=1
count1=0
count2=0
flag=1
Chef and Two String CodeChef Solution in C
#include<stdio.h>
#include<math.h>
#include<string.h>
char a[100001],b[100001];
long long int l,i,ans;
int main()
{
long long int t,pp;
scanf("%lld",&t);
while(t--)
{
scanf("%s%s",a,b);
l=strlen(a);
for(i=0;i<l-1;i++)
{
if(a[i]!=b[i])
{
if(i<=1)
{
a[i]='2';b[i]='1';
}
else if(a[i-1]=='2'&&a[i-2]=='2')
{
a[i]='1';b[i]='2';
}
else if(a[i-1]=='2'&&a[i-2]=='1')
{
a[i]='2';b[i]='1';
}
else if(b[i-1]=='2'&&b[i-2]=='2')
{
a[i]='2';b[i]='1';
}
else if(b[i-1]=='2'&&b[i-2]=='1')
{
a[i]='1';b[i]='2';
}
}
}
//printf("%s\n%s\n",a,b);
pp=0;
for(i=0;i<=l-2;)
{
if(b[l-2]=='2')
{
pp=1;
break;
}
else if(b[i]=='1')
{
i++;
}
else if((b[i]=='2'&&b[i+1]=='2'&&b[i+2]=='1'))
{
i=i+3;
}
else
{
pp=1;
break;
}
}
if(pp!=1)
{
for(i=0;i<=l-2;)
{
if(a[l-2]=='2')
{ //printf("p1\n");
pp=1;
break;
}
else if(a[i]=='1')
{
i++;
}
else if((a[i]=='2'&&a[i+1]=='2'&&a[i+2]=='1'))
{
i=i+3;
}
else
{
pp=1;
break;
}
}
}
if(pp==1)
{
printf("0\n");
}
else
{
ans=2;
for(i=0;i<l-1;)
{
if(a[i]=='1'&&(a[i]==b[i]))
{
ans=(ans*2)%1000000007;
i++;
}
else if(a[i]==b[i]&&a[i+1]=='2')
{
ans=(ans*4)%1000000007;
i=i+2;
}
else
{
while((i<l-1)&&(a[i]=='2'||b[i]=='2'))
{
if(a[i]==b[i])
{
ans=(ans*2)%1000000007;
}
i++;
}
ans=(ans*2)%1000000007;
}
}
printf("%lld\n",ans);
}
}
return 0;
} Chef and Two String CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
/**
* Created by Yoav Tamir on 3/21/2017.
*/
public class Main {
static final int MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(reader.readLine());
for (int i = 0; i < t; i++) {
String a = reader.readLine();
String b = reader.readLine();
long ans = 1;
int len = a.length();
int twoNum = 0;
if(len == 1){
ans = 2;
writer.write(String.valueOf(ans));
writer.newLine();
writer.flush();
continue;
}
if(!(b.charAt(len - 2) == a.charAt(len - 2) && a.charAt(len - 2) == '1')){
ans = 0;
writer.write(String.valueOf(ans));
writer.newLine();
writer.flush();
continue;
}
ans = 2;
int j = 0;
while(j < len - 2) {
if(twoNum == 0){
if(b.charAt(j) == a.charAt(j) && a.charAt(j) == '1'){
ans *= 2;
ans %= MOD;
j++;
}
else if(b.charAt(j) == a.charAt(j) && a.charAt(j) == '2'){
if(b.charAt(j+1) == a.charAt(j+1) && a.charAt(j+1) == '2'
&& b.charAt(j+2) == a.charAt(j+2) && a.charAt(j+2) == '1'){
j += 3;
ans *= 8;
ans %= MOD;
}else{
ans = 0;
break;
}
}else if(b.charAt(j) != a.charAt(j)){
j++;
twoNum = 1;
ans *= 2;
ans %= MOD;
}else{
ans = 0;
break;
}
}else if(twoNum == 1){
if(b.charAt(j) == a.charAt(j) && a.charAt(j) == '2'){
ans *= 2;
ans %= MOD;
twoNum = 3;
j++;
}else if(b.charAt(j) != a.charAt(j)){
twoNum = 2;
j++;
}else{
ans = 0;
break;
}
}else if(twoNum == 2){
if(b.charAt(j) == a.charAt(j) && a.charAt(j) == '1'){
j++;
ans *= 2;
ans %= MOD;
twoNum = 0;
}
else if(b.charAt(j) == '1' || a.charAt(j) == '1'){
j++;
twoNum = 1;
}else{
ans = 0;
break;
}
}else {//twoNum == 3
if(b.charAt(j) != a.charAt(j)){
j++;
twoNum = 2;
}else{
ans = 0;
break;
}
}
}
if(twoNum == 1 || twoNum == 3){
ans = 0;
}
if(j == len - 2){
ans *= 2;
ans %= MOD;
}
writer.write(String.valueOf(ans));
writer.newLine();
writer.flush();
}
}
}Chef and Two String CodeChef Solution in PYTH
# cook your code here
for i in range(input()):
s1 = list(raw_input().strip())
s2 = list(raw_input().strip())
s1.insert(0,'1')
s1.insert(0,'1')
s2.insert(0,'1')
s2.insert(0,'1')
count = 0
esc = False
chain = False
n = len(s1)
for j, c in enumerate(s1):
if j == 0 or j==n-1 or j==1:
continue
req = {'1req1': False, '1req2': False, '1has2': False, '2req1': False, '2req2': False, '2has2': False}
if s1[j - 1] == '2' and s1[j - 2] == '2':
req['1req1'] = True
if s1[j] == '2':
req['1has2'] = True
elif s1[j - 1] == '2' and s1[j - 2] == '1':
req['1req2'] = True
if s1[j] == '2':
req['1has2'] = True
else:
if s1[j] == '2':
req['1has2'] = True
if s2[j - 1] == '2' and s2[j - 2] == '2':
req['2req1'] = True
if s2[j] == '2':
req['2has2'] = True
elif s2[j - 1] == '2' and s2[j - 2] == '1':
req['2req2'] = True
if s2[j] == '2':
req['2has2'] = True
else:
if s2[j] == '2':
req['2has2'] = True
if (req['1req2'] and req['2req2'] and not(s1[j]=='2' and s2[j]=='2')) or (req['1req1'] and req['2req1'] and not(s1[j]=='1' and s2[j]=='1')):
print 0
esc = True
break
elif ((req['1req2'] or req['2req2']) and (s1[j]!='2' and s2[j]!='2')) or ((req['1req1'] or req['2req1']) and (s1[j]!='1' and s2[j]!='1')):
print 0
esc = True
break
elif (req['1req2'] and req['2has2']) or (req['2req2'] and req['1has2']):
s1[j],s2[j] = s2[j],s1[j]
elif (req['1req1'] and not req['2has2']) or (req['2req1'] and not req['1has2']):
s1[j],s2[j] = s2[j],s1[j]
if s1[j]==s2[j]:
count+=1
if s1[j]=='1':
chain=False
elif not chain:
chain=True
count+=1
count+=1
if esc:
continue
elif n==3:
print 2
elif s1[n-2]=='2' or s2[n-2]=='2':
print 0
elif (s1[n-3]=='2' and s1[n-4]=='1') or (s2[n-3]=='2' and s2[n-4]=='1'):
print 0
else:
print pow(2,count,1000000007)Chef and Two String CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Chef_and_Two_String
{
class Program
{
static void Main(string[] args)
{
int M = Convert.ToInt32(1e9 + 7);
int N = Convert.ToInt32(1e5 + 10);
int cases, n;
//char[] a = new char[N];
//char[] B = new char[N];
int[, ,] dp = new int[N, 3, 3];
int testCase = Convert.ToInt32(Console.ReadLine());
for (int t = 0; t < testCase; t++)
{
string a = Console.ReadLine();
string b = Console.ReadLine();
n = a.Length;
dp[n - 1, 0, 0] = 2;
dp[n - 1, 0, 1] = 0;
dp[n - 1, 0, 2] = 0;
dp[n - 1, 1, 0] = 0;
dp[n - 1, 1, 1] = 0;
dp[n - 1, 1, 2] = 0;
dp[n - 1, 2, 0] = 0;
dp[n - 1, 2, 1] = 0;
dp[n - 1, 2, 2] = 0;
for (int i = n - 2; i >= 0; i--)
{
if (a[i] == '1' && b[i] == '1')
{
dp[i, 0, 0] = (2 * dp[i + 1, 0, 0]) % M;
dp[i, 0, 1] = (2 * dp[i + 1, 0, 0]) % M;
dp[i, 0, 2] = 0;
dp[i, 1, 0] = (2 * dp[i + 1, 0, 0]) % M;
dp[i, 1, 1] = (2 * dp[i + 1, 0, 0]) % M;
dp[i, 1, 2] = 0;
dp[i, 2, 0] = 0;
dp[i, 2, 1] = 0;
dp[i, 2, 2] = 0;
}
else if (a[i] == '2' && b[i] == '2')
{
dp[i, 0, 0] = (2 * dp[i + 1, 2, 2]) % M;
dp[i, 0, 1] = 0;
dp[i, 0, 2] = (2 * dp[i + 1, 2, 1]) % M;
dp[i, 1, 0] = 0;
dp[i, 1, 1] = 0;
dp[i, 1, 2] = 0;
dp[i, 2, 0] = (2 * dp[i + 1, 1, 2]) % M;
dp[i, 2, 1] = 0;
dp[i, 2, 2] = (2 * dp[i + 1, 1, 1]) % M;
}
else
{
dp[i, 0, 0] = (dp[i + 1, 0, 2] + dp[i + 1, 2, 0]) % M;
dp[i, 0, 1] = dp[i + 1, 2, 0];
dp[i, 0, 2] = dp[i + 1, 0, 1];
dp[i, 1, 0] = dp[i + 1, 0, 2];
dp[i, 1, 1] = 0;
dp[i, 1, 2] = dp[i + 1, 0, 1];
dp[i, 2, 0] = dp[i + 1, 1, 0];
dp[i, 2, 1] = dp[i + 1, 1, 0];
dp[i, 2, 2] = 0;
}
}
//for (int i = n - 2; i >= 0; i--)
//{
// for (int j = 0; j < 3; j++)
// {
// for (int k = 0; k < 3; k++)
// {
// Console.Write(dp[i, j, k] + " ");
// }
// }
// Console.WriteLine();
//}
Console.WriteLine(dp[0, 0, 0]);
}
Console.ReadLine();
}
}
}Chef and Two String CodeChef Solution in GO
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
reader := bufio.NewReaderSize(os.Stdin, 1<<13)
writer := bufio.NewWriterSize(os.Stdout, 1<<13)
input := new(Input)
for T := readInt(reader); T > 0; T-- {
input.a = readInts(reader)
input.b = readInts(reader)
fmt.Fprintln(writer, input.Solve())
}
writer.Flush()
}
// Returns the answer for a given input.
func (input *Input) Solve() int64 {
if input.memo == nil {
// Initialize the memo table, each index will need a 2D matrix
// to represent each state.
input.memo = make([][][]int64, 1e5)
// Now for each index.
for i := 0; i < len(input.memo); i++ {
// The 2D matrix to represent the states.
// The number of mandatory operations are in the range [0, 4)
input.memo[i] = make([][]int64, 4)
// Now the slices that will store the actual results
for j := 0; j < len(input.memo[i]); j++ {
input.memo[i][j] = make([]int64, 4)
}
}
}
// Fill the memo with -1 to mark unsolved states. Don't
// use 0 because it's a valid answer.
for i := 0; i < len(input.memo); i++ {
for j := 0; j < len(input.memo[i]); j++ {
for k := 0; k < len(input.memo[i][j]); k++ {
input.memo[i][j][k] = -1
}
}
}
// All preparations done, call the method to compute the result.
return input.countSubsets(0, 0, 0)
}
// Returns the number of subsets that satisfy the problem constraints.
//
// idx is current index in the a and b slices.
// mndA is the number of mandatory operations in the slice a.
// mndB is the number of mandatory operations in the slice b.
func (input *Input) countSubsets(idx, mndA, mndB int) int64 {
// Check if we've gone out of bounds.
// Doing an equals comparison is enough because we don't
// actually perform the jumps of length 2.
if idx == len(input.a) {
// We have gone out of bounds, check if this is a correct ending state.
_, validA := nextState(input.a, idx, mndA)
_, validB := nextState(input.b, idx, mndB)
if validA && validB {
// Correct ending state, return 1 as the only correct answer
// in this case is the empty subset since there are no more elements remaining.
return 1
}
// It's not correct, no possible subsets.
return 0
}
// Store the result in a pointer so we don't have to reference the memo table anymore,
// and need only to worry about the result
res := &input.memo[idx][mndA][mndB]
// If the answer answer already computed just return it.
if *res > -1 {
return *res
}
// We can't use the -1 anymore, time to put real values in it.
*res = 0
// Try with both subsets, one that contains a swap,
// another empty.
for swap := 0; swap < 2; swap++ {
if swap == 1 {
// Swap the values before adding to the result.
input.swap(idx)
}
// Calculate the values for the next state and check if we can proceed.
if nextA, okA := nextState(input.a, idx, mndA); okA {
// a is okay, now check b.
if nextB, okB := nextState(input.b, idx, mndB); okB {
// b is also okay, keep counting.
*res += input.countSubsets(idx+1, nextA, nextB)
// And don't forget the modulo.
if *res >= MOD {
// It's enough to subtract since we're making the that the
// result will never reach 2 * MOD or larger numbers.
*res -= MOD
}
}
}
if swap == 1 {
// The values were swapped, put them back in their initial position.
input.swap(idx)
}
}
return *res
}
// Returns the next mandatory count and whether this state is valid or not.
//
// The state is considered valid if there are no mandatory counts remaining,
// or the current position is an expected value with the mandatory counts.
func nextState(a []int, idx, mnd int) (int, bool) {
// We need to deal right away with the cases where we have gone out of
// bounds.
if idx == len(a) {
// The only valid states are mnd = 0 (no mandatory jump) or mnd = 3,
// meaning we found the first '2' in the pattern '221x'. But since it was
// right at the end of the array it means we have reached the end successfuly.
return 0, mnd == 0 || mnd == 3
}
// No jumps or sub-pattern 'x' inside '221x'.
if mnd == 0 || mnd == 1 {
if a[idx] == 1 {
// No mandatory jumps, just keep going.
return 0, true
}
// a[idx] = 2, found the first '2' in the pattern '221x',
// we need 3 more mandatory jumps.
return 3, true
}
if mnd == 2 {
// Sub pattern '1x'
if a[idx] == 1 {
// One more mandatory jump for the 'x'
return 1, true
}
// a[idx] = 2, not valid.
return 0, false
}
// mnd = 3, sub-pattern '21x'
if a[idx] == 2 {
// Two more for '1x'
return 2, true
}
// a[idx] = 1, not valid.
return 0, false
}
// Swap a[idx] and b[idx].
func (input *Input) swap(idx int) {
input.a[idx] ^= input.b[idx]
input.b[idx] ^= input.a[idx]
input.a[idx] ^= input.b[idx]
}
const MOD int64 = 1e9 + 7
// Modulo is an expensive operation, do it when only when necessary.
// In this problem we'll only be dealing with additions and multiplications.
func mod(x int64) int64 {
if x >= MOD {
return x % MOD
}
return x
}
// Input for a single test case.
type Input struct {
// Store as int slices for easier manipulation.
a, b []int
// Store a table with calculated answers.
// As int64 to leave a large enough room for the modular calculations.
// It stores the answer for the triple (index, mnda, mndb)
// where mnd is the number of mandatory digits remaining.
memo [][][]int64
}
// Returns the number of subsets that satisfy the problem constraints by
// checking each possible subset.
func (input Input) bruteSolve() int {
// Store the length of the arrays to avoid
// calling it everytime (becomes verbose).
n := len(input.a)
// To store our answer.
ans := 0
for mask := 0; mask < 1<<uint(n); mask++ {
// To store the indexes we have swapped to reset
// the values of the arrays.
subset := make([]int, 0)
for bit := 0; bit < n; bit++ {
if mask&(1<<uint(bit)) > 0 {
// add this index to the subset
subset = append(subset, bit)
}
}
// Swap the positions.
swapSubset(input.a, input.b, subset)
// And see if it adds to the answer.
if isGood(input.a) && isGood(input.b) {
ans++
}
// Done, now restore the previous state
swapSubset(input.a, input.b, subset)
}
// We're done.
return ans
}
// Return strue if the string a:
// - Starts with the first index;
// - It's possible to make a walk in the string from the beginning to the end
// where each position is visited exactly once.
//
// A walk is defined as a set of steps at which each step stays inside the
// string and its length is equal to the value at the current position.
func isGood(a []int) bool {
// Go for a walk. At each iteration we will always try to move forward first.
// The only time we can move backwards is right after making a move of length 2. In which case the move is mandatory.
// To store our current index
i := 0
// Loop until we reach the end, at each iteration we have already covered
// all the previous positions
for {
if i >= len(a) {
// We have gone out of bounds, bad string.
return false
}
if i == len(a)-1 {
// We reached the end, this string is good.
return true
}
// Can only move forward
if a[i] == 1 {
i++
} else {
// Move forward 2 positions;
i += 2
if i >= len(a) {
// Out of bounds.
return false
}
// Then backwards 1 position (will stay inside bounds);
if a[i] != 1 {
// We can't perform the move. Bad string.
return false
}
i--
// Then forward 2 more positions.
if a[i] != 2 {
// We can't perform the move. Bad string.
return false
}
i += 2
}
}
}
// Swaps a and b in the positions contained in s.
func swapSubset(a, b, s []int) {
for i := 0; i < len(s); i++ {
a[s[i]] ^= b[s[i]]
b[s[i]] ^= a[s[i]]
a[s[i]] ^= b[s[i]]
}
}
// Returns an int slice made of 1s and 2s.
//
// It works with the isValid function because the slice
// to be read will only contain character '1' and '2'.
func readInts(reader *bufio.Reader) []int {
b, err := reader.ReadByte()
for !isValid(b, err) {
b, err = reader.ReadByte()
}
res := make([]int, 0)
for isValid(b, err) {
res = append(res, int(b)-'0')
b, err = reader.ReadByte()
}
return res
}
func readInt(reader *bufio.Reader) int {
b, err := reader.ReadByte()
for !isValid(b, err) {
b, err = reader.ReadByte()
}
res := 0
for isValid(b, err) {
res = res*10 + int(b-'0')
b, err = reader.ReadByte()
}
return res
}
func isValid(b byte, err error) bool {
return err == nil && '0' <= b && b <= '9'
}Chef and Two String CodeChef Solution Review:
In our experience, we suggest you solve this Chef and Two String CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and Two String CodeChef Solution.
Conclusion:
I hope this Chef and Two String CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
