srsly,whats up with orz blogs.if u want downvotes then just make blog and rant about why dp bad af and conterintuitive.

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | tourist | 176 |

7 | sus | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | SecondThread | 169 |

most of the time whenever i do dp problems.the editorial just say what to memoize.im kinda confused.why string dp requires the prefix of the previous and why in a grid we require the previous step?

can somebody kindly explain? this is the hardest thing about dp for me

dunno whats wrong

int n;

cin >> n;

int a[100][100];

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++) { cin >> a[i][j]; }

}

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++) { cout << a[i][j]; } cout << endl;

}

the previous blog got downvoted,so ima just make a copy

I've practiced for dp and i have found my weakness.its the dp state.somehow i never guessed it correctly.the states that i made was never relevant to the actual answer.its totally wrong.i have no clue whenever i try to make some dp states and just see if somethings correct.idk how poeple just solve dp like its 1+1.i do not know what do memoize.can someone help me?

https://atcoder.jp/contests/abc220/editorial/2703

on the recent atcoder round,i find problem D not very intuitive.can someone explain the editorial even more?

most people will ask how to do dp.now im asking,what to dp?

ive seen so many dp tutorials.most of them are really good.i understand dp because of them.but there is still 1 more flaw.what to dp?.i usually ask this question to myself when im practicing for dp and stuck for 30 mins because idk where to start.i dont see anything dp-able from a dp problem but i know its a dp problem.some dp problems are obvious like knapsack but others like in contest r not rlly straightforward.i will end up seeing the editorial without even trying not because i dont want to try,but because im unable to.i really want to improve.ive put the effort to try but cant.maybe u guys can help.

https://codeforces.com/contest/201/problem/A

the editorial is too long and i dont understand.also its a dp problem.can somebody help? thanks!

most of the time,when im learning new algo,i always struggle to implement them in problems.i remember studying binary search.it took me 20 mins to understand the concept and 7 months to actually able to solve 1 problem using it.and now im learning bfs and dfs and other graph theory.i understand bfs concepts but when applied to real problems,i cant.i ended up copying others because in the problem i encounter,the nodes are coordinates,instead of numbers like node 1,2 etc.took me 3 days to try to solve before giving up.

does anyone know how to overcome this?

i think its best to share practice results daily so that people will know cp makes me want to kill myself and reaching pupil is so hard.

practice=bfs and dfs and basic graphs verdict=fail

i understood the point of bfs and dfs.but when it is applied to real problems,it will drive me nuts.from lunch to dinner i still unable to solve basic graoh taht only requires bfs with modification.so cringe ngl.

imagine ur trying to solve problem C.the first time u see the problem statement ur like damn this is interesting.and 30 mins later u ahve no clue how to solve even though u have thought hardly about the problem as if youre solving world hunger and peace. then u see the editorial and it says.

just split it into 2 numbers and ur basically done.

happens to noone except me i guess

finally! poggers

i have found my real problem in cp.not dp not implementation but more like psychological effect.i dont really know if a blog similar to this exist but im just going to make one anyway.

it all started on my first ccontest on other judge.where i felt confident enough to solve 3 problems.without any knowledge on any algorithm.at this time i just learnt how to take sum of multiple numbers.

long story short,the contest started.i immediately do problem A.it was pretty easy.now i come to problem b.it looks pretty easy so i immediately tried.at first i cant implement it.so i did a quick google search.i found one solution but it didnt fit time limit.it was linear search.after long time,i decided to give up and see the editorial.i found out that it needed n log n binary search or two pointers.i felt really sad.failed to solve 3 problems like what i expected.

then i joined codeforces.after reading some binary search and done a few problems i joined another contest.i thought the previous one was just a bad day for me.but turns out i was still unable to do problem c.it was really hard like it looks easy if u do it on paper but for coding part,rlly hard ngl.

this cycle continues until now and idk what to do.even on practice i feel scared of trying 1300+ like i know that my solution will fail and eventually waste my time.while in contrary if u dont try u wont be able to do it.

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

https://codeforces.com/contest/1459/problem/B

i just started learning dp a year ago and i could not find the solution for this problem.i dont know the states because i dont know what thing matters to get to a certain point and also the dimension of the dp.can anyone help me>

i practiced for 5 hours straight and cant even do a single problem.

after i play apex legends for 1 hour i have 3 problems ac streak

conclusion=play apex legends and stop studying

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2021 10:51:36 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|