lastdancee's blog

Able to solve hard dp , graph … problems but stuck Div 2 a b c adhoc , constructive , greedy …
By lastdancee, history, 2 hours 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
  • +12
  • Vote: I do not like it

»
63 minutes ago, hide # |
 
Vote: I like it +1 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
  • »
    »
    46 minutes ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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?”...

    → Reply
    • »
      »
      »
      36 minutes ago, hide # ^ |
       
      Vote: I like it +2 Vote: I do not like it

      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

      → Reply