I personally think that all these variations of partition category are non trivial and hard to come up with the solution on our own but once we learn them all then further problems can be mapped into on these 5-6 problems. So if anyone reading this, don't get demotivated if you had seen MCM problem solution and tried this on your own but couldn't solve it. I spent 2 hrs but wasn't able to come up with the solution. Just watch all these 5-6 videos on partition pattern and , you'll feel confident on this pattern.
Yes!! Thank you for the encouragement. I think that this pattern in dp is actually the hardest to grasp. But I think that makes it all the more interesting and challenging!!
The linked leetcode problem is incorrect and as coding ninjas link is removed I think you should fix this.........and bro mcm is hard, remaining patterns I was able to do on my own after 1 or 2 prblms, but this 🤯
Here's the Tabulation Code which is running absolutely fine in Coding Ninjas: #define ll long long int ll mod=1000000007; int evaluateExp(string & exp) { int n=exp.length(); vector dp(n,vector(n,vector(2,0))); for(int i=n-1;i>=0;i--) { for(int j=i;j
TABULATION CODE: #include int mod=1e9+7; #define ll long long int evaluateExp(string & exp) { int n=exp.length(); vector dp(n,vector (n,vector (2,0))); for(int i=n-1;i>=0;i--){ for(int j=0;j
34:08 Dont let Striver fool you. Tabulation is as easy as previous dp question and you can easily figure it out. best of luck buddy!! hint : 4 nested loops will be there (i , j, isTrue, k)
Understood!!. And this is the tabulation code incase anyone needs(the numbers of iterations are also halved) -> ```cpp #include const long long mod = 1000000007; int evaluateExp(string & exp) { // Write your code here. long long n = exp.length(); long long isTrue = 1; vector dp(n+2,vector(n+2,vector(2,0))); //base cases of i>j already intialized with 0 for(int i=0;i=0;i-=2){ for(int j=i+2;j
Here's the tabulation code which got me correct! #include #define ll long long int mod = 1000000007; int evaluateExp(string & exp) { int n= exp.size(); vector dp(n, vector (n, vector (2, 0)));
This is just for my own reference: Bhai multiply hi hoga na because dekh left mai maan le (()(())()()()) , ((()(()))(())) ye do ways hai and (()(())()()()) , ((()(()))(())), (()(())()()()) , ((()(()))(())) then har ek left ke liye 4 options hai ki true mile, so agar and rahega then 2 * 4 ways hoga!
well its pretty easy to write the try all ways wala case in terms of tabulation. but how to write base is getting tough. while iterating if i > j continue; and i==j copy the memoization.
yeah that's right bro after filling base cases sepratly , whenever encounter base case condition while filling remaining table just continue (because that one is already filled)
left | right can be true even if one of left or right is false. That's why we need to consider the false ways as well to find out total number of ways. Thanks.
but this is not the case when we have & as an operator. left&right is true only if both of them are true then why are we considering the else case?@hakraborty9717
This question was a direct application of MCM problem, i did this on my own so you can to. Dont fall for the comments below,these are rote learning weaklings. Even if you werent able to do it and watch the solution,you'll realize the actual dp part is same as mcm, the additional logic is pure logic.
JUST IN CASE ANYONE NEEDS THE CODE. int f(int i, int j, bool istrue, string &exp,vector&dp){ if(i>j){ return 0; } if(i==j){ if(istrue){ return exp[i]=='T'; } else return exp[i]=='F'; } if(dp[i][j][istrue]!=-1){ return dp[i][j][istrue]; } int ways=0; for(int k=i+1;k
c++ tabulation code: // no of ways in which the boolean expression evaluates to 'true' // logical operators present are: &,|, ^ int countWays(int n, string s) { // state: dp[i][j][0]: # ways the expresion from index i to j evaluates to 'false', similary dp[i][j][1]: # ways expr evaluates to 'true' vector dp(n, vector (n, vector (2, 0))); // bc: when i < j then ans = 0 // when i == j: then if s[i] == 'true', dp[i][j][0] = 0, dp[i][j][1] = 1 and v.v // transition: since we're doing partition at logical operators bcz: then left side and right of the problem becomes an independent subproblem. // flow of states: bottom to top && left to right for(int i = n-1; i >= 0; i -= 2) { for(int j = 0; j < n; j += 2) { // transition for dp[i][j][0/1] // bc if(i > j) continue; if(i == j) { if(s[i] == 'T') dp[i][j][1] = 1, dp[i][j][0] = 0; else dp[i][j][0] = 1, dp[i][j][1] = 0; } else { int waysTrue = 0, waysFalse = 0; // total no of ways in which the exp evaluates to true or false. for(int ind = i+1; ind < n && ind
the moment when i seen this question , instead of dp use of stack came to mind then i started to implement , and then got accepted . Logic-> if s[i]==',' continue and if its ')' then we have to perform operation that is before opening bracket for this closing bracket, i'll perform the operation (or,and or not),, so i stored all character (t/f) in a vector until stack top becomes '(' and then pop it nd then st.top() will be the operation that i have to perform then i perform the operation and push the result in the top. and if any other character comes(&,|,!,( ), then normally push it , and at the end of all operations ,, the stack top will be storing the t/f answer
STRIVER : IF UY KNOW MCM THIS QUESTION IS CAKE WALK Me after listening this and directly jumps on question AFTER ONE DECADE ME : IS THIS WAS A CAKE WALK ?😶
let's say, int x = INT_MAX; and int y = INT_MAX; suppose you want to do (x+y)%mod then x + y will already overflow and then doing modulus operation will be useless. Therefore x & y must be long long not int.
for and case lets assume left true ways = 10 and right true ways =5 how can it be left*right .we got true only when both r true. i.e.,min of those two. am i wrong .please explain
ok, i will explain you using one exmaple, lets say we have 3 places delhi,hyderabad,chennai. Think delhi and chennai as start and end points while hyderabad is mid point. lets say we have only 2 ways to travel from delhi to hyderabad,(way1,way2) and simillarly we have 2 ways to travel to chennai from hyderabad(way3,way4). so what are the total ways to travel to chennai from delhi i,e., 4(way1->way3,way1->4,way2->way3,way2->way4) which is obtained by multiplying totalways(delhi to hyderabad) and totalways(hyderabad to chennai) which is supposed to be 2*2=4. I hope this explanation clear your doubt.
Striver you are the GOAT!!!!! def evaluateExp(exp: str) -> int: n = len(exp) m = 1000000007 dp = [[[0 for i in range(2)] for j in range(n)] for k in range(n)] for i in range(n): if exp[i] == 'T': dp[i][i][1] = 1 elif exp[i] == 'F': dp[i][i][0] = 1 for i in range(n-1, -1, -1): for j in range(i, n, 1): for ind in range(i+1, j, 2): lt = dp[i][ind-1][1] lf = dp[i][ind-1][0] rt = dp[ind+1][j][1] rf = dp[ind+1][j][0] if exp[ind] == '&': dp[i][j][1] += (lt*rt)%m dp[i][j][0] += (lt*rf + rt*lf + rf*lf)%m elif exp[ind] == '|': dp[i][j][1] += (lt*rt + lt*rf + rt*lf)%m dp[i][j][0] += (lf*rf)%m elif exp[ind] == '^': dp[i][j][1] += (lt*rf + rt*lf)%m dp[i][j][0] += (lt*rt + lf*rf)%m dp[i][j][1] %= m dp[i][j][0] %= m return dp[0][n-1][1]
But why we are checking for false in '&' condition 😢 Edit - because for false also we have to return some value , we are not just checking left true or right true we are checking for false also , so values should be returned their .
Understood As Always. Below is the tabulation code. #include int mod= (int)(1e9)+7; long long f(int i, int j,int isTrue, string &exp, vector& dp){ if(i==j){ if(isTrue) return exp[i]=='T'; return exp[i]=='F'; } if(dp[i][j][isTrue]!=-1) return dp[i][j][isTrue];
Anyone help why mod is required here , as i can see the constraints length of exp can go upto 200 ,TC: N^3 = (200)^3=(2.100)^3=8.10^6, it can be computed ,right. correct me if i am wrong.
Understood😀 Here's the tabulation code... #include #define ll long long int mod = 1000000007; int evaluateExp(string & exp) { // Write your code here. int n = exp.length(); vector dp(n+1, vector(n+1, vector(2, 0))); //base case for(int i=0;i=0;i--){ for(int j=i;j
able to solve if the problem will only require that is the expression evaluates to true or not but can't think of how to calculate number of ways it can be true
#Tabulation code in python def tabular(self,s): n = len(s) dp=[[[0 for i in range(2)] for j in range(n+1)] for k in range(n+1)] for i in range(n): for j in range(n): for flag in range(2): if i == j: if flag : dp[i][j][flag] = int(s[i]=='T') # print("t",dp[i][j][flag]) else: dp[i][j][flag] = int(s[i]=='F') # print("f",dp[i][j][flag])
for i in range(n-1,-1,-1): for j in range(n): if i>=j: continue else: for flag in range(2): ans = 0 for ind in range(i+1,j,2): lt = dp[i][ind-1][1] lf = dp[i][ind-1][0] rt = dp[ind+1][j][1] rf = dp[ind+1][j][0]
if s[ind] == '&': if flag: ans += lt*rt else: ans += lf*rf + rt*lf + lt*rf elif s[ind] == '|': if flag: ans += lt*rt + lt*rf + rt*lf else: ans += lf*rf else: if flag: ans+= lf*rt + rf*lt else: ans+=lf*rf + lt*rt dp[i][j][flag] = ans return dp[0][n-1][1]
Python Tabulation solution: ''' Tabulation - Bottom Up from base case TC = O(N ^ 3) SC = O(N ^ 2 * 2) + No recursion depth ''' n = len(exp) mod = 1000000007 dp = [[[False for _ in range(2)] for j in range(n+1)] for i in range(n+1)] # Base case for i in range(n): for j in range(n): if i == j: dp[i][j][0] = (exp[i] == 'F') dp[i][j][1] = (exp[i] == 'T') # Reverse of top down # i -> 0 to n-1, j -> n-1 to 0 # But j has to be greater than i, so start j from (i + 1) for i in range(n-1, -1, -1): for j in range(i+1, n): for evaluateTrue in range(2): # will never execute, just for safety if i > j: continue ways = 0 # Try all possible ways - Partition on operator # Each operator is equidistant with 2 spaces for sym_idx in range(i+1, j, 2): # Left and Right expressions can be either True or False left_true_ways = dp[i][sym_idx-1][True] left_false_ways = dp[i][sym_idx-1][False] right_true_ways = dp[sym_idx+1][j][True] right_false_ways = dp[sym_idx+1][j][False] # Based on the symbol, compute possibilities if exp[sym_idx] == '&': if evaluateTrue: # Both left and right must be true ways += (left_true_ways * right_true_ways) else: # left F right F/ left T right F/ left F right T ways += ((left_false_ways * right_false_ways) + (left_true_ways * right_false_ways) + (left_false_ways * right_true_ways))
elif exp[sym_idx] == '|': if evaluateTrue: # Either of left or right or both can be True ways += ((left_true_ways * right_true_ways) + (left_true_ways * right_false_ways) + (left_false_ways * right_true_ways)) else: # Both left and right has to be false ways += (left_false_ways * right_false_ways) elif exp[sym_idx] == '^': # XOR => returns T, if left and right have opp polarities if evaluateTrue: ways += ((left_false_ways * right_true_ways) + (left_true_ways * right_false_ways)) else: ways += ((left_true_ways * right_true_ways) + (left_false_ways * right_false_ways)) dp[i][j][evaluateTrue] = ways % mod return dp[0][n-1][1]
Gfg Tabulation (Approach 2): Here I'll be travesing i and j only towards operands i.e. T or F instead of traversing i and j over each index int countWays(int n, string s){ // code here // vector dp(n,vector(n,vector(2,-1))); // return solve(0,n-1,true,s,dp)%modulo; vector dp(n,vector(n,vector(2,0))); for(int i=0;i=0;i-=2){ for(int j=i+2;j
Tabulation Code (Java): import java.util.*; public class Solution { static int mod = 1000000007; public static int evaluateExp(String s) { int n = s.length(); int[][][] dp = new int[n][n][2];
Tabulation Code #include long mod = 1e9 + 7; int evaluateExp(string & s) { // Write your code here. int n = s.length(); vector dp (n+1, vector(n+1, vector(2, 0))); for (int i{}; i=0; i-=2){ for (int j{i+2}; j
Tabulation Code with only 3 nested loops which got accepted on Interview Bit const int MOD = 1003; int Solution::cnttrue(string s) { int n = s.size(); vector dp(n, vector (n, vector (2, 0))); for(int i=0; i=0; i--){ for(int j=i; j
Tabulation Code: int countWays(string &S){ const int mod=1e9+3; int N=S.size(); // using tabulation vectordp(N,vector(N,vector(2,0))); for(int i=0;i=0;st-=2){ for(int en=0;en=en)continue; int totTrues=0,totFalses=0; for(int i=st+1;i
This is the tabulation code according to your approach: unsigned int mod=1e9+7; int evaluateExp(string & s) { int n=s.size(); vector dp(n+1,vector(n+1,vector(2,0)));
I personally think that all these variations of partition category are non trivial and hard to come up with the solution on our own but once we learn them all then further problems can be mapped into on these 5-6 problems. So if anyone reading this, don't get demotivated if you had seen MCM problem solution and tried this on your own but couldn't solve it. I spent 2 hrs but wasn't able to come up with the solution. Just watch all these 5-6 videos on partition pattern and , you'll feel confident on this pattern.
I dont disagree
@@akashsahu2571what's you opinion
its like we are byhearting the concepts
Yes!! Thank you for the encouragement. I think that this pattern in dp is actually the hardest to grasp. But I think that makes it all the more interesting and challenging!!
thnxx.needed this
Watching this again after 8 months, and I had entirely forgotten how to solve this one. Thanks again for making it clear!
I did knew MCM but it was not at all a cake walk
same ):
Same🥲
It motivated me
+1
The way of thinking its recursion aproach is beyond my imagination! GreatWork! US!
The way of thinking its recursion aproach is beyond my imagination! GreatWork! US!
correction:- Insted of on an operand* it's on an operator 6:40
I think returning pair will be easier to understand and we can use 2d dp
yes i am thinking so, if(i==j ){
if(str[i]=='T') {
return {1,0};
}
else return {0,1};
}
is the code ok fore base case:
@@soumabhaghosh6199 yes and below is the code
def evaluateExp(expr):
# Write your code here.
dp = {}
def dfs(i, j):
if (i, j) in dp:
return dp[(i, j)]
if i > j: return 0
if i == j:
if expr[i] == 'T':
return [1, 0]
else:
return [0, 1]
waysTrue = 0
waysFalse = 0
for k in range(i + 1, j, 2):
lt = dfs(i, k - 1)[0]
lf = dfs(i, k - 1)[1]
rt = dfs(k + 1, j)[0]
rf = dfs(k + 1, j)[1]
if expr[k] == "|":
# if isTrue:
waysTrue += lt * rt + lt * rf + rt * lf
# else:
waysFalse += lf * rf
if expr[k] == "&":
# if isTrue:
waysTrue += lt * rt
# else:
waysFalse += lf * rf + lt * rf + rt * lf
if expr[k] == "^":
# if isTrue:
waysTrue += lt * rf + lf * rt
# else:
waysFalse += lf * rf + lt * rt
dp[(i, j)] = [waysTrue, waysFalse]
return [waysTrue, waysFalse]
return dfs(0, len(expr) - 1)[0]
The linked leetcode problem is incorrect and as coding ninjas link is removed I think you should fix this.........and bro mcm is hard, remaining patterns I was able to do on my own after 1 or 2 prblms, but this 🤯
Here's the Tabulation Code which is running absolutely fine in Coding Ninjas:
#define ll long long int
ll mod=1000000007;
int evaluateExp(string & exp) {
int n=exp.length();
vector dp(n,vector(n,vector(2,0)));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j
Thanks a lot.
bro it also consider the case s[i]==operation in this our answer is wrong na?
UNDERSTOOD.........Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Striver bhaiya please add 5-8 problems Bitmask DP
US as always ❤️
Thank you so much for this!! I can't imagine learning DSA without you❤
// TABULATION
vector dp(n, vector(n, vector(2, 0)));
for(int i=0; i=0; i-=2){
for(int j=i+2; j
Understood, Thank you so much Striver
TABULATION CODE:
#include
int mod=1e9+7;
#define ll long long
int evaluateExp(string & exp) {
int n=exp.length();
vector dp(n,vector (n,vector (2,0)));
for(int i=n-1;i>=0;i--){
for(int j=0;j
I came up with the solution , it took me about 1.5 hour but i did it, all thanks to striver :)
Very Nice explanation,one of the easiest lecture on partition dp.
34:08 Dont let Striver fool you. Tabulation is as easy as previous dp question and you can easily figure it out. best of luck buddy!!
hint : 4 nested loops will be there (i , j, isTrue, k)
understood after waching the video twice or thrice....This is really a tough question
Understood!!. And this is the tabulation code incase anyone needs(the numbers of iterations are also halved) ->
```cpp
#include
const long long mod = 1000000007;
int evaluateExp(string & exp) {
// Write your code here.
long long n = exp.length();
long long isTrue = 1;
vector dp(n+2,vector(n+2,vector(2,0)));
//base cases of i>j already intialized with 0
for(int i=0;i=0;i-=2){
for(int j=i+2;j
Wow it was something else but thanks for easy to learn explaination, Understood
Here's the tabulation code which got me correct!
#include
#define ll long long
int mod = 1000000007;
int evaluateExp(string & exp) {
int n= exp.size();
vector dp(n, vector (n, vector (2, 0)));
for(int i=0; i=0; i--){
for(int j=i+1; j
Great. I also wrote the same code. Base Case was the main highlight of tabulation.
why does j start from i+1?
AND
When I do _for(int j=0; jj) continue;
This gives me wrong answer, why?
awesome explanation as always💥💥
Please add more videos to this playlist if possible 🥺
@Ayush Negi Welcome!
Do learn notion, because it can be a life saver!
bhai abb kya puri dp us hi se kara leag khud bhi kuch kr le
@@taashukumar1155 You are right, but he'll get paid for uploading more videos... Good for him as well as us
@parthsalat kaha hai notes?
This is just for my own reference: Bhai multiply hi hoga na because dekh left mai maan le (()(())()()()) , ((()(()))(())) ye do ways hai and (()(())()()()) , ((()(()))(())), (()(())()()()) , ((()(()))(())) then har ek left ke liye 4 options hai ki true mile, so agar and rahega then 2 * 4 ways hoga!
Understood!! Thank you soooooo much as always!!
well its pretty easy to write the try all ways wala case in terms of tabulation.
but how to write base is getting tough.
while iterating if i > j continue;
and i==j copy the memoization.
i dont know its right or not but am getting correct answers for it
@@devbhattdev1607 it is right
yeah that's right bro
after filling base cases sepratly , whenever encounter base case condition while filling remaining table just continue (because that one is already filled)
Why do we need to consider the else case as the problem stated that boolean expressions need to be true?
True
left | right can be true even if one of left or right is false. That's why we need to consider the false ways as well to find out total number of ways. Thanks.
but this is not the case when we have & as an operator. left&right is true only if both of them are true then why are we considering the else case?@hakraborty9717
Understood well!! Awesome explanation
This question was a direct application of MCM problem, i did this on my own so you can to. Dont fall for the comments below,these are rote learning weaklings. Even if you werent able to do it and watch the solution,you'll realize the actual dp part is same as mcm, the additional logic is pure logic.
JUST IN CASE ANYONE NEEDS THE CODE.
int f(int i, int j, bool istrue, string &exp,vector&dp){
if(i>j){
return 0;
}
if(i==j){
if(istrue){
return exp[i]=='T';
}
else return exp[i]=='F';
}
if(dp[i][j][istrue]!=-1){
return dp[i][j][istrue];
}
int ways=0;
for(int k=i+1;k
Understood, sir. Thank you very much.
c++ tabulation code:
// no of ways in which the boolean expression evaluates to 'true'
// logical operators present are: &,|, ^
int countWays(int n, string s) {
// state: dp[i][j][0]: # ways the expresion from index i to j evaluates to 'false', similary dp[i][j][1]: # ways expr evaluates to 'true'
vector dp(n, vector (n, vector (2, 0)));
// bc: when i < j then ans = 0
// when i == j: then if s[i] == 'true', dp[i][j][0] = 0, dp[i][j][1] = 1 and v.v
// transition: since we're doing partition at logical operators bcz: then left side and right of the problem becomes an independent subproblem.
// flow of states: bottom to top && left to right
for(int i = n-1; i >= 0; i -= 2) {
for(int j = 0; j < n; j += 2) {
// transition for dp[i][j][0/1]
// bc
if(i > j) continue;
if(i == j) {
if(s[i] == 'T') dp[i][j][1] = 1, dp[i][j][0] = 0;
else dp[i][j][0] = 1, dp[i][j][1] = 0;
}
else {
int waysTrue = 0, waysFalse = 0; // total no of ways in which the exp evaluates to true or false.
for(int ind = i+1; ind < n && ind
As always "understood" ❤
Homework code for tabulation in this ques:
int tab(string s,int n)
{
vector dp(n,vector(n,{0,0}));//{true,false}
for(int i=0,j=0;i
the moment when i seen this question , instead of dp use of stack came to mind then i started to implement , and then got accepted .
Logic-> if s[i]==',' continue
and if its ')' then we have to perform operation that is before opening bracket for this closing bracket, i'll perform the operation (or,and or not),,
so i stored all character (t/f) in a vector until stack top becomes '(' and then pop it nd then st.top() will be the operation that i have to perform then i perform the operation and push the result in the top. and if any other character comes(&,|,!,( ), then normally push it , and at the end of all operations ,, the stack top will be storing the t/f answer
As always "understood" ❤️
I was getting confused initially when you were saying operand instead of operator. You can add a note on video about it
understood thank you striver
Thank you striver❤
STRIVER : IF UY KNOW MCM THIS QUESTION IS CAKE WALK
Me after listening this and directly jumps on question
AFTER ONE DECADE
ME : IS THIS WAS A CAKE WALK ?😶
Same😂
Understood 😊
Appreciate your efforts 🙏
#understood
Please add more videos to this playlist striver ,we really need them
Great explanation
but could not understand why we require to take long long because we are doing mod of 1e9+7 at every step
let's say,
int x = INT_MAX;
and
int y = INT_MAX;
suppose you want to do (x+y)%mod
then x + y will already overflow and then doing modulus operation will be useless. Therefore x & y must be long long not int.
you can use modulo properties too if you don't want to use long long
Understood Sir, Thank you very much
Understood ❤❤❤❤
**Tabulation code using striver's principles:**
int evaluateExp(string & exp) {
int n = exp.size();
vector dp(n, vector (n, vector(2, 0)));
for(int ind = 0; ind < n; ind++) {
for(int isTrue = 0; isTrue = 0; i--) {
for(int j = 0; j
UnderStood amazing💥
Understood. Thankyou Sir
Tabulation Code:
int evaluateExp(string &exp) {
// Write your code here.
int n=exp.length();
vector dp(n,vector(n,vector (2,0)));
for(int i=n-1;i>=0;i--)
{
for(int j=i;j
for and case lets assume left true ways = 10 and right true ways =5 how can it be left*right .we got true only when both r true. i.e.,min of those two.
am i wrong .please explain
ok, i will explain you using one exmaple, lets say we have 3 places delhi,hyderabad,chennai. Think delhi and chennai as start and end points while hyderabad is mid point. lets say we have only 2 ways to travel from delhi to hyderabad,(way1,way2) and simillarly we have 2 ways to travel to chennai from hyderabad(way3,way4). so what are the total ways to travel to chennai from delhi i,e., 4(way1->way3,way1->4,way2->way3,way2->way4) which is obtained by multiplying totalways(delhi to hyderabad) and totalways(hyderabad to chennai) which is supposed to be 2*2=4. I hope this explanation clear your doubt.
"UNDERSTOOD" as always!
*Tabulation*
#include
int evaluateExp(string &exp)
{
int n = exp.size();
vector dp(n, vector(n, vector(2, 0)));
for (int start = n - 1; start >= 0; start--)
{
for (int end = 0; end < n; end++)
{
for (int isTrue = 1; isTrue >= 0; isTrue--)
{
if (start > end)
{
continue;
}
if (start == end)
{
if (isTrue == 1)
{
dp[start][end][isTrue] = exp[start] == 'T';
}
else
{
dp[start][end][isTrue] = exp[start] == 'F';
}
}
else
{
int MOD = 1e9 + 7;
long long ways = 0;
for (int k = start + 1; k
Thank you
Understood!
hey struver i did'nt understand why you are mutiplying the lt lr etc
is it necessary to tell the tabulation approach in interviews,wont memoization wrok,?? I am kind of struggling with tabulation
Try to write in paper what the row and column exactly mean? I used to struggle as well in base cases until I started writing them down in the paper.
Amazing explanation
Striver you are the GOAT!!!!!
def evaluateExp(exp: str) -> int:
n = len(exp)
m = 1000000007
dp = [[[0 for i in range(2)] for j in range(n)] for k in range(n)]
for i in range(n):
if exp[i] == 'T':
dp[i][i][1] = 1
elif exp[i] == 'F':
dp[i][i][0] = 1
for i in range(n-1, -1, -1):
for j in range(i, n, 1):
for ind in range(i+1, j, 2):
lt = dp[i][ind-1][1]
lf = dp[i][ind-1][0]
rt = dp[ind+1][j][1]
rf = dp[ind+1][j][0]
if exp[ind] == '&':
dp[i][j][1] += (lt*rt)%m
dp[i][j][0] += (lt*rf + rt*lf + rf*lf)%m
elif exp[ind] == '|':
dp[i][j][1] += (lt*rt + lt*rf + rt*lf)%m
dp[i][j][0] += (lf*rf)%m
elif exp[ind] == '^':
dp[i][j][1] += (lt*rf + rt*lf)%m
dp[i][j][0] += (lt*rt + lf*rf)%m
dp[i][j][1] %= m
dp[i][j][0] %= m
return dp[0][n-1][1]
But why we are checking for false in '&' condition 😢
Edit - because for false also we have to return some value , we are not just checking left true or right true we are checking for false also , so values should be returned their .
Really well explained.
Understood As Always.
Below is the tabulation code.
#include
int mod= (int)(1e9)+7;
long long f(int i, int j,int isTrue, string &exp, vector& dp){
if(i==j){
if(isTrue) return exp[i]=='T';
return exp[i]=='F';
}
if(dp[i][j][isTrue]!=-1) return dp[i][j][isTrue];
long long cnt=0;
for(int k=i+1; k
@31:26 thats what she said
why did we use a "x" in and operator
Understood 😊😊😊
leetcode m nhi h kya ye?
Anyone help why mod is required here , as i can see the constraints length of exp can go upto 200 ,TC: N^3 = (200)^3=(2.100)^3=8.10^6, it can be computed ,right. correct me if i am wrong.
In case anyone is intrested in Tabulaton code, here it is in JAVA :
public class Solution {
private static final int MOD = (int) 1e9 + 7;
public static int evaluateExp(String exp) {
int n = exp.length();
long[][][] dp = new long[n][n][2];
for (int i = 0 ; i < n ; i++) {
if (exp.charAt(i) == 'T') {
dp[i][i][1] = 1;
dp[i][i][0] = 0;
} else if (exp.charAt(i) == 'F') {
dp[i][i][1] = 0;
dp[i][i][0] = 1;
}
}
for (int i = n-1 ; i >= 0 ; i-=2) {
for (int j = i ; j < n ; j+=2) {
for (int k = i+1 ; k < j ; k+=2) {
long lt = dp[i][k-1][1];
long rt = dp[k+1][j][1];
long lf = dp[i][k-1][0];
long rf = dp[k+1][j][0];
if (exp.charAt(k) == '&') {
dp[i][j][1] = (dp[i][j][1] + lt*rt) % MOD;
dp[i][j][0] = (dp[i][j][0] + lt*rf + rt*lf + rf*lf) % MOD;
} else if (exp.charAt(k) == '|') {
dp[i][j][1] = (dp[i][j][1] + lt*rf + rt*lf + rt*lt) % MOD;
dp[i][j][0] = (dp[i][j][0] + lf*rf) % MOD;
} else {
dp[i][j][1] = (dp[i][j][1] + lt*rf + rt*lf) % MOD;
dp[i][j][0] = (dp[i][j][0] + lf*rf + lt*rt) % MOD;
}
}
}
}
return (int) dp[0][n-1][1];
}
}
Understood!!! But mind twisting!
Understood😀
Here's the tabulation code...
#include
#define ll long long
int mod = 1000000007;
int evaluateExp(string & exp) {
// Write your code here.
int n = exp.length();
vector dp(n+1, vector(n+1, vector(2, 0)));
//base case
for(int i=0;i=0;i--){
for(int j=i;j
Why is he calculating and summing up the no of ways when False comes. @30:02
Understood💙
able to solve if the problem will only require that is the expression evaluates to true or not
but can't think of how to calculate number of ways it can be true
*Tabulation code in Java:*
import java.util.Arrays;
public class Solution {
public static int evaluateExp(String exp) {
int mod = 1000000007;
// Write your code here.
int n = exp.length();
int[][][] dp = new int[n][n][2];
for(int i = 0; i < n; i++) {
dp[i][i][1] = exp.charAt(i) == 'T' ? 1 : 0;
dp[i][i][0] = exp.charAt(i) == 'F' ? 1 : 0;
}
for(int i = n-1; i >= 0; i--) {
for(int j = i+1; j < n; j++) {
for(int isTrue = 0; isTrue < 2; isTrue++) {
if(i > j)
continue;
long ans = 0;
for(int idx = i+1; idx < j; idx+=2) {
long leftFalse = dp[i][idx-1][0];
long leftTrue = dp[i][idx-1][1];
long rightFalse = dp[idx+1][j][0];
long rightTrue = dp[idx+1][j][1];
if(exp.charAt(idx) == '&') {
if(isTrue == 1)
ans = (ans + (leftTrue*rightTrue)%mod) % mod;
else
ans = (ans + (leftFalse*rightFalse +
leftFalse*rightTrue + leftTrue*rightFalse)%mod) % mod ;
}
else if(exp.charAt(idx) == '|') {
if(isTrue == 1)
ans = (ans + (leftTrue*rightTrue +
leftTrue*rightFalse + leftFalse*rightTrue)%mod) % mod;
else
ans = (ans + (leftFalse*rightFalse)%mod) % mod;
}
else if(exp.charAt(idx) == '^') {
if(isTrue == 1)
ans = (ans + (leftTrue*rightFalse
+ rightTrue*leftFalse)%mod) % mod;
else
ans = (ans + (leftFalse*rightFalse
+ leftTrue*rightTrue)%mod) % mod;
}
}
dp[i][j][isTrue] = (int)ans;
}
}
}
return dp[0][n-1][1];
}
}
tabulation code :
vector dp(n+1, vector(n+1, vector(2, 0)));
for(int i = 0; i < n; i++) {
dp[i][i][1] = exp[i] == 'T';
dp[i][i][0] = exp[i] == 'F';
}
for(int i = n-1; i >= 0; i--) {
for(int j = i + 1; j < n; j++) {
for(int isTrue = 0; isTrue
#Tabulation code in python
def tabular(self,s):
n = len(s)
dp=[[[0 for i in range(2)] for j in range(n+1)] for k in range(n+1)]
for i in range(n):
for j in range(n):
for flag in range(2):
if i == j:
if flag :
dp[i][j][flag] = int(s[i]=='T')
# print("t",dp[i][j][flag])
else:
dp[i][j][flag] = int(s[i]=='F')
# print("f",dp[i][j][flag])
for i in range(n-1,-1,-1):
for j in range(n):
if i>=j:
continue
else:
for flag in range(2):
ans = 0
for ind in range(i+1,j,2):
lt = dp[i][ind-1][1]
lf = dp[i][ind-1][0]
rt = dp[ind+1][j][1]
rf = dp[ind+1][j][0]
if s[ind] == '&':
if flag:
ans += lt*rt
else:
ans += lf*rf + rt*lf + lt*rf
elif s[ind] == '|':
if flag:
ans += lt*rt + lt*rf + rt*lf
else:
ans += lf*rf
else:
if flag:
ans+= lf*rt + rf*lt
else:
ans+=lf*rf + lt*rt
dp[i][j][flag] = ans
return dp[0][n-1][1]
Tabulation code:
int n=exp.size();
vectordp(n,vector(n,vector(2,0)));
for(int i=n-1;i>=0;i--){
for(int j=i;j
tebulation code:
int n = arr.size();
vectordp(n+3,vector(n+3,vector(2,0)));
// return f(0,n-1,1,exp,dp);
for(int i=0;i=0;i--){
for(int j=i;j
16:30
Python Tabulation solution:
'''
Tabulation - Bottom Up from base case
TC = O(N ^ 3)
SC = O(N ^ 2 * 2) + No recursion depth
'''
n = len(exp)
mod = 1000000007
dp = [[[False for _ in range(2)] for j in range(n+1)] for i in range(n+1)]
# Base case
for i in range(n):
for j in range(n):
if i == j:
dp[i][j][0] = (exp[i] == 'F')
dp[i][j][1] = (exp[i] == 'T')
# Reverse of top down
# i -> 0 to n-1, j -> n-1 to 0
# But j has to be greater than i, so start j from (i + 1)
for i in range(n-1, -1, -1):
for j in range(i+1, n):
for evaluateTrue in range(2):
# will never execute, just for safety
if i > j:
continue
ways = 0
# Try all possible ways - Partition on operator
# Each operator is equidistant with 2 spaces
for sym_idx in range(i+1, j, 2):
# Left and Right expressions can be either True or False
left_true_ways = dp[i][sym_idx-1][True]
left_false_ways = dp[i][sym_idx-1][False]
right_true_ways = dp[sym_idx+1][j][True]
right_false_ways = dp[sym_idx+1][j][False]
# Based on the symbol, compute possibilities
if exp[sym_idx] == '&':
if evaluateTrue:
# Both left and right must be true
ways += (left_true_ways * right_true_ways)
else:
# left F right F/ left T right F/ left F right T
ways += ((left_false_ways * right_false_ways) +
(left_true_ways * right_false_ways) +
(left_false_ways * right_true_ways))
elif exp[sym_idx] == '|':
if evaluateTrue:
# Either of left or right or both can be True
ways += ((left_true_ways * right_true_ways) +
(left_true_ways * right_false_ways) +
(left_false_ways * right_true_ways))
else:
# Both left and right has to be false
ways += (left_false_ways * right_false_ways)
elif exp[sym_idx] == '^':
# XOR => returns T, if left and right have opp polarities
if evaluateTrue:
ways += ((left_false_ways * right_true_ways) +
(left_true_ways * right_false_ways))
else:
ways += ((left_true_ways * right_true_ways) +
(left_false_ways * right_false_ways))
dp[i][j][evaluateTrue] = ways % mod
return dp[0][n-1][1]
Gfg Tabulation (Approach 2):
Here I'll be travesing i and j only towards operands i.e. T or F instead of traversing i and j over each index
int countWays(int n, string s){
// code here
// vector dp(n,vector(n,vector(2,-1)));
// return solve(0,n-1,true,s,dp)%modulo;
vector dp(n,vector(n,vector(2,0)));
for(int i=0;i=0;i-=2){
for(int j=i+2;j
I did not understand , why are you taking solutions for false too because the question only asks for getting true , right?
Tabulation Code (Java):
import java.util.*;
public class Solution {
static int mod = 1000000007;
public static int evaluateExp(String s) {
int n = s.length();
int[][][] dp = new int[n][n][2];
for(int i=n-1;i>=0;i--){
for(int j=0;j
Tabulation code :
int tabulation(){
vector dp(n , vector(n , vector(2,0)));
// base case
for(int i=0;i=0;i--){
for(int j=i+1;j=0;isTrue--){
if(i>j) continue;
int ways = 0;
for(int ind =i+1;ind
Tabulation Code
#include
long mod = 1e9 + 7;
int evaluateExp(string & s) {
// Write your code here.
int n = s.length();
vector dp (n+1, vector(n+1, vector(2, 0)));
for (int i{}; i=0; i-=2){
for (int j{i+2}; j
Amazing work !!
Amazing man❤
The question linked to DP-52 in the A-Z sheet is wrong. Its of stack. Kindly fix it! Peace and love ❣
Hi, striver , what if we watch your video, by applying US VPN, do it will increase your earning, if yes we will do it.?
doesn't work like that
we just need true wale ways ,why we aree adding false wale ways ,and returning both
Tabulation Code with only 3 nested loops which got accepted on Interview Bit
const int MOD = 1003;
int Solution::cnttrue(string s) {
int n = s.size();
vector dp(n, vector (n, vector (2, 0)));
for(int i=0; i=0; i--){
for(int j=i; j
thnx striver
mja aaya sikh ke
Understood but i do not think it will be asked in interviews.
Tabulation Code:
int countWays(string &S){
const int mod=1e9+3;
int N=S.size();
// using tabulation
vectordp(N,vector(N,vector(2,0)));
for(int i=0;i=0;st-=2){
for(int en=0;en=en)continue;
int totTrues=0,totFalses=0;
for(int i=st+1;i
Understood 🥰
The same problem can be done by using stack without using mcm
why did we use multiply in finding no. of ways like X1 x X2
Maths 😅
coz we need to make whole exp think now
why do they use %mod for the result?
I just don't get it
Understood!!!Thank you
This is the tabulation code according to your approach:
unsigned int mod=1e9+7;
int evaluateExp(string & s) {
int n=s.size();
vector dp(n+1,vector(n+1,vector(2,0)));
for(int i=n-1;i>=0;i-=2){
if(s[i]=='T')
dp[i][i][1]=1;
else
dp[i][i][0]=1;
for(int j=i+2;j
heres the tabulation code
int n = exp.size();
vector dp(n+1,vector(n+1,vector(2,0)));
for(int i =0;i=0;i--){
for(int j=i+1;j