Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

mac_n_cheese_pog's blog

What is DP,seriously
By mac_n_cheese_pog, history, 3 years ago, In English

This will most likely be my last blog about dp since i have given up on cp communities.noone is helping me nor even caring to me.whenever i ask someone they think im just trolling when im being dead serious.

dynamic programming,what is it? dynamic programming is the technique of optimization.instead of bruteforcing,we can just do dp.which is convenient.there are 2 ways.recursion with memoization and filling arrays(basically all memoization).

sounds simple right? lets move on to the example.there are alot of classical dp problems like 0-1 knapsack,prefix sum,catalan numbers and so on.it might be hard if u do them for the first time.but as time goes on,it will become easier.

now to the real deal.how to do it in contest when its not classical problems.like modified knapsack wheremaybe 1 item cannot be taken twice or maybe every i-th taking process some value will cut down into n/2 because of some reason and many more.now you are solving a brand new problems.can you? this is equivalent of making a brand new algorithm,but in this case its just modifying but still it requires thinking and impossible to do within contest time.

most tutorials will say identify,think about states and youre done.yea thats it.thats basically what dp is about.but about getting the exact states that the problem wants? im not so sure if everyone can do that unless by doing similar problems(not classical but the exact same type of problem that is given to you).

what ur going to do in this situation? ask? if you have someone that u can rely on then good,it would be easy.but what if someone just trolls you everytime and ignore you because they are better than you and not worht of their time? do u think this is just beyond rude?.u will just fall into the pit of desperation and cant do anything since you cant adapt and noone is guiding.u will just become a cheater if u are really desperate to have better(i think most cheater are in this case,correct me if im wrong).but for someone that doesnt want to cheat and improve purely? how? like a clueless baby that try to stay alive without a parent,u will eventually fail.trust me,u will.u will just make a blog on how to improve and people will say u suck,not worth of cp and probably tell you just quit cp ur not smart enough.

the point of making this blog is just to remind people that sometimes,learning an algorithm is not worth your time.its just really abstract that people just make random proof for the sake of editorial content.

perhaps someone can convince me that dp is not that hard? but i think at this stage noone will ever change my mindset.

goodbye

  • Vote: I like it
  • -27
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
3 years ago, # |
  Vote: I like it +35 Vote: I do not like it

noone is helping me nor even caring to me

This is a very much false claim. For example, I did try to help you with figuring out how to do binary search. But you were obviously not interested.

perhaps someone can convince me that dp is not that hard?

What for? To be ignored again?

goodbye

Good luck in your future endeavors.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i never ignore people.im just confused why u gave binary search tutorial to me.i said there its a quick binary search tutorial i dont need help at that time.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Is this new blog your quick DP tutorial and you actually don't need any help either?

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

Practice! This is the best method to improve DP skills!

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

On most of the easier DPs (I'm assuming your level, sorry), you should think about any recursion that solves you problem and use memoization on that.

And if you wanna do it bottom-up, you think about a order to fill your DP that guarantees that a value needed will be always calculated before it was needed (look at your recursion again to know that).

You can't improve on DP just by searching classical problems, they are useful just on a little part of the DPs problems.

About the "learning a algorithm is not worth your time" and "become a cheater because wants to be better", it looks like you are just trolling.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    then how am i going to improve? ive searched dp problems in codeforces and they are too hard,while the easy ones are solvable with math ,which is not that good tbh cuz mostly the editorial only provide math solution.atcoder has good dp problems but i think its still not enough.what problems should i do

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      When you find a problem that have a DP tag, it's because someone solved it with DP, so you can solve it with DP. Look on the comments on editorial and maybe you find any soluton. You should notice that most experienced users will solve the easier problems with really simple algorithms, while other will "overkill" with DP. But if you wanna be better at DP, just overkill it.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how am i going to overkill when i dont even know what the dp approach is?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I just said, if a problem has the tag DP, dont mind if the editorial has simple math, use it to train DP because it can be solved with DP too. You dont have to start practice with harder problems because DP is needed on them.

          → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
void solve_dp() {
    // this works for 90% of <= 2500 rated problems
    while (transitions_too_slow()) add_states();
    while (states_too_many()) add_greedy_and_ds();
}
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

At low elo, you probably don't want to challenge too many hard DP problems, DP is not magic, it is doable, just that you'll probably find it hard. Why? DP involves dealing with states and transitions, knowing which ones are necessary and which aren't, I.e. they basically overcomplicate things. This is not very intuitive in the beginning.

Look at the code written by high rated coders, their thought process is quite refined. They don't take a lot many unnecessary variables, with time anyone and everyone can do that. So practice a lot, build generic problem solving skills. When you know the basics, you build an understanding of the applications of each algorithm/technique/data structure. At which point it becomes easier to pinpoint the exact one required and work in that direction.

My advice: Work on problems on Implementation/Greedy/Binary Search/Prefix Sums/Maps/Sets etc until you're stable pupil. At which point you can dive into DP without getting burned.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my friend said if u want to do dp then practice.so i decided to practice atcoder dp and in other judge.i feel dp is so random,like genuinely random.others like binary search has easy idea or prefix sums.map and sets i can use both no problem.but dp? idk man whats the states what is necessary takes time to practice but that time may take 10 years or probably until i die.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't exactly see the distinction between all the algorithms per se. Never did topic-specific practice. Seeing the time-constraints, we get some idea about the expected time complexity. That also gives us a hint about the states/transition at times about a possible DP approach. But yes, when approaching DP (which I think should be done later, in your case) solving a lot of problems is what everyone suggests.

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I see this post by accident after 6 months. I think maybe I'm late :(

I can solve many dp problems myself, but I can't tell you what dp is, because I don't know what dp is too. Dp is such a big system with so many tricks that telling you what dp is is useless, and you can use dp to solve many easy problems even if you don't know what dp is.

Dp is not just guess. When you have solved many problems, you will know some classic ways to solve dp problems. Although they can't solve all dp problems, they can make you a candidate master for sure. The first step is hard, but after it you can improve your skill quickly.

I have been like you before, and I hope you can do it.

(Sorry about my poor English)

→ Reply