Hello Codeforces!
Today I hardly solved problems, but devoted time to theory. I solved several problems on the topic Binary Search and 2 pointers from other sites, looked for materials on the topic Dp, and today I almost finished the 1st topic from the ITMO Academy course.
It’s strange, because today, without practicing, I wrote a better contest than yesterday.
Plans for tomorrow:
Complete the remaining unsolved problems, end the 1st topic of the course, and write a contest from the coach.
If your goal is pupil, learning DP is complete overkill.
Last time I see than almost every B from lasts Div.2 had "Dp" tag
People like to slap dp tag on pretty much any problem, even if it's not related to dp. If you check out the editorial you will see that it's not DP at all.
agreed
A wise man once said "Every problem can be solved with dp, but should you solve it with dp?"
Sure, but "dp mindset" is probably single most important part to all of cp, even when not applying dp.
True, but it's not really applicable to div2B. I also see many newbies, especially those who have prior experience in Leetcode, try to "force" DP on problems that aren't DP.
Bad solution with inappropriate dp is better than not solve at all. Everyone should start with what they can do, rather than waiting until they can find perfect solutions without anything unnecessary.
Yes, but when looking at div2b there is no solution with dp, bad or good, appropriate or inappropriate.
Counterexample: https://mirror.codeforces.com/contest/1934/problem/B
It doesn't matter at this level (and at my level too, btw). Just practice anything new to get experience how to approach problems and what ideas can work under which conditions.
ok, fair enough. I still think that practicing fundamentals is more useful than practicing DP, simply because most div2A/B are more observation-based than algorithms.
What are fundamentals? Basically restating, but a majority of problems rely on idea of "how can i reuse information processing in right order instead of bruteforcing all possibilities" in some form, even div2A/B. This is what I mean by "dp mindset", as even now I basically think about all these problems same way whether I end up applying dp or not.
I think it's almost impossible to avoid somewhat "forcing" the limitted ideas you've seen onto problems in early stages, as there is only so much you know to think about at first. It is just good to tell people to consciously avoid this and look for small things you know for sure instead of solving entire problem at once then build from that, then as they learn and do more they will get out of the "forcing topics" stage.
This problem doesn't need DP at all.
You should note stuff like:
And then just brute it, filling the rest with 30's.
i think what vstiff means is that it CAN be solved with dp, not that it is the best way
Not exactly. Norp declared his intention to reach pupil. This task is $$$\approx$$$ "solve AB in Div 2 round". And if you studied DP, knapsack is one of the most dp-est thing, you'd definitely know how to approach that problem and with good chance already reached the goal in that round. And with same good chance lost it in the next one with totally-non-DP B.
I never said it's most efficient way. I just say that if learning DP is fun for you then surely go ahead and practice it and won't harm reaching pupil in any way.
My main point is that comments just criticising someone's decisions without advice how to improve it are not very helpful. Norp did his best to solve the task reaching pupil and you see a flaw in his solution. Instead of just saying the his solution is suboptimal propose a better way with more efficient learning resources, because what's obvious for you (need of studying fundamentals) may not be the case for someone else.
here is a solution in O(1) of the problem that you mentioned as a counterexample : https://mirror.codeforces.com/contest/1934/submission/249139150
I 100% agree with this
For specialist is Dp needed ?
Could you share your resources relating to binary search on other sites? Thanks!
try cses problem sheet
别在意那些点负的人，继续努力