Editorial for CTU Open Contest 2017 - Pond Cascade


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.
  • One way of solving the problem is simply to simulate it
  • Another way is to binary search over time

Simulation:

  • Use priority queue to track order of events when some pond fills up to the top
  • We will keep an array which will contain, for each pond, subsequent pond where the water will overflow
  • While processing an event, set remaining volume of current pond to zero and decrease remaining empty volume of subsequent pond and create an event based on new flow to the subsequent pond
  • All that is left is to memorize the time for the last and for all ponds
  • Total running time: \mathcal O(N \log N)

Binary search:

  • Use binary search to guess time when the last and all of the ponds fill up separately
  • Based on the guessed time, we can loop through the ponds and find out how many litres will be poured in and consequently how much liquid is poured to the subsequent in order
  • Based on the result of binary search (either we got too much liquid in pond or not enough to fill up), we adjust our guess
  • It can be easily proven that our guess has to be between 1 and 10^9 seconds
  • Then we can simply iterate and keep trying till we get our desired precision or for fixed number of iterations (50 is more than sufficient)

Comments

There are no comments at the moment.