This page is still in WIP. A lot of information is missing or not reviewed.
Try this problem by yourself first! Check the Code Jam Page.
Overview
We have three printers, each with its own ink levels. We have $C_i$ for the ink level of Cyan on the $i$th printer, $M_i$ for the Magenta level, $Y_i$ for the color Yellow and $K_i$ for Black. The ink is measured on units. On each printer we want to print a big D that requires 1,000,000 units of ink. Each D must have the same color. We need to find that color.
What we want is to find $c, m, y, k$ integers such that
\[\begin{eqnarray} & c \leq C_i \qquad m \leq M_i \qquad y \leq Y_i \qquad k \leq K_i \,, \qquad \forall i, \; 1 \leq i \leq 3 . \end{eqnarray}\]To solve this problem, it is sufficient that the integers satisfy the following inequalities:
\[\begin{eqnarray} & c \leq \min(C_1, C_2, C_3) \qquad m \leq \min(M_1, M_2, M_3) \\ & y \leq \min(Y_1, Y_2, Y_3) \qquad k \leq \min(K_1, K_2, K_3) . \end{eqnarray}\]We can then set each integer to the minimum of the ink of its corresponding color. Finally, depending on the sum of the integers, we can determine if the problem is impossible or if we can find a solution.
Context
We’re give three printers. Each one has its own ink levels for Cyan ($C_i$), Magenta ($M_i$), Yellow ($Y_i$) and Black ($K_i$). We need to print three big D’s for the Database Design Day logo. Each D must be printed on one printer and all of the D’s must have the same color. That is, we must select a color with four levels of ink $c$, $m$, $y$ and $k$ such that $c \leq C_i$, $m \leq M_i$, $y \leq Y_i$ and $k \leq K_i$, for $1 \leq i \leq 3$.
The total amount of ink needed to print a single D is $10^6$ units. There may exist more than one possible solution or even none. If at least one solution exists, we can output any solution. If there’s none, we print IMPOSSIBLE.
A minimum property
We have the following property:
\[\begin{eqnarray} & \text{If} \quad a \leq b \quad \text{and} \quad a \leq c \quad \text{then} \quad a \leq \min(b, c) . \end{eqnarray}\]To see why this is true, we can divide it in two cases:
- Case $b \leq c$. Then $\min(b, c) = b$. And because $a \leq b$, then $a \leq \min(b, c)$.
- Case $b > c$. Then $\min(b, c) = c$. And because $a \leq c$, then $a \leq \min(b, c)$.
It is analogous to see that if $a \leq b, \; a \leq c$ and $a \leq d$, then $a \leq \min(b, c, d)$. Try it yourself!
Solution
To solve this problem, let’s take another look at the inequalities at the beginning of this section and expand them:
\[\begin{eqnarray} & c \leq C_1 \qquad m \leq M_1 \qquad y \leq Y_1 \qquad k \leq K_1 , \\ & c \leq C_2 \qquad m \leq M_2 \qquad y \leq Y_2 \qquad k \leq K_2 , \\ & c \leq C_3 \qquad m \leq M_3 \qquad y \leq Y_3 \qquad k \leq K_3 \end{eqnarray}\]Using a minimum property on each ink, we then have that:
\[\begin{eqnarray} & c \leq \min(C_1, C_2, C_3) , \qquad m \leq \min(M_1, M_2, M_3) , \\ & y \leq \min(Y_1, Y_2, Y_3) , \qquad k \leq \min(K_1, K_2, K_3) . \end{eqnarray}\]The algorithm
Having everything prepared, we can explain the following algorithm that searches for a possible solution:
- Set
my_color = [0, 0, 0, 0]. - Assign the current color
COL = Cyan. - Compute
col = min(COL_1, COL_2, COL_3)and assignmy_color[i] = col, whereiis the respective color position. - Compute the sum of the integers in
my_colorand store it insum_of_units. - Is
sum_of_units >= 1 000 000?- If it is, compute
difference = sum_of_units - 1,000,000and assignmy_color[i] = my_color[i] - difference. That is your color! - If it is not, assign
COLto the next color (Magenta, Yellow or Black) and return to step 3.
- If it is, compute
- If you’re out of colors and
sum_of_unitsis still less than 1,000,000, then it is impossible to solve the problem. Thus, printIMPOSSIBLE.
Let’s see some examples on how this works.
Examples
- $\texttt{my_color} = [0, 0, 0, 0]$.
- We’ll start with the color Cyan.
- $\min(C_1, C_2, C_3) = 699\,508$. We assign this value to $\texttt{my_color} = [699\,508,\; 0,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 699\,508 + 0 + 0 + 0 = 699\,508$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. Now follow with the color Magenta.
- $\min(M_1, M_2, M_3) = 148\,041$. We assign this value to $\texttt{my_color} = [699\,508,\; 148\,041,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 699\,508 + 148\,041 + 0 + 0 = 847\,549$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. Now follow with the color Yellow.
- $\min(Y_1, Y_2, Y_3) = 178\,147$. We assign this value to $\texttt{my_color} = [699\,508,\; 148\,041,\; 178\,147,\; 0]$.
- $\texttt{sum_of_units} = 699\,508 + 148\,041 + 178\,147 + 0 = 1\,025\,696$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Yup. $\texttt{difference} = 1\,025\,696 - 1\,000\,000 = 25\,696$.
- $\texttt{my_color[3]} = 178\,147 - 25\,696 = 152\,451$.
- $\texttt{my_color} = [699\,508,\; 148\,041,\; 152\,451,\; 0]$ is our color!
- $\texttt{my_color} = [0, 0, 0, 0]$.
- We’ll start with the color Cyan.
- $\min(C_1, C_2, C_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 0,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 0 + 0 + 0 + 0 = 0$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. Now follow with the color Magenta.
- $\min(M_1, M_2, M_3) = 999\,999$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. Now follow with the color Yellow.
- $\min(Y_1, Y_2, Y_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. Now follow with the color Black.
- $\min(K_1, K_2, K_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$.
- $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
- $\texttt{sum_of_units} \geq 1\,000\,000$?
- Nope. We’re out of colors. D:
- Print
IMPOSSIBLE.
The Code
Remember that Code Jam asks us to read the ink levels from the input. For the examples above, the input would have looked like this:
1
2
3
4
5
6
7
2
768763 148041 178147 984173
699508 515362 534729 714381
949704 625054 946212 951187
1000000 1000000 0 0
0 1000000 1000000 1000000
999999 999999 999999 999999
To read the input, we need to first read the first integer $T$ and then repeat our algorithm $T$ times. Here’s the code on how to read the printers input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
String get_input_string()
{
// Read input. If it is null, return an empty string.
var my_input = stdin.readLineSync();
if (my_input != null)
return my_input;
else
return '';
}
List<List<int>> get_printers_input()
{
// The result will be a list of lists of integers.
List<List<int>> printers = [];
for (int j = 0; j < 3; j++)
{
// We read the whole input line once. This is the info of one printer.
String input_line = get_input_string();
// We split the input using the space (' ') as a separator.
List<String> input_split = input_line.split(' ');
// We create a new list of integers, consisting of the four integers
// that we have read.
List<int> input_ints = [
int.parse(input_split[0]),
int.parse(input_split[1]),
int.parse(input_split[2]),
int.parse(input_split[3])
];
// Finally we append the new list to our resulting list of printers.
printers.add(input_ints);
}
return printers;
}
With the printers info, we can then code the algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
List<dynamic> give_color_x(List<List<int>> printers, int color_pos)
{
// Return the color on position `color_pos`.
return <dynamic>[
printers[0][color_pos],
printers[1][color_pos],
printers[2][color_pos]
];
}
List<int> return_solution(List<List<int>> printers)
{
List<int> my_colors = [0, 0, 0, 0];
for (int i = 0; i < 4; i++)
{
// Select color `i` and compute the minimum.
num min_units = give_color_x(printers, i).cast<num>().reduce(min);
// Assign the minimum to our variable `min_colors`.
my_colors[i] = min_units.toInt();
// Compute the sum of all our ink units.
int sum_of_units = my_colors.reduce((a, b) => a + b);
if (sum_of_units >= 1000000)
{
// If the sum is more than 1,000,000, compute the difference and
// subtract it from the last used color.
int difference = sum_of_units - 1000000;
my_colors[i] = my_colors[i] - difference;
break;
}
}
return my_colors;
}
We then finally check if the sum of our colors is exactly 1,000,000. If it is, there’s our solution! If it isn’t, it is impossible.
Alternative Solutions
There was a slight variation from our approach. Instead of computing the minimum of an ink and immediately seeing if the sum is greater than or equal to 1,000,000, we would compute the minimum of each ink first. If the sum of the minimum of the inks is greater than or equal to 1,000,000, then it was possible to find a solution. We would then calculate the difference between the sum and 1,000,000. Finally we would subtract the difference from an ink. Here was my problem. If the difference was greater than a single ink, we would choose multiple inks to subtract from. I thought that checking after every ink was an easier problem than subtracting from possibly multiple inks.