piggydan's blog

By piggydan, history, 4 weeks ago, In English,

Many of the simpler but non-conventional greedy problems involve sorting the input (against a custom comparator) into an optimal selection ordering. I find the most challenging part for me to be deriving this comparator. I have came across this problem several times already, such as in 1203F1 - Complete the Projects (easy version) and LuoguOJ 1080.

Most often, the comparator is derived by assuming a property of the ordering (i.e. "A comes before B in the ordering") and then bashing out its implications through casework. However, this is cumbersome and often leads to mistakes.

Does anyone have tips on how they solve these kinds of greedy problems?

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

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

You can refer to Errichto's lecture series on Exchange arguments on youtube.