Editorial for COCI '06 Regional #3 Firefly
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
If the firefly destroys a stalagmite (stalactite) of size , then it will also destroy all stalagmites (stalactites) of size greater than or equal to
, so the relative ordering of stalagmites (stalactites) is irrelevant. We can therefore separately sort stalactites and stalagmites and use binary search to determine the number of obstacles destroyed on any given level. Iterating on all possible levels gives us the solution.
It is also possible to solve the problem faster, by preprocessing the number of stalagmites (stalactites) of size less than , for each number
.
Comments