A - Make 10 Editorial by evima
◆ Exploiting parity
When making a stick of length \(10\), we will always use an even number of sticks of length \(3\). Thus, instead of having \(N_3\) sticks of length \(3\), let us assume that we have \(\lfloor\frac{N_3}{2}\rfloor\) sticks of length \(6\) from the beginning. Thus, we can reduce the problem to making sticks of length \(10\) from sticks of lengths \(2\), \(4\), and \(6\). Furthermore, by dividing the length of every stick by \(2\), we end up with the following problem.
- We have \(N_1\) sticks of length \(1\), \(N_2\) sticks of length \(2\), and \(N_3\) sticks of length \(3\). Find the maximum number of sticks of length \(5\) that can be made.
Below, we deal with this problem instead of the original.
We will call a way to make the maximum possible number of sticks of length \(5\) an optimal solution.
◆ The structure of an optimal solution (1)
Intuitively, having two sticks of length \(1\), for example, is better than having one stick of length \(2\) because they are more versatile. Based on these observations, let us analyze the structure that we can assume an optimal solution has.
We can prove the following:
when we have at least one stick of length \(2\) and at least one stick of length \(3\), there is an optimal solution that bonds those sticks to form a stick of length \(5\).
Let us prove this. We will assume that no optimal solution bonds a stick of length \(2\) and a stick of length \(3\) and derive a contradiction. Let us take an optimal solution and name it \(X\). Also, let us take a stick of length \(2\) and another of length \(3\) and name them \(A\) and \(B\), respectively.
- If \(X\) uses neither \(A\) nor \(B\): we can bond \(A\) and \(B\) to form a new stick of length \(5\), which contradicts the optimality of \(X\).
- If \(X\) uses \(A\) but not \(B\): we can break the stick of length \(5\) containing \(A\) and then bond \(A\) to \(B\) to obtain an optimal solution that bonds a stick of length \(2\) and a stick of length \(3\), which is a contradiction.
- If \(X\) uses \(B\) but not \(A\): contradictory, similarly to the case above.
- If \(X\) uses both \(A\) and \(B\): we can break the stick of length \(5\) containing \(A\) and the stick of length \(5\) containing \(B\), and then bond \(A\) to \(B\) and bond together the remaining sticks, to obtain an optimal solution that bonds sticks of length \(2\) and \(3\), which is a contradiction.
This completes the proof.
◆ The structure of an optimal solution (2)
With the fact shown above, we have found what to bond when we have both sticks of length \(2\) and sticks of length \(3\). What remains is the case we have no sticks of length \(2\) or no sticks of length \(3\).
Similarly to the proof above, we can prove the following. We will omit the proofs.
If we have no sticks of length \(2\), at least one stick of length \(3\), and at least two sticks of length \(1\), there is an optimal solution that bonds those sticks of length \(3, 1, 1\) to form a stick of length \(5\).
If we have no sticks of length \(3\), at least two sticks of length \(2\), and at least one stick of length \(1\), there is an optimal solution that bonds those sticks of length \(2, 2, 1\) to form a stick of length \(5\).
If we have no sticks of length \(3\), just one stick of length \(2\), and at least three sticks of length \(1\), there is an optimal solution that bonds those sticks of length \(2, 1, 1, 1\) to form a stick of length \(5\).
◆ Greedy algorithm
Eventually, we can see that the following greedy algorithm finds an optimal solution.
(Step 1) If we have at least one stick of length \(2\) and at least one stick of length \(3\), bond those sticks to form a stick of length \(5\). Repeat as many times as possible.
(Step 2) If we have at least one stick of length \(3\) and at least two sticks of length \(1\), bond those sticks to form a stick of length \(5\). Repeat as many times as possible.
(Step 3) If we have at least two sticks of length \(2\) and at least one stick of length \(1\), bond those sticks to form a stick of length \(5\). Repeat as many times as possible.
(Step 4) If we have at least one stick of length \(2\) and at least three sticks of length \(1\), bond those sticks to form a stick of length \(5\). Repeat as many times as possible.
(Step 5) If we have at least five sticks of length \(1\), bond those sticks to form a stick of length \(5\). Repeat as many times as possible.
◆ Sample Implementation
posted:
last update: