Editorial for Krazy Golf

Use this editorial only when stuck, and do not 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$ break less gates than position $i-1$ ?
If position $i$ breaks gate $j$ , what do we know about gate $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:

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}

Create a custom monotonic stack, which passes on extra pills when gates are popped off the stack:

Editorial for Krazy Golf

Hints

Solution

Comments0

New comment