Editorial for WC '17 Contest 2 J3 - Escaping the Mines

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.

Let's start by looping over the values $J_{1 \dots N}$ ~J_{1 \dots N}~ and determining which members of the Fellowship are able to clear the chasm by themselves (all members $i$ ~i~ such that $J_i \ge M$ ~J_i \ge M~). Let $Y$ ~Y~ be the number of members who can do so, and let $X$ ~X~ be the number of members who cannot. Each member of the former group can help out at most one member of the latter group, meaning that $\min(X, Y)$ ~\min(X, Y)~ extra members can get carried across in addition to the $Y$ ~Y~ members who can jump across regardless. This gives us an answer of $Y+\min(X, Y)$ ~Y+\min(X, Y)~.

Comments

There are no comments at the moment.