in the definition of the node just replacing vector into an array ie int val [2][2] gives ac to your solution .. the problem was you are using too many resizes using the vector..also you could use ios_base::sync blah blah to further improve on it
Thanks!Vector to array was a nice catch. Also I don't think ios_base applies here as the input and output is performed before our function is call, did you ever try that in the past in leetcode?
When merging the node, why is it ans[i][j] = max(ans[i][j], lft[i][k] + rgt[1 - k][j]) ? Do we have to also consider this case: lft[i][0] + rgt[0][j], where last element of lft and first element of rgt is not selected
You can consider that case as well but that should already be covered in rgt[1][j] because the definition of the values in this array is "what is the maximum value we can have if we start with this index". Therefore if there is a scenario where not choosing the 1st index would yield better results, the value will reflect the same. Hope that clarifies.
I tried by creating segmentTree of vector of size 4 instead of Struct Node and it passed all test case . I meant Tree.resize(4*n,vector(4,0)) I must say thank tou for the efforts you put in to explain. beautiful explanation
![3098. Find the Sum of Subsequence Powers | 4D DP | time- O(n^5) [*will be updated for O(n^4)]](http://i.ytimg.com/vi/3go6vNha0Do/mqdefault.jpg)
Superb Explanation sir🔥
in the definition of the node just replacing vector into an array ie int val [2][2] gives ac to your solution .. the problem was you are using too many resizes using the vector..also you could use ios_base::sync blah blah to further improve on it
Thanks!Vector to array was a nice catch.
Also I don't think ios_base applies here as the input and output is performed before our function is call, did you ever try that in the past in leetcode?
@@codingmohan i didnt believe in it too.. but i could see some 50 ms improvement for 350 ms run time...
you waited? of course.
Block placement query is easier than Maximum sum of subsquence...
True
Superb 🔥. Can you solve the Biweekly Contest 131 4th question ?
When merging the node, why is it ans[i][j] = max(ans[i][j], lft[i][k] + rgt[1 - k][j]) ? Do we have to also consider this case: lft[i][0] + rgt[0][j], where last element of lft and first element of rgt is not selected
You can consider that case as well but that should already be covered in rgt[1][j] because the definition of the values in this array is "what is the maximum value we can have if we start with this index". Therefore if there is a scenario where not choosing the 1st index would yield better results, the value will reflect the same.
Hope that clarifies.
Thank you sir!
Awesome explanation! Thankyou Mohan!!
Awesome question, awesome explanation
Awesome explanation, thake you bhaiya ❤
I tried by creating segmentTree of vector of size 4 instead of Struct Node and it passed all test case . I meant Tree.resize(4*n,vector(4,0))
I must say thank tou for the efforts you put in to explain. beautiful explanation
great explanation!
Awesome Explanation
nice explanation
sir could you plz make video on block placement queries
Thank you sir!