Problem Links:
Setter : Siddhant Gandhi
Tester : Jatin Nagpal
Editorialist : Siddhant Gandhi
DIFFICULTY
Easy - Medium
PRE-REQUISITES
Basic Math
PROBLEM
A mathematical expression consisting of binary bitwise operators( &, |, ^ ) is input as a string. Find out the maximum possible answer of this expression given that you can perform any operation first, that is you can violate precedence of operators.
BRUTE FORCE( for PARTIAL marks )
A brute force way to solve this problem would be solving the expression in all possible ways and then finding the maximum of the computed answers.
The number of ways in this case would be number of possible permutations of operators, here a permutation of operators would denote the sequence in which they are solved.
Let’s consider an expression x1&x2^x3&x4 , here there are 3 operators, let’s number them as 1 , 2 and 3 respectively, then the permutation (2, 1, 3) means that we solve 2nd operator first then the 1st operator and finally the 3rd one, so we first solve (x2 ^ x3) , then we solve x1 & (x2 ^ x3) and finally we solve ((x1 & (x2 ^ x3)) & x4).
This approach would only fetch you partial marks, to head towards AC see the below given approach.
HEADING TOWARDS AC!
We can make this process more efficient by using this approach-
Let’s consider the same example again x1&x2^x3&x4 .
The operands here are [x1, x2, x3, x4] , we now divide the operands into 2 different contiguous groups.
Our aim is to solve all possible answers of 1st group with all possible answers of the 2nd group.
The various possible groupings are-
a) [x1] [x2, x3, x4]
b) [x1, x2] [x3, x4]
c) [x1, x2, x3] [x4]
Let’s first solve for a) type grouping which is [x1] [x2, x3, x4] -
The only possible answer for 1st group is x1.
2nd group can be further subdivided as-
i) [x2] [x3, x4]
ii) [x2, x3] [x4]
On solving i) we get x2 ^ (x3 & x4).
On solving ii) we get (x2 ^ x3) & x4.
So there are 2 possible answers of 2nd group of a) which when solved with the only possible answer x1 of 1st group of a) results in 2 possible outcomes which are –
x1 & (x2 ^ (x3 & x4))
x1 & ((x2 ^ x3) & x4)
So the grouping of type a) results in 2 possible answers.
Let’s now solve for b) type grouping which is [x1, x2] [x3, x4] –
This need not be divided into further sub-groups as the only possible answer of 1st group is –
(x1 & x2)
, and the only possible answer of 2nd group is –
(x3 & x4)
So the only possible outcome of grouping of type b) is –
((x1 & x2) ^ (x3 & x4))
Finally we need to solve for c) type grouping which is [x1, x2, x3] [x4] –
This can solved in a similar way as grouping of type a) and would yield 2 possible outcomes.
So now we got (2 + 1 + 2) that is 5 possible answers out of which we need to compute the maximum.
The above solution would fetch you an AC verdict but it can be made even more efficient by using Dynamic Programming because there are various operations which are performed again and again on the same operands, so we store the result once it is computed.
SOLUTION:
Setter
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
// 0 is &
// 1 is |
// 2 is ^
vector <int> b,c;
vector <int> dfs(int st,int en)
{
vector <int> ret;
if(st>en)
{
ret.push_back(b[st]);
return ret;
}
f(i,st,en+1)
{
vector <int> a=dfs(st,i-1);
vector <int> d=dfs(i+1,en);
for(int j: a)
{
for(int k: d)
{
if(c[i]==0)
ret.push_back(j&k);
else if(c[i]==1)
ret.push_back(j|k);
else
ret.push_back(j^k);
}
}
}
return ret;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
b.clear();
c.clear();
int n;
string a;
cin>>a;
n=a.length();
f(i,0,n)
{
if(a[i]<='9'&&a[i]>='0')
{
b.push_back(0);
int bs=b.size()-1;
while(a[i]<='9'&&a[i]>='0')
{
b[bs]=b[bs]*10+(a[i]-'0');
i++;
}
i--;
}
else
{
if(a[i]=='&')
c.push_back(0);
else if(a[i]=='|')
c.push_back(1);
else if(a[i]=='^')
c.push_back(2);
else
assert(1==2);
}
}
vector <int> an=dfs(0,b.size()-2);
int ans=0;
for(int i: an)
ans=max(ans,i);
cout<<ans<<'\n';
}
return 0;
}
Tester(DP Solution)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
// 0 is &
// 1 is |
// 2 is ^
vector <int> dp[101][101];
vector <int> b,c;
vector <int> dfs(int st,int en)
{
if(dp[st+1][en+1].size()!=0)
return dp[st+1][en+1];
vector <int> ret;
if(st>en)
{
ret.push_back(b[st]);
return dp[st+1][en+1]=ret;
}
f(i,st,en+1)
{
vector <int> a=dfs(st,i-1);
vector <int> d=dfs(i+1,en);
for(int j: a)
{
for(int k: d)
{
if(c[i]==0)
ret.push_back(j&k);
else if(c[i]==1)
ret.push_back(j|k);
else
ret.push_back(j^k);
}
}
}
// sort(ret.begin(),ret.end());
// unique(ret.begin(), ret.end());
return dp[st+1][en+1]=ret;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
f(i,0,101)
f(j,0,101)
dp[i][j].clear();
b.clear();
c.clear();
int n;
string a;
cin>>a;
n=a.length();
f(i,0,n)
{
if(a[i]<='9'&&a[i]>='0')
{
b.push_back(0);
int bs=b.size()-1;
while(a[i]<='9'&&a[i]>='0')
{
b[bs]=b[bs]*10+(a[i]-'0');
i++;
}
i--;
}
else
{
if(a[i]=='&')
c.push_back(0);
else if(a[i]=='|')
c.push_back(1);
else if(a[i]=='^')
c.push_back(2);
else
assert(1==2);
}
}
vector <int> an=dfs(0,b.size()-2);
int ans=0;
for(int i: an)
ans=max(ans,i);
cout<<ans<<'\n';
}
return 0;
}
COMPLEXITY
Complexity is roughly O( Catalan number ).
Assuming N is number of operators:-
Equation for calculating T(N) :-
T(N) = (T(N - 1) * T(0)) + (T(N - 2) * T(1)) + (T(N - 3) * T(2)) + … + (T(0) * T(N - 1)); Given T(0) = 1
For DP solution it’s T(N) + 2 * T(N - 1) + 3 * T(N - 2) + … + (N + 1) * T(0)
For non-DP solution, it’s sum of complexities of all the nodes in the tree formed by T(N)-
Ex:
T(2) / \ T(1)*T(0) : T(0)*T(1) /\ /\ T(0) T(0) T(0) T(0)
Ans = 2+4*1+4*1 = 10 ( T(2)=2,T(1)=1,T(0)=1 )
Feel free to share your approach. 