Also in most the dp problems after reading the statement you're like how would I know what will be the best way↵
so definitely we have to try everything but in a smarter way that's nothing by dp. and also low constraints is another big hint.↵
↵
so first step to see understand the question clearly and see how the process would look like means imagine any general scenario↵
then let's assume we know the optimal way and see how any general ans would look like (means maybe we have to choose some indices or whatever)↵
Then maybe analyzing the PROPERTIES of general ans would help (like you can make some easy observation that length can't be too large there can't be two even no.↵
or any sort of observation) and then many time it turns out that the general structure of our ans is not too typical and we can maybe brute force or Binary search ↵
means the problems becomes approachable after that and we'll definitely get to the final solution after this.↵
↵
so the main part is to see the general ans and making some claims about it.↵
Example : recent global round 18 C problem is completely solvable just by this.↵
↵
Why am I telling all this? because it helps a lot in dp and in any problem.↵
Let's take the well known longest common subsequence problem ... ↵
First it's easy to understand the solution after seeing it.. you should know the reason why we choose that state not more and not less why?↵
so in the optimal subsequence (be it any) we will choose some of the characters from s1 and same chars from s2↵
so let's construct our ans and if we pause the video at any moment in the process of selecting indices of our optimal ans↵
we are left at some position in s1 and some in s2 and we don't know what to take next bcoz we are not GOD right?↵
this means we should try every thing means if we have made suppose acca so we should try every next char 'a' to 'z' and see the next closest position of that char in s1 and then in s2 if available↵
and try every character this way... we can do this way by precomputing next closest character alag se but it's not needed because dp is all about being smart ...↵
so if we are at i index in s1 and j in s2 and if we again play and pause our optimal ans construction video we will see that we will either take i+1 and match it will some char after index j in s2 or we ↵
don't take i+1 similarily with j+1 in s2 and as soon as we reach just before our taking the optimal indexes in both strings means i+1 and j+1 and obviously s1[i+1]=s2[j+1] then we will take it.↵
so we will either skip i+1(and not j+1 in the hope it may combine with some future i), skip j+1, skip both, or take i+1 and j+1 in our ans... these 4 ways↵
↵
Long description na? well done if you actually read it..↵
Do this LCS problem after reading complete thing : https://codeforces.me/contest/1584/problem/F↵
↵
Firstly, just like Binary search any and every question can be solved using Dp(after monotonic reasoning in BS). It's which is easy to do and do the constraints↵
allow us or we have to find some greegdy thing) so don't think ye question dp ka tha ye nhi tha it will create unnecessary stress.↵
It's the most common and often used techniques in problems, so knowing it before hand and thinking along that lines helps a lot.↵
↵
Now my made(or copied) process of solving dp problems..↵
after you have understood the question made some observations your ans and ready to find that using dp.↵
Then you should think after making some of your ans in the halfway what things you should know and keep in mind↵
to complete your ans.↵
1. Obviously how much part of your array you have used in making your ans till this point. means the prefix of array used or index you're at.↵
2. sometimes some properties of made ans affect the remaining part of ans.. suppose there is constraint on sum on no's you pick or you wan't sum to be divisible by p then you should keep the sum%p.↵
3. some flag maybe you have some option which you can use only once so whether you used that chance or not↵
4. whatever the statement says..↵
5. and obviously the ans which you'have made so far otherwise what's the point if you don't remember what you've done at the end.↵
In most of the cases you will keep some aggregate value of the indexes you have choosen till now depending upon what's asked and not the vector of all indices you've choosen so far.↵
but if you have to keep exact indices you've choosen then in most cases N is small N<=20 so you can keep a mask of choosen indices. even if that's not the case then maybe you will keep complete vector of choices (but then basically it's↵
brute force recursion) or maybe you're wrong(almost 99% sure). or it depends↵
↵
Now, you've made a list of all the things you need to keep in mind while making your ans.↵
see the list carefully and check every thing once more can you drop it somehow.↵
↵
and out of all the things obviously which have largest range make it your value of dp and rest all your states.↵
because you will try every value of states and calculate ans for every of them (though many of them are even not possible and sensible↵
Because we can keep all the things in state and make the value of dp to be (boolean is it possible) ↵
and iterate over all possible states and answers(kept in state) and if it's possible consider that as an answer. ↵
But we're not dumb we will make one(the max one) state value of your dp.↵
↵
and after that you'll compute the complexity means multiply all the Max value of each state and see if it fits in time↵
then time to think about transitions and if not then rethink.↵
↵
States are like you fix somethings like length of prefix of array, sum of numbers, count of some special numbers taken, ↵
and after fixing these things you're trying to find your answer. Means you're basically making your problem easy by solving ↵
shorter version of that(considering only some prefix of array) and imposing some constraints yourself and then try to find ans (means no of ways of min/max something)↵
because the constraints allow us to fix somethings at our end.↵
↵
Just like in binary search some restrictions question give and some we impose ourselves by fixing mid and then try to solve the problem if this mid is fixed↵
means simplified our problems and then get some greedy idea to check whether that mid is possible or not.↵
That mid is same as state in dp.↵
↵
As you might know transition are nothing just edges in our DAG of states.↵
we have made our states by making our answer in halfway .. so time to complete that answers ↵
then what are the next choices or decisions we should make to complete that answer ... ↵
we should consider that choice and after choosing our states will change and we should update the answer to that newly achieved state.↵
This way of updating the states after making decisions is called push DP. (we are pushing current value to future values)↵
We're at current state and thinking what are the possible options to go to some other state and update their values.↵
So in this way whenever we reach at any state it's correct value is stored in it bcoz all the states which can possiblly ↵
update it's answer are already visited and all future states we're going to visit will never update it. so it's value is final.↵
Basically all the states v such that v--> cur is an edge is already explored. And there must exist some order of exploring the states like this ↵
since it's DAG and we can go in order of top sort means the states which have no incoming edges first(indegree==0, these are called base case) and so on..↵
↵
↵
One another way is to think like is we try to compute value of current state so we think how we could have ↵
reached this state and compute it's ans by all the smaller states.↵
Again we have to make sure all the smaller states have their correct answer stored.↵
↵
Now what makes the difference in Leetcode and CF DP problem is that.. in leetcode constraints are too low↵
and as you make your list of things you've to keep in mind it fits in time just code and submit. ↵
That's not the case with CF. you have to practice problems and learn how to optimize your list of things and don't think it's unsolvable and loose hope.↵
REMEMBER The most Beautiful part about CF is that the problems are solvable and that's gives us the hope to fuck our mind for hours in that.↵
↵
time complexity : ↵
(multiply all max limits for states)*(Transition time to calculate one state)↵
↵
I think that's all. ↵
The next part is after you have done that part on paper (after some practice you can do that in mind in minutes).↵
is HOW TO IMPLEMENT THIS↵
one beautiful part is if you've not made any mistake in considering your choices and it fits in time.. congrats you've the right solution and it will ↵
definitely pass ... maybe this is not the intended solution by author.↵
SO the second last part is to write.↵
↵
you can practice writing recursive codes in start and shift to iterative when you're comfortable with that paper wala part.↵
↵
Also since samples are small you should first try your approach step by step on samples then move on to implement.↵
Last is what if you get wrong on samples. You should be good at printing stuff and identify what's going not according to you.↵
↵
↵
as you learn there are some after stuff too.. since it's important topic there a lot of types of variation.↵
Like ↵
1. (It's not rare btw) One common thing is slightly twist your definition of dp and instead of best ans if this this state.. change to min index to achieve this ans↵
2. You can binary search on one of your states.↵
Like this wonderful problem(https://codeforces.me/contest/1550/problem/E) it uses both points above.↵
↵
And also there are also combination of topics like contribution to sum, probability(Expected value).↵
↵
GOOD LUCK! Thanks for reading and baring with my horrible english.
so definitely we have to try everything but in a smarter way that's nothing by dp. and also low constraints is another big hint.↵
↵
so first step to see understand the question clearly and see how the process would look like means imagine any general scenario↵
then let's assume we know the optimal way and see how any general ans would look like (means maybe we have to choose some indices or whatever)↵
Then maybe analyzing the PROPERTIES of general ans would help (like you can make some easy observation that length can't be too large there can't be two even no.↵
or any sort of observation) and then many time it turns out that the general structure of our ans is not too typical and we can maybe brute force or Binary search ↵
means the problems becomes approachable after that and we'll definitely get to the final solution after this.↵
↵
so the main part is to see the general ans and making some claims about it.↵
Example : recent global round 18 C problem is completely solvable just by this.↵
↵
Why am I telling all this? because it helps a lot in dp and in any problem.↵
Let's take the well known longest common subsequence problem ... ↵
First it's easy to understand the solution after seeing it.. you should know the reason why we choose that state not more and not less why?↵
so in the optimal subsequence (be it any) we will choose some of the characters from s1 and same chars from s2↵
so let's construct our ans and if we pause the video at any moment in the process of selecting indices of our optimal ans↵
we are left at some position in s1 and some in s2 and we don't know what to take next bcoz we are not GOD right?↵
this means we should try every thing means if we have made suppose acca so we should try every next char 'a' to 'z' and see the next closest position of that char in s1 and then in s2 if available↵
and try every character this way... we can do this way by precomputing next closest character alag se but it's not needed because dp is all about being smart ...↵
so if we are at i index in s1 and j in s2 and if we again play and pause our optimal ans construction video we will see that we will either take i+1 and match it will some char after index j in s2 or we ↵
don't take i+1 similarily with j+1 in s2 and as soon as we reach just before our taking the optimal indexes in both strings means i+1 and j+1 and obviously s1[i+1]=s2[j+1] then we will take it.↵
so we will either skip i+1(and not j+1 in the hope it may combine with some future i), skip j+1, skip both, or take i+1 and j+1 in our ans... these 4 ways↵
↵
Long description na? well done if you actually read it..↵
Do this LCS problem after reading complete thing : https://codeforces.me/contest/1584/problem/F↵
↵
Firstly, just like Binary search any and every question can be solved using Dp(after monotonic reasoning in BS). It's which is easy to do and do the constraints↵
allow us or we have to find some gree
It's the most common and often used techniques in problems, so knowing it before hand and thinking along that lines helps a lot.↵
↵
Now my made(or copied) process of solving dp problems..↵
after you have understood the question made some observations your ans and ready to find that using dp.↵
Then you should think after making some of your ans in the halfway what things you should know and keep in mind↵
to complete your ans.↵
1. Obviously how much part of your array you have used in making your ans till this point. means the prefix of array used or index you're at.↵
2. sometimes some properties of made ans affect the remaining part of ans.. suppose there is constraint on sum on no's you pick or you wan't sum to be divisible by p then you should keep the sum%p.↵
3. some flag maybe you have some option which you can use only once so whether you used that chance or not↵
4. whatever the statement says..↵
5. and obviously the ans which you'have made so far otherwise what's the point if you don't remember what you've done at the end.↵
In most of the cases you will keep some aggregate value of the indexes you have choosen till now depending upon what's asked and not the vector of all indices you've choosen so far.↵
but if you have to keep exact indices you've choosen then in most cases N is small N<=20 so you can keep a mask of choosen indices. even if that's not the case then maybe you will keep complete vector of choices (but then basically it's↵
brute force recursion) or maybe you're wrong(almost 99% sure). or it depends↵
↵
Now, you've made a list of all the things you need to keep in mind while making your ans.↵
see the list carefully and check every thing once more can you drop it somehow.↵
↵
and out of all the things obviously which have largest range make it your value of dp and rest all your states.↵
because you will try every value of states and calculate ans for every of them (though many of them are even not possible and sensible↵
Because we can keep all the things in state and make the value of dp to be (boolean is it possible) ↵
and iterate over all possible states and answers(kept in state) and if it's possible consider that as an answer. ↵
But we're not dumb we will make one(the max one) state value of your dp.↵
↵
and after that you'll compute the complexity means multiply all the Max value of each state and see if it fits in time↵
then time to think about transitions and if not then rethink.↵
↵
States are like you fix somethings like length of prefix of array, sum of numbers, count of some special numbers taken, ↵
and after fixing these things you're trying to find your answer. Means you're basically making your problem easy by solving ↵
shorter version of that(considering only some prefix of array) and imposing some constraints yourself and then try to find ans (means no of ways of min/max something)↵
because the constraints allow us to fix somethings at our end.↵
↵
Just like in binary search some restrictions question give and some we impose ourselves by fixing mid and then try to solve the problem if this mid is fixed↵
means simplified our problems and then get some greedy idea to check whether that mid is possible or not.↵
That mid is same as state in dp.↵
↵
As you might know transition are nothing just edges in our DAG of states.↵
we have made our states by making our answer in halfway .. so time to complete that answers ↵
then what are the next choices or decisions we should make to complete that answer ... ↵
we should consider that choice and after choosing our states will change and we should update the answer to that newly achieved state.↵
This way of updating the states after making decisions is called push DP. (we are pushing current value to future values)↵
We're at current state and thinking what are the possible options to go to some other state and update their values.↵
So in this way whenever we reach at any state it's correct value is stored in it bcoz all the states which can possiblly ↵
update it's answer are already visited and all future states we're going to visit will never update it. so it's value is final.↵
Basically all the states v such that v--> cur is an edge is already explored. And there must exist some order of exploring the states like this ↵
since it's DAG and we can go in order of top sort means the states which have no incoming edges first(indegree==0, these are called base case) and so on..↵
↵
↵
One another way is to think like is we try to compute value of current state so we think how we could have ↵
reached this state and compute it's ans by all the smaller states.↵
Again we have to make sure all the smaller states have their correct answer stored.↵
↵
Now what makes the difference in Leetcode and CF DP problem is that.. in leetcode constraints are too low↵
and as you make your list of things you've to keep in mind it fits in time just code and submit. ↵
That's not the case with CF. you have to practice problems and learn how to optimize your list of things and don't think it's unsolvable and loose hope.↵
REMEMBER The most Beautiful part about CF is that the problems are solvable and that's gives us the hope to fuck our mind for hours in that.↵
↵
time complexity : ↵
(multiply all max limits for states)*(Transition time to calculate one state)↵
↵
I think that's all. ↵
The next part is after you have done that part on paper (after some practice you can do that in mind in minutes).↵
is HOW TO IMPLEMENT THIS↵
one beautiful part is if you've not made any mistake in considering your choices and it fits in time.. congrats you've the right solution and it will ↵
definitely pass ... maybe this is not the intended solution by author.↵
SO the second last part is to write.↵
↵
you can practice writing recursive codes in start and shift to iterative when you're comfortable with that paper wala part.↵
↵
Also since samples are small you should first try your approach step by step on samples then move on to implement.↵
Last is what if you get wrong on samples. You should be good at printing stuff and identify what's going not according to you.↵
↵
↵
as you learn there are some after stuff too.. since it's important topic there a lot of types of variation.↵
Like ↵
1. (It's not rare btw) One common thing is slightly twist your definition of dp and instead of best ans if this this state.. change to min index to achieve this ans↵
2. You can binary search on one of your states.↵
Like this wonderful problem(https://codeforces.me/contest/1550/problem/E) it uses both points above.↵
↵
And also there are also combination of topics like contribution to sum, probability(Expected value).↵
↵
GOOD LUCK! Thanks for reading and baring with my horrible english.
