Teamwork
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2800
Tags: constructive algorithms, greedy, math

As soon as SWERC starts, your experienced $$$3$$$-person team immediately realizes that the contest features $$$a$$$ easy problems, $$$b$$$ medium problems, and $$$c$$$ hard problems. Solving a problem will take any of you $$$2$$$, $$$3$$$, or $$$4$$$ time units, depending on whether the problem is easy, medium, or hard. Regardless of the difficulty of the problem, the last time unit spent to solve it has to be spent using your shared computer.

You organize your efforts so that each of you starts (and ends) solving problems at integer time units. Any given problem can be solved by only one contestant; it requires a contiguous amount of time (which depends on the difficulty of the problem). None of the $$$3$$$ of you can solve more than one problem at a time, but you can start solving a new problem immediately after finishing one. Similarly, the shared computer cannot be used by more than one of you at a time, but any of you can start using the computer (to complete the problem currently being solved) immediately after someone else stops using it.

Given that the contest lasts $$$l$$$ time units, find the maximum number of problems that your team can solve. Additionally, find one way to solve the maximum number of problems.

Input format:
The input has a single line. It contains four integers $$$a$$$, $$$b$$$, $$$c$$$, $$$l$$$ ($$$0 \leq a, b, c, \leq 10^4$$$, $$$0 \le l \le 10^5$$$) — the number of easy, medium, and hard problems, and the duration of the contest.

Output format:
On the first line, print a single integer $$$n$$$ — the maximum number of problems that your team can solve.

Then, on the $$$j$$$-th of the following $$$n$$$ lines, print three integers $$$x_j$$$, $$$p_j$$$, $$$q_j$$$ ($$$1 \leq x \leq 3$$$, $$$0 \leq p_j < q_j \leq l$$$) — the contestant that solves the $$$j$$$-th problem, and the start and end time for solving the $$$j$$$-th problem (measured as time units elapsed from the beginning of the contest). The difference $$$q_j - p_j$$$ is $$$2$$$, $$$3$$$, or $$$4$$$, depending on the difficulty of the problem.

The last $$$n$$$ lines are to be provided in increasing order of end time: $$$q_1 < q_2 < \cdots < q_n$$$. If there are multiple ways to solve $$$n$$$ problems, output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the first contestant solves an easy problem between time $$$0$$$ and time $$$2$$$ while the second contestant solves a medium problem between time $$$0$$$ and time $$$3$$$.

In the second sample, the first contestant solves an easy problem between time $$$0$$$ and time $$$2$$$, and then also solves a medium problem between time $$$2$$$ and time $$$5$$$. In the meantime, the second contestant solves another medium problem between time $$$0$$$ and time $$$3$$$, while the third contestant solves a hard problem between time $$$0$$$ and time $$$4$$$.

In the third sample, the contest only has medium and hard problems, and there is not enough time to solve any of them.

Example input:
2 1 1 3

Example output:
2
1 0 2
2 0 3

Example input:
1 2 3 5

Example output:
4
1 0 2
2 0 3
3 0 4
1 2 5

