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.
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.
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.
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 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.