Editorial for Krazy Golf

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Hints

||In what scenarios will position $i$ ~i~ break less gates than position $i-1$ ~i-1~?||
||If position $i$ ~i~ breaks gate $j$ ~j~, what do we know about gate $j$ ~j~ for all further positions?||

Solution

View Solutions

Note that since we'd only get more pills if we started later in the trail, if a gate is broken earlier on, we can consider it "broken" for all future queries - the only scenario where we don't actually break it is there is a stronger gate in front of it. As such, this supports two feasible solutions: 1. Just put all the gates you've seen into a stack, and remove a gate from the stack when we have enough pills to break it. This requires a prefix sum in order to efficiently compute the sum of pills up to a certain pont: @code_include[solutions/main.cpp]{langs: "cpp", rm_config: True} 2. Create a custom monotonic stack, which passes on extra pills when gates are popped off the stack: @code_include[solutions/custom_ms.py]{langs: "py", rm_config: True}

Comments

There are no comments at the moment.