Editorial:
To start, we determine whether it is possible to solve $$$a$$$ easy problems, $$$b$$$ medium problems, and $$$c$$$ hard problems in a contest that lasts $$$l$$$ time units. Once we are able to do this, it is easy to find the optimal number of problems that can be solved; we will do it in the "Full solution" section below.
We are going to prove that it is possible to solve $$$a$$$ easy problems, $$$b$$$ medium problems, and $$$c$$$ hard problems if and only if the following two constraints are satisfied: $$$$$$  (1) \qquad l \geq a + b + c +  \begin{cases}   0 & \text{if $a=b=c=0$} \\   1 & \text{if $a\geq 1$} \\   2 & \text{if $a=0$ and at least one of $b$ and $c$ is $\geq 1$} \\  \end{cases} $$$$$$
$$$$$$ (2) \qquad 3l \geq 2a + 3b + 4c +  \begin{cases}   0 & \text{if $a=b=c=0$} \\   3 & \text{if $a,b,c\geq 1$} \\   4 & \text{   if at least one of $a,b,c$ is $0$ but at least one of $a,b$ is $\geq 1$} \\   6 & \text{if $a=b=0$ and $c\geq 1$} \\  \end{cases} $$$$$$
These two constraints might seem complicated at first glance, but for the most part, they are quite easy to come up with. They have a very natural interpretation in terms of available computer time and contestant time.
Proof that the constraints are necessary
In this section, we show that constraints (1) and (2) above need to be satisfied for it to be possible to solve the given problems in $$$l$$$ time units.
Any problem takes $$$1$$$ time unit of computer time and there are $$$l$$$ time units in total, so $$$l \geq a+b+c$$$. We only need to strengthen this inequality a little bit in order to obtain constraint (1). Notice that the computer is necessarily idle during the first time unit of the contest, because any problem's solution starts with at least $$$1$$$ time unit of non-computer time. Therefore, if at least one of $$$a,b,c$$$ is $$$\geq 1$$$, we must have $$$l \geq a+b+c+1$$$. Similarly, if $$$a=0$$$ and at least one of $$$b$$$ and $$$c$$$ is $$$\geq 1$$$, then any problem's solution starts with at least $$$2$$$ time units of non-computer time; thus the computer is idle during the first $$$2$$$ time units and we must have $$$l \geq a+b+c+2$$$. This proves constraint (1). Note that we could further strengthen the constraint to $$$l \geq a+b+c+3$$$ if $$$a=b=0$$$ and $$$c \geq 1$$$, but such improvement is not needed (constraint (2) is stronger than (1) in this case).
Apart from computer time, our other limited resource is contestant time, of which there is a total of $$$3l$$$ time units ($$$l$$$ time units for each of the $$$3$$$ contestant). Each easy problem requires $$$2$$$ units of contestant time, each medium problem requires $$$3$$$ units, and each hard problem requires $$$4$$$ units. Therefore, we must have $$$3l \geq 2a + 3b + 4c$$$. We are going to strengthen this inequality to obtain constraint (2).
If $$$a=b=c=0$$$ there is nothing more to do, so suppose from now on that at least one of $$$a,b,c$$$ is $$$\geq 1$$$. Then the contest must last at least $$$2$$$ time units for it to be possible to solve all problems. The last time unit of the contest can be used by at most $$$1$$$ contestant, who is completing a problem's solution using the shared computer. Similarly, the last $$$2$$$ time units can be used by at most $$$2$$$ contestants: one contestant can complete a problem's solution at time $$$l$$$ (using the computer in the last time unit of the contest) and one can complete a problem's solution at time $$$l-1$$$ (using the computer in the second to last time unit). In total, there are at least $$$3$$$ units of contestant time that are necessarily wasted. Therefore, we must have $$$3l \geq 2a+3b+4c+3$$$.
The contest can last $$$2$$$ time units only if $$$a=1$$$ and $$$b=c=0$$$, and in this case we have $$$3l = 2a+3b+4c+4$$$ (so constraint (2) holds). Assume from now on that the contest lasts at least $$$3$$$ time units. If at least one of $$$a,b,c$$$ is $$$0$$$, then it is not possible for all $$$3$$$ contestants to start solving a problem at time $$$0$$$, because at least two contestants would finish solving a problem at the same time; therefore, at least one additional unit of contestant time is wasted, so $$$3l \geq 2a+3b+4c +4$$$. This improvement is useful for instance in the case $$$a=1$$$, $$$b=0$$$, $$$c=1$$$, where we get $$$3l \geq 10$$$ and so $$$l \geq 4$$$ (in this case, constraint (1) only yields $$$l\geq 3$$$).
Finally, we need to strengthen the inequality once more when $$$a=b=0$$$ and $$$c\geq 1$$$. In this case, the contest necessarily lasts at least $$$4$$$ time units. At most one contestant can start solving a problem at time $$$0$$$, and at most one other contestant can start solving a problem at time $$$1$$$. This means that at least $$$2$$$ units of contestant time are wasted between time $$$0$$$ and time $$$1$$$, and at least $$$1$$$ additional unit is wasted between time $$$1$$$ and time $$$2$$$. If we add the $$$3$$$ units of contestant time that are wasted at the end of the contest, we obtain that $$$3l \geq 2a+3b+4c+6$$$.
Proof that the constraints are sufficient & construction of a strategy
In this section, we inductively show that constraints (1) and (2) are sufficient for it to be possible to solve all problems. We do so by describing an explicit greedy strategy built by induction on $$$a+b+c$$$.
We first observe that constraint (1) implies constraint (2) whenever $$$a \geq c+1$$$. Indeed, in this case we have $$$a+b+c+1 \geq \frac13(2a + 3b + 4c + 4)$$$.
Suppose that $$$b \geq 2$$$, or $$$b=1$$$ and $$$a \geq c+1$$$. Note that constraint (1) implies $$$l\geq 3$$$. By induction, it is possible to solve $$$a$$$ easy problems, $$$b-1$$$ medium problems, and $$$c$$$ hard problems in $$$l-1$$$ time units, because both constraints remain satisfied (if $$$b=1$$$ and $$$a \geq c+1$$$, constraint (2) is implied by constraint (1) which remains satisfied). Given any strategy to do so, at least one contestant is idle between time $$$l-3$$$ and time $$$l-1$$$, because otherwise, the computer would need to be used by all $$$3$$$ contestants within these $$$2$$$ time units. Any such idle contestant can then solve the remaining medium problem between time $$$l-3$$$ and time $$$l$$$; this gives us a strategy to solve all problems in $$$l$$$ time units.
Suppose now that $$$a \geq 2$$$ and $$$c \geq 1$$$. Note that constraint (1) implies $$$l \geq 4$$$. By induction, it is possible to solve $$$a-1$$$ easy problems, $$$b$$$ medium problems, and $$$c-1$$$ hard problems in $$$l-2$$$ time units, because both constraints remain satisfied (if $$$c=1$$$, constraint (2) is implied by constraint (1) which remains satisfied). Given any strategy to do so, at least one contestant (say, $$$x$$$) is idle between time $$$l-4$$$ and time $$$l-2$$$, and at least one other contestant (say, $$$y$$$) is idle between time $$$l-3$$$ and time $$$l-2$$$. Contestant $$$x$$$ can then solve a hard problem between time $$$l-4$$$ and time $$$l$$$, and contestant $$$y$$$ can solve an easy problem between time $$$l-3$$$ and time $$$l-1$$$.
We are left with the following four small cases (leaving out $$$a=b=c=0$$$ where there is nothing to solve).
• $$$b=c=0$$$. By constraint (1), we have $$$l \geq a+1$$$.  A strategy is to have the $$$i$$$-th easy problem solved between time $$$i-1$$$ and time $$$i+1$$$, by the first contestant if $$$i$$$ is odd and by the second contestant if $$$i$$$ is even.  The third contestant gets bored and leaves the contest hall to get some pizza.
• $$$a\leq 1$$$, $$$b=0$$$. By constraint (2), we have $$$3l \geq 4c + 6$$$ (regardless of whether $$$a=0$$$ or $$$a=1$$$), so $$$l \geq \lceil \frac43 c + 2 \rceil$$$.  If $$$a=1$$$, the easy problem can be solved by the first contestant between time $$$0$$$ and time $$$2$$$.  Then, the $$$i$$$-th hard problem can be solved by contestant $$$(i \!\!\mod 3) + 1$$$ between time $$$\lceil \frac43 i - 2 \rceil$$$ and time $$$\lceil \frac43 i + 2 \rceil$$$.
• $$$a=0$$$ and $$$b=1$$$. By constraint (2), we have $$$3l \geq 4c+7$$$, so $$$l \geq \lceil \frac43 c + \frac73 \rceil$$$.  We can have the first contestant solve the only medium problem between time $$$0$$$ and time $$$3$$$.  Then, the $$$i$$$-th hard problem can be solved by contestant $$$(i \!\!\mod 3) + 1$$$ between time $$$\lceil \frac43 i - \frac53 \rceil$$$ and time $$$\lceil \frac43 i + \frac73 \rceil$$$.
• $$$a=b=1$$$, $$$c \geq 1$$$. By constraint (2), we have $$$3l \geq 4c+8$$$, so $$$l \geq \lceil \frac43 c + \frac83 \rceil$$$.  We can have the first contestant solve the only small problem between time $$$0$$$ and time $$$2$$$. and the second contestant solve the only medium problem between time $$$0$$$ and time $$$3$$$.  Then, the $$$i$$$-th hard problem can be solved by contestant $$$(i+1 \!\!\mod 3) + 1$$$ between time $$$\lceil \frac43 i - \frac43 \rceil$$$ and time $$$\lceil \frac43 i + \frac83 \rceil$$$.
Alternative construction of a strategy
The following is a simpler greedy strategy to solve $$$a$$$ easy problems, $$$b$$$ medium problems, and $$$c$$$ hard problems in the minimum amount of time.
Consider the time units one by one, from the beginning of the contest. At the $$$i$$$-th time unit (for $$$i=1, 2,\dots$$$), do at most one of the following:
• if at least one hard problem remains, $$$i \geq 4$$$, and at least one contestant has been idle between time $$$i-4$$$ and time $$$i$$$, then let one such contestant solve a hard problem between time $$$i-4$$$ and time $$$i$$$;
• if at least one medium problem remains, $$$i \geq 3$$$, and at least one contestant has been idle between time $$$i-3$$$ and time $$$i$$$, then let one such contestant solve a medium problem between time $$$i-3$$$ and time $$$i$$$;
• if at least one easy problem remains, $$$i \geq 2$$$, and at least one contestant has been idle between time $$$i-2$$$ and time $$$i$$$, then let one such contestant solve an easy problem between time $$$i-2$$$ and time $$$i$$$.
For simplicity, we only prove that the constructed strategy is optimal for $$$a,b,c \geq 1$$$; the remaining cases are left to the reader. The strategy begins by solving an easy problem between time $$$0$$$ and time $$$2$$$, a medium problem between time $$$0$$$ and time $$$3$$$, and a hard problem between time $$$0$$$ and time $$$4$$$. Then, it proceeds by solving all remaining medium problems up to time $$$b+3$$$. Afterwards, it alternatively solves an easy and a hard problem up to time $$$b+2\min(a,c)+1$$$. Finally, the remaining easy or hard problems are solved. If $$$a \geq c$$$, then only $$$1$$$ unit of computer time is wasted, so constraint (1) is tight and the strategy is optimal. On the other hand, if $$$a \leq c$$$, then at most $$$5$$$ units of contestant time are wasted, so constraint (2) is tight and the strategy is optimal.
Full solution
Let us now go back to the original task, which requires us to determine the maximum number of problems $$$n$$$ that can be solved in time $$$l$$$. To do so, we run a binary search on $$$n$$$ in the interval $$$[0, \, a+b+c]$$$. For a given candidate value of $$$n$$$, we greedily decide the types of problems to be solved: first up to $$$a$$$ easy problems, then up to $$$b$$$ medium problems, then up to $$$c$$$ hard problems, until we meet the desired total number of problems $$$n$$$ (obviously, there is no advantage in planning to solve a problem while skipping a strictly easier one). Thanks to the previous sections, we are able to determine in $$$O(1)$$$ time whether it is possible to solve the $$$n$$$ chosen problems. Once the optimal value of $$$n$$$ is found, we can print an explicit strategy in $$$O(n)$$$ time. Overall, the complexity of this solution is $$$O(\log(a+b+c) + n)$$$.
To determine whether it is possible to solve the $$$n$$$ chosen problems, we can also greedily construct an optimal strategy and check whether it takes at most $$$l$$$ time units. Such a solution does not explicitly rely on checking constraints (1) and (2).