Great Explaination !! I was a bit confused at first but looking at 18:10 again, fired some extra neurons in my brain😂. Excellent job man.. a person needs to have very deep understanding to explain like this..! Hats off...
This is by far the best explanation for this problem! I understood what to do after only watching the Type 1 cases, and the Type 2 cases naturally made sense without watching it :)
Great explaination!! O(t.n) gave TLE. I tried so many times still I got TLE so I optimised it to O(t+n) as you said that it's homework XD. Code for Ref: #include using namespace std; int mod=1e9+7; int maxn=1e6+1; vector dp(maxn,vector(2)); vector ans(maxn); int main() { ios_base::sync_with_stdio(0); cin.tie(0); dp[0][0]=1; dp[0][1]=1; for(int i=1;i>t; while(t--) { int n;cin>>n; cout
#Day 11 Again late To watch Video But Problem and The Explnation Lost My Sleeep.... The Problem is overhelming by looking the problem i was telling ki aisa explain to koi nhi kar sakta if some one ask me na ki bro explain me this problem i'll also do same thing because now i understand it very well but as a good student i should repeat lecture 2 time so i'll grasp the better understanding....Thanks you So much Priaynsh 😊😊😊😊 And Also You add wrong Links of Problem it'll jump to array Description...
The explanation is good but it would be great if you have said how this will actually cover all cases like how does this covers placing a block of size 1 2 3.. and horizantal block of diff sizes
#include #include #define End " " using namespace std; int mod = 1e9 + 7; /* type 1 block is block with width 1 type 2 block is block with width 2 at every index we if have type 1-1 block at i-1th index-> we have options 1st. to allow left one 2nd to allow right one 3rd to allow both 4th close both and start new 2 blocks of 1-1 type 5th close both and start a double block of type 2 if we have type 2 block at last index we have options 1st to grow the double block 2nd to stop it and start 2 blocks of 1-1 type 3rd to stop it and start and new double block of type 2 */ int dp[1000001][3]; long long countingTowers(int n, int type) { if (n == 1) return 1; if (dp[n][type] != -1) return dp[n][type]; if (type == 1) { // out of 5 ways 4 are where we use type 1 block , and 1 is we use type 2 long long ans = ((4 * countingTowers(n - 1, 1)) % mod + countingTowers(n - 1, 2) % mod) % mod; return dp[n][type] = ans; } else { long long ans = (2 * (countingTowers(n - 1, 2)) % mod + countingTowers(n - 1, 1) % mod) % mod; return dp[n][type] = ans; } } int main() { int t; cin >> t; memset(dp, -1, sizeof(dp)); while (t--) { int n; cin >> n; int ans = (countingTowers(n, 1) + countingTowers(n, 2)) % mod; cout
Homework completed . new dp state -> dp[I][0]/dp[I][1]=no of ways to fill the grid from (i-1)th row to n such that there is a horizontal/vertical block trying to extend to (i+1)th row . Pre-computation outside code -> #include using namespace std; const int mod=1e9+7; vector dp(1e6+1,vector(2)); void solve(){ int n; cin >> n; cout
How did you came to this approach i mean i just not able to see things like this i know practice is the thing but is there something idea to target these type of problems, well when did you continue this series.
Hey priyansh , I have done dsa all the data structures and all algorithms like binary search bit manipulation graphs algorithm greedy dp sliding window two pointers. I have also done 170 questions on leetcode But never been to competitive programming or codeforces Which level should I start on tle eliminators ?
You can go for either level 3 or 4. At TLE we don’t just focus on the basics but also go deep in a topic so just saying that you have done all the DSA might not be the right way to pick a level. I would suggest first completing level 3 and then going for level 4 in the next batch.
The base case according to how the state has been defined is dp[n][1] = 1, dp[n][0] = 1 Remember what is the state: dp[i][0], dp[i][1] are number of ways to fill the tower from ith row to the n-1th row. Hence your final subproblem will be dp[0][0] + dp[0][1]
@@TLE_Eliminators I understood on why we go only until 1 and not until 0 because if we go until 0 we would be counting for n+1 height instead of n. I think you meant dp[1][0] + dp[1][1] for the final subproblem
Looking at the question u can't even think of anything, great explanation man
Exactly, like mentioned in the video, I (Priyansh) also struggled very hard with this one long back
Trying to find a solution in VietNamese, but... you literally blow a breath of fresh air to my mindset of dp by your explaination. Thank you
Great Explaination !! I was a bit confused at first but looking at 18:10 again, fired some extra neurons in my brain😂. Excellent job man.. a person needs to have very deep understanding to explain like this..! Hats off...
Haha thank you❤
This is by far the best explanation for this problem! I understood what to do after only watching the Type 1 cases, and the Type 2 cases naturally made sense without watching it :)
By far, the best explanation to this problem.
Great explaination!! O(t.n) gave TLE. I tried so many times still I got TLE so I optimised it to O(t+n) as you said that it's homework XD.
Code for Ref:
#include
using namespace std;
int mod=1e9+7;
int maxn=1e6+1;
vector dp(maxn,vector(2));
vector ans(maxn);
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
dp[0][0]=1;
dp[0][1]=1;
for(int i=1;i>t;
while(t--)
{
int n;cin>>n;
cout
Amazing.
Even I'm getting TLE for O(n * t) not sure why. If my code is similar to the one in video.
Just a quick follow up....
int MOD won't work
but u can try const int MOD and O(n * t) will pass.
Extremely good explanation. Thank you very much.
Great Explanation!
understood at another level
Finally Understood the solution
Just small suggestion
Horizontal -> width (2)
Vertical -> width (1)
Thanks for uploading it.
Haha yes, that might have been a bit confusing.
You really should make CSES GRAPH solution.
Kudos bro...!! Wonderful explanation
#Day 11 Again late To watch Video But Problem and The Explnation Lost My Sleeep.... The Problem is overhelming by looking the problem i was telling ki aisa explain to koi nhi kar sakta if some one ask me na ki bro explain me this problem i'll also do same thing because now i understand it very well but as a good student i should repeat lecture 2 time so i'll grasp the better understanding....Thanks you So much Priaynsh 😊😊😊😊 And Also You add wrong Links of Problem it'll jump to array Description...
Great explanation
Hats off man!
i find this question much more easier than array description \0=0/ # understood
Excellent explanation.
The explanation is good but it would be great if you have said how this will actually cover all cases like how does this covers placing a block of size 1 2 3.. and horizantal block of diff sizes
Great explanation 💥
Great explanation !! Understood very well
amazing solution :))
#include
#include
#define End "
"
using namespace std;
int mod = 1e9 + 7;
/*
type 1 block is block with width 1
type 2 block is block with width 2
at every index we if have type 1-1 block at i-1th index->
we have options
1st. to allow left one
2nd to allow right one
3rd to allow both
4th close both and start new 2 blocks of 1-1 type
5th close both and start a double block of type 2
if we have type 2 block at last index
we have options
1st to grow the double block
2nd to stop it and start 2 blocks of 1-1 type
3rd to stop it and start and new double block of type 2
*/
int dp[1000001][3];
long long countingTowers(int n, int type)
{
if (n == 1)
return 1;
if (dp[n][type] != -1)
return dp[n][type];
if (type == 1)
{
// out of 5 ways 4 are where we use type 1 block , and 1 is we use type 2
long long ans = ((4 * countingTowers(n - 1, 1)) % mod + countingTowers(n - 1, 2) % mod) % mod;
return dp[n][type] = ans;
}
else
{
long long ans = (2 * (countingTowers(n - 1, 2)) % mod + countingTowers(n - 1, 1) % mod) % mod;
return dp[n][type] = ans;
}
}
int main()
{
int t;
cin >> t;
memset(dp, -1, sizeof(dp));
while (t--)
{
int n;
cin >> n;
int ans = (countingTowers(n, 1) + countingTowers(n, 2)) % mod;
cout
Very nicely explain
understood badhiiya tha bro
absolute Magic
Homework completed .
new dp state -> dp[I][0]/dp[I][1]=no of ways to fill the grid from (i-1)th row to n such that there is a horizontal/vertical block trying to extend to (i+1)th row .
Pre-computation outside code ->
#include
using namespace std;
const int mod=1e9+7;
vector dp(1e6+1,vector(2));
void solve(){
int n; cin >> n;
cout
Perfect. That's exactly what was required.
Yes I also do the same thing but i was confused what was this LL 🤐🤐 and why we are using this without that the answer is wrong
@@musaddikkhan9720LL is long long
understood
How did you came to this approach i mean i just not able to see things like this i know practice is the thing but is there something idea to target these type of problems,
well when did you continue this series.
pls make solution of "Projects"
Hey priyansh , I have done dsa all the data structures and all algorithms like binary search bit manipulation graphs algorithm greedy dp sliding window two pointers. I have also done 170 questions on leetcode
But never been to competitive programming or codeforces
Which level should I start on tle eliminators ?
You can go for either level 3 or 4. At TLE we don’t just focus on the basics but also go deep in a topic so just saying that you have done all the DSA might not be the right way to pick a level. I would suggest first completing level 3 and then going for level 4 in the next batch.
I am unable to understand why did we return dp[1][0] + dp[1][1] instead of dp[0][0] + ...? The base case was already handled right
The base case according to how the state has been defined is dp[n][1] = 1, dp[n][0] = 1
Remember what is the state: dp[i][0], dp[i][1] are number of ways to fill the tower from ith row to the n-1th row. Hence your final subproblem will be dp[0][0] + dp[0][1]
@@TLE_Eliminators I understood on why we go only until 1 and not until 0 because if we go until 0 we would be counting for n+1 height instead of n. I think you meant dp[1][0] + dp[1][1] for the final subproblem
😭