← All solutions

Solved by 128 teams.

First solved after 21 minutes.

Shortest team solution: 1458 bytes.

Shortest judge solution: 1783 bytes.

This was one of the easiest problems, having a pretty natural greedy solution, but it still required a bit of datastructure work.

Suppose that there are a front-row tiles tied for cheapest, and b in the back row, and assume without loss of generality that a ≤ b. We need to decide which a of these b back-row tiles should be matched with the front row. We can do this greedily, always taking the shortest possible back-row tile for each front-row tile, which ensures that the left-overs are as tall as possible. Having done this, we can now ignore the left-most a positions and their tiles, and solve the problem again with the remaining tiles.

Finding the shortest available tile for each spot requires some form of query structure such as a balanced binary tree, which results in an O(n log n) running time. C++, Java and Kotlin all provide built-in classes for this, but solving this problem in Python requires a bit more manual labor.