Solution

Consider the lattice points \((x,y,z)\) in 3D space where we can form \(x\), \(y\), \(z\) sets of Div.1, Div.2, Div.3 respectively, and let \(S\) be the set of such points.

In conclusion, \(S\) is the set of all lattice points \((x,y,z)\) that satisfy all of the following inequalities for some integers \(R_x,R_y,R_z,R_{xy},R_{xz},R_{yz},R_{xyz}\): (This is a natural idea when considering that the continuous relaxation problem is a Minkowski sum of convex polyhedra.)

• \(0 \le x \le R_x\)
• \(0 \le y \le R_y\)
• \(0 \le z \le R_z\)
• \(x+y \le R_{xy}\)
• \(x+z \le R_{xz}\)
• \(y+z \le R_{yz}\)
• \(x+y+z \le R_{xyz}\)

In other words, by maintaining \(R_x \dots R_{xyz}\), we can compute the number of times C3C can be held as \(min(R_x,R_y,R_z,\frac{R_{xy}}{2},\frac{R_{xz}}{2},\frac{R_{yz}}{2},\frac{R_{xyz}}{3})\).

When adding a writer, we can update \(R_x \dots R_{xyz}\) independently. Examples of update formulas are as follows:

• \(R_x = R_x+min(A_i,B_i,C_i)\)
• \(R_{xy} = R_{xy}+min(A_i+D_i,B_i,C_i)\)
• \(R_{xz} = R_{xz}+min(min(A_i,B_i)+min(D_i,E_i),C_i)\)
• \(R_{xyz} = R_{xyz}+min(A_i+D_i,B_i+E_i,B_i+D_i,C_i)\)

The time complexity is \(O(N)\). (Code)

Proof

It is clear that the value obtained by the above solution is an upper bound, so we show that it is also a lower bound.

When \((x,y,z)\) is contained in \(S\), \((x-1,y,z), (x,y-1,z), (x,y,z-1)\) are also contained in \(S\) (as long as the coordinates do not become negative).

Consider the maximal point set \(T\), which consists of all points in \(S\) such that none of \((x+1,y,z), (x,y+1,z), (x,y,z+1)\) is contained in \(S\).

The point \(P=(x_P,y_P,z_P)\) in \(T\) with the maximum \(y\) is uniquely determined. This is because when Div.2 is formed to the maximum extent, each writer’s problem proposals will have 0 proposals of either Hard, Medium, or Easy, so only either Div.1 or Div.3 can be formed, and the maximum values of \(x,z\) are independently and uniquely determined.

Starting from \(P\) and decreasing \(y\) by \(1\) each time, initially we can increase both \(x,z\) by \(1\) each (let the upper limit of this count be \(C_{xz}\)), and at some point we can only increase one of \(x,z\) by 1. There are upper limits to the number of times we can increase \(x,z\) by \(1\) respectively (let them be \(C_x,C_z\)), and there is also an upper limit to their sum (let it be \(C_{sum}\)). \(C_{xz},C_x,C_z,C_{sum}\) can each be computed greedily as in this code.

The figure below illustrates an example of \(S,T,P,C_{xz},C_x,C_z,C_{sum}\).

Such \(S\) with \(T\) becomes a point set that can be represented by \(R_x,R_y,R_z,R_{xy},R_{xz},R_{yz},R_{xyz}\) as in the above solution. It is constructively shown that all points in \(S\) are realizable, proving that it is a lower bound.