DP 52. Evaluate Boolean Expression to True | Partition DP
HTML-код
- Опубликовано: 2 май 2022
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/32tAMUW
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the question evaluate boolean expression to true.
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
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
I did knew MCM but it was not at all a cake walk
same ):
Same🥲
It motivated me
+1
Watching this again after 8 months, and I had entirely forgotten how to solve this one. Thanks again for making it clear!
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 🤯
The way of thinking its recursion aproach is beyond my imagination! GreatWork! US!
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 ❤️
correction:- Insted of on an operand* it's on an operator 6:40
Understood!! Thank you soooooo much as always!!
Understood, Thank you so much Striver
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]
Thank you so much for this!! I can't imagine learning DSA without you❤
Understood well!! Awesome explanation
Thank you
Understood!
Amazing work !!
Understood. Thankyou Sir
Thank you striver❤
Really well explained.
#understood
Please add more videos to this playlist striver ,we really need them
Understood 😊
Appreciate your efforts 🙏
As always "understood" ❤️
awesome explanation as always💥💥
Understood, sir. Thank you very much.
Very Nice explanation,one of the easiest lecture on partition dp.
Understood!!!Thank you
Understood, thanks
Understood ❤❤❤❤
Amazing explanation
Understood, thanks!
understood!!
thnx striver
understood after waching the video twice or thrice....This is really a tough question
Understood Sir, Thank you very much
"UNDERSTOOD" as always!
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?
Understood💙
Just WOW!!
Amazing man❤
why did we use a "x" in and operator
I was getting confused initially when you were saying operand instead of operator. You can add a note on video about it
UnderStood amazing💥
Understood !!!!!
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)
understood
Understood!!! But mind twisting!
Understood
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.
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?
Striver please make a playlist on bit manupulation
Understood !
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
I came up with the solution , it took me about 1.5 hour but i did it, all thanks to 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
Understood 🥰
Understood !!
Understood 😊😊
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
understoood
Great
Understood.
hey struver i did'nt understand why you are mutiplying the lt lr etc
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 ...
mja aaya sikh ke
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!
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.
UNDERSTOOD
Tabulation Code:
int evaluateExp(string &exp) {
vector dp(exp.size(),vector(exp.size(),vector(2,0)));
for(int i=exp.size()-1;i>=0;i--){
for(int j=i;j
why do they use %mod for the result?
I just don't get it
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
**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
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
understood💝🧡💝
why did we use multiply in finding no. of ways like X1 x X2
Maths 😅
coz we need to make whole exp think now
The leetcode question has a slight variation.can anyone explain to me that
*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
Understood Sir :)
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
leetcode m nhi h kya ye?
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
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.
The question linked to DP-52 in the A-Z sheet is wrong. Its of stack. Kindly fix it! Peace and love ❣
we just need true wale ways ,why we aree adding false wale ways ,and returning both
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
Whys we are doing ways+=
CFBR
op
I tried solving without watching the video, my solution is accepted in gfg, but not in code studio
Operand will be a operator, right?
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
Understood but i do not think it will be asked in interviews.
#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]
US striver , Diffucult one , No way i would have got this in interview
understood :-)
I think striver also has to go through the solution to explain this kinda problems
tough question
US
i am getting wrong answer in CodingNinja's platform ( 10/11 test cases passed) need help
same
Must be due to typecasting from Long back to int