Editorial for WC '16 Finals S1 - Cow-Bot Construction
Submitting an official solution before solving the problem yourself is a bannable offence.
For starters, if , 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 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' requirements. As such, let's start by sorting the modules in non-decreasing order of their values, which can be done in time. The modules at the end (with the largest 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 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 be the number of modules installed so far (which we'll iterate upwards from to ), be the first module which hasn't yet been installed (initially module in the sorted list), and let be the total amount of time taken so far (initially ). At each step, if , then the Cow-Bot is currently able to install the -th module, so it should certainly do so – in this case, we'll increment by , and by . 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 by . This simulation process takes time.
Comments