Editorial for WC '16 Finals S1 - Cow-Bot Construction


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.

For starters, if E \le B, then the engineers are at least as fast as the Cow-Bot at installing modules, so they might as well just install all of them themselves. This will take them N \times E minutes.

Otherwise, the Cow-Bot is faster, so our goal is to have it install as many modules as possible, with the only limitation being the modules' M requirements. As such, let's start by sorting the modules in non-decreasing order of their M values, which can be done in \mathcal O(N \log N) time. The modules at the end (with the largest M values) are the least likely to be able to be installed by the Cow-Bot before it's too late, so the engineers should prioritize installing those. On the other hand, the modules at the start (with the smallest M values) will be the ones which the Cow-Bot should go ahead and install whenever it can.

These ideas suggest the following greedy solution, in which we'll simulate the modules' installation. Let m be the number of modules installed so far (which we'll iterate upwards from 0 to N-1), i be the first module which hasn't yet been installed (initially module 1 in the sorted list), and let t be the total amount of time taken so far (initially 0). At each step, if m \ge M_i, then the Cow-Bot is currently able to install the i-th module, so it should certainly do so – in this case, we'll increment i by 1, and t by B. Otherwise, there's no module currently available for the Cow-Bot to install, so the engineers must go ahead and install one from the end – in this case, we'll just increment t by E. This simulation process takes \mathcal O(N) time.


Comments

There are no comments at the moment.