← All solutions

Problem authors:
Derek Kisman and Walter Guttmann
Solved by 24 teams.
First solved after 76 minutes.
Shortest team solution: 1545 bytes.
Shortest judge solution: 871 bytes.

Consider a face of die D₃, with value v. Let S_i(v), for i ∈ {1, 2}, be the expected value of points die D_i gets if D₃ lands on this face. The expected value die D₁ gets overall is the average of S₁(v) over all faces of D₃.

S₁(v) is simply the number of faces of D₁ larger than v, plus half the number of faces equal to v. The same goes for S₂(v). This means that there are O(n) possible values for the pair (S₁(v), S₂(v)), and we can easily calculate all of them in O(n log n). We are now looking to assign weights to those points so that the weighted average of S₁(v) is ≤ 0.5, and the weighted average of S₂(v) is as high as possible (and vice versa).

This is a geometry problem. Note that all the points we can obtain by weighted averages of a set of points is exactly their convex hull; so we’re looking for the highest y-variable value in the convex hull intersected with x ≤ 0.5, which can be determined in O(n) in a number of ways.