Hello everyone,
Can anyone please suggest me some good and easy dynamic programming problems to start on HackerRank? Or on Codechef? And please also suggest how to learn dynamic programming. I tried the SECO problem on the SEP17 competition, I think I got the logic but wasn’t able to implement it, tried reading the editorial but it went over my head!! If anyone can help me with that problem too because I think it also involves dynamic programming.
Thanks in advance!!
For leaning DP as a beginner, start from leaning the basic concepts of dp. HERE
are the examples of the problems which involve dp. First understand where and why we use DP.
Secondly SEACO problem of sept17 had max time complexity of O(nlogn). Using DP will cost you TLE. O(n*n)
So you need to learn segment trees for 100 points. For doing it using DP you can have a look at my solution for 50 points which i did initially here.
Feel free to ask if you didn’t get it.
Thank you, that helps, so we cannot solve SECO for 100 without trees?
There is a method to do it without trees as well. I used square root decomposition to reduce my O({N}^{2}) to O(N\sqrt{N})
Hackerrank does not have “easy” dp problems. All of them are medium or hard. Try codeforces and codechef. Sort problems by their tags, and give an attempt. If you fail (which you will in start), first look at pre-requisites. Learn that thing, and attempt the problem later again.
Keep doing this until you solve the problem. This is the learning curve, and efforts have to be put in at the end of the day.
How do I find the dp problems on codechef? Is there a search bar?
At homepage, on the left you will see “Tag” . There are tags like “dp” “segment-tree” “cakewalk” etc. using which we can sort the problems.
Thank you you’re the best
Why not.
I have a total of M commands. The thing causing TLE is that, lets say I give commend 2 1 1000. Now we have to repeat commands from 1 to 1000 again. In short, we have to iterate through M commands for upto M times, which can give TLE.
What if I “group” the commands? Eg, make an array “update[N/1000]”. If all commands in range [1,999] are to be updated, I increased update[999/1000]=update[0] by 1. You see that we saved time, instead of increasing counter of 1000 commands, we updated 1 element of our array. It significantly reduces the time taken.
Yup 
Thanks!!
To solve SEACO question in linear time, you may refer to my explanation here and my code here,
No trees, Just difference arrays and sum arrays again and again… !!!
I know the code appears a bit complex at first…(to me too )
But if you are comfortable with difference arrays, you should have no problem understanding it!!
Feel free to ask anything…
Please upvote…