I can solve some pretty tough problems involving DP, graphs, and data structures. Sometimes I can handle problems that feel much more “advanced” technically.
But strangely, when I face some Div.2 A/B/C problems, especially greedy, constructive, or adhoc, I often get completely stuck . This kind of observation feels very different from DP or graph problems. In DP, I usually ask: What is the state? What is the transition? How do I optimize it?
But in these small constructive/greedy problems, I dont know what to do or coul not think of any solutions that i have approached before . How can i fix this bugs ?
I think the first thing to remember is that the fact that there are people who are good at them means that it's possible to get good at them. I find remembering that gives me a lot more confidence that I can improve if that makes sense.
Then I think there are some general strategies that you will get better at using over time. Just like how with DP you can ask what the states and transitions are.
Such as
Thanks, that makes a lot of sense.
I think I’m too used to asking “what algorithm or data structure should I use?”, while for constructive/greedy problems I should probably ask things like “what is the trick?”, “what is the bound?”, and “is my condition sufficient?”...
Yeah that could be good. In general I think it's easier to think of a strategy and then use data structures and algorithms to make your strategy work than it is to start with data structures and algorithms and think of your strategy second.
Exception: tree DP, just write a state and it probably works lol
For most Div. 2 A/B questions, I don't think any algorithm or data structure is needed. Most A/B questions are observation, implementation, or math-based. For that, you can solve questions from a few recent Div. 2 contests. By the way currently i am struggling to learn dp. Would appreciate your advice how to learn and where to learn dp
I think this website is really helpful if you want to learn algorithms, especially DP: https://youkn0wwho.academy/topic-list It covers many DP topics, such as knapsack, optimized knapsack, tree DP, DAG DP, divide and conquer DP, bitmask DP, SOS DP, etc. Personally, I learned DP from many different sources and used this website, along with others, for practice. I think the key is to solve as many DP problems as possible, but at the same time, you should try to deeply understand the idea behind each DP technique instead of just memorizing patterns, learn different types of DP and practice a lot of problems for each type. Over time, you will naturally get better at it.
thanks a lot.
for me, it is common that I make small mistakes and sit 2 hours straight trying to figure it out and fix.
Clearly based on rating you are better than me however I feel that I have a converse issue where I cannot do ‘traditional problems’ and can’t really do data structures well (yet) but I’m better at ad hoc and greedy relative to my intuition ability. I think that you probably have a really strong intuition for problems you have seen but perhaps haven’t quite developed your reasoning. I think some igm (pretty sure colingalen) said something like thinking longer when practicing helps develop ability to solve new problems and spending less on each problem but seeing more ideas helps intuition (which you seem to have).
That’s true. I think one of my weaknesses is that whenever I face a new type of problem that requires deep reasoning, I often get stuck. The reason I can solve many traditional problems is probably because I have practiced those types a lot, so I’m more familiar with their patterns. So I think the best way for us is to keep practicing consistently, but also make sure to spend more time thinking deeply about each problem instead of moving on too quickly.