lastdancee's blog

Able to solve hard dp , graph … problems but stuck Div 2 a b c adhoc , constructive , greedy …
By lastdancee, history, 89 minutes ago, In English

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 ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 minutes ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • For "construct an optimal configuration" you can probably prove some kind of upper bound and then find a construction that always achieves it (remember that the problem writers are not LGMs and had to figure out how prove this too)
  • don't remember any other ones off the top of my head lol
→ Reply