← All solutions

Shortest judge solution: 561 bytes. Shortest team solution (during contest): 660 bytes.

This is a simple, but deceivingly tricky problem that most teams managed to solve, but most of them needed more than one attempt to get it right. Most teams correctly guessed a greedy approach will be required, but figuring out the right greedy approach at the first attempt turned out far from obvious.

First, notice that obviously we should reformat the drives for which we gain space due to reformatting prior to any drives for which we lose space due to reformatting. A standard exchange argument if we have two such drives adjacent proves that (if we swap them, we have more free space available both when looking at the first drive formatting, and when looking at the second one).

Now, we need to order the drives for which we gain space, and the drives for which we lose space. For a drive for which we gain space, its best to start with the drives that are the smallest before reformatting (since they require the least space to start — again, an exchange argument proves this). For drives for which we lose space, you can notice that the problem is symmetrical — if you wanted to reformat the drives back to the old filesystem, you could reverse the order of reformattings and do it in the same space. So, the drives for which we lose space should be ordered by space after reformatting, in decreasing order. Again, an exchange argument shows this to be correct.

Once we know the correct ordering, we can just simulate, adding the extra space as needed, and the total amount of extra space added will be the final answer. Some teams instead performed a binary search on the answer, which is also fine, although unnecessary.