--- title: 3D Printing categories: [Technical Logs, Individual] tags: [dart] math: true image: path: https://codejam.googleapis.com/dashboard/get_file/AQj_6U1yXmbP6Nf5PONAMbqVd5eyM5BBSbjggzDn9H6vS3ATQiqbGVrfZ0ABoAbBkn8IWocYoj1rdJim6VkTTOP4/3d_printing.png alt: "3 printers with their own ink levels." --- > This page is still in WIP. A lot of information is missing or not reviewed. {: .prompt-danger } --- Try this problem by yourself first! Check the [Code Jam Page](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a4672b). ## 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.
O     O     O
o o o
...

## 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: 1. **Case $b \leq c$.** Then $\min(b, c) = b$. And because $a \leq b$, then $a \leq \min(b, c)$. 1. **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! {: .prompt-tip}
O     O     O
o o o
...

## 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](#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: 1. Set `my_color = [0, 0, 0, 0]`. 1. Assign the current color `COL = Cyan`. 1. Compute `col = min(COL_1, COL_2, COL_3)` and assign `my_color[i] = col`, where `i` is the respective color position. 1. Compute the sum of the integers in `my_color` and store it in `sum_of_units`. 1. Is `sum_of_units >= 1 000 000`? - If it is, compute `difference = sum_of_units - 1,000,000` and assign `my_color[i] = my_color[i] - difference`. That is your color! - If it is not, assign `COL` to the next color (Magenta, Yellow or Black) and return to step 3. 1. If you're out of colors and `sum_of_units` is still less than 1,000,000, then it is impossible to solve the problem. Thus, print `IMPOSSIBLE`. Let's see some examples on how this works. ### Examples
Input 1
$$ \begin{align*} C_1 &= 768\,763 &\qquad M_1 &= 148\,041 &\qquad Y_1 &= 178\,147 &\qquad K_1 &= 984\,173 \\ C_2 &= 699\,508 &\qquad M_2 &= 515\,362 &\qquad Y_2 &= 534\,729 &\qquad K_2 &= 714\,381 \\ C_3 &= 949\,704 &\qquad M_3 &= 625\,054 &\qquad Y_3 &= 946\,212 &\qquad K_3 &= 951\,187 \end{align*} $$
Steps 1
1. $\texttt{my_color} = [0, 0, 0, 0]$. 1. We'll start with the color Cyan. 1. $\min(C_1, C_2, C_3) = 699\,508$. We assign this value to $\texttt{my_color} = [699\,508,\; 0,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 699\,508 + 0 + 0 + 0 = 699\,508$. 1. $\texttt{sum_of_units} \geq 1\,000\,000$? - **Nope.** Now follow with the color Magenta. 1. $\min(M_1, M_2, M_3) = 148\,041$. We assign this value to $\texttt{my_color} = [699\,508,\; 148\,041,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 699\,508 + 148\,041 + 0 + 0 = 847\,549$. 1. $\texttt{sum_of_units} \geq 1\,000\,000$? - **Nope.** Now follow with the color Yellow. 1. $\min(Y_1, Y_2, Y_3) = 178\,147$. We assign this value to $\texttt{my_color} = [699\,508,\; 148\,041,\; 178\,147,\; 0]$. 1. $\texttt{sum_of_units} = 699\,508 + 148\,041 + 178\,147 + 0 = 1\,025\,696$. 1. $\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!
Input 2
$$ \begin{align*} C_1 &= 1\,000\,000 &\qquad M_1 &= 1\,000\,000 &\qquad Y_1 &= 0 &\qquad K_1 &= 0 \\ C_2 &= 0 &\qquad M_2 &= 1\,000\,000 &\qquad Y_2 &= 1\,000\,000 &\qquad K_2 &= 1\,000\,000 \\ C_3 &= 999\,999 &\qquad M_3 &= 999\,999 &\qquad Y_3 &= 999\,999 &\qquad K_3 &= 999\,999 \end{align*} $$
Steps 2
1. $\texttt{my_color} = [0, 0, 0, 0]$. 1. We'll start with the color Cyan. 1. $\min(C_1, C_2, C_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 0,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 0 + 0 + 0 + 0 = 0$. 1. $\texttt{sum_of_units} \geq 1\,000\,000$? - **Nope.** Now follow with the color Magenta. 1. $\min(M_1, M_2, M_3) = 999\,999$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$. 1. $\texttt{sum_of_units} \geq 1\,000\,000$? - **Nope.** Now follow with the color Yellow. 1. $\min(Y_1, Y_2, Y_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$. 1. $\texttt{sum_of_units} \geq 1\,000\,000$? - **Nope.** Now follow with the color Black. 1. $\min(K_1, K_2, K_3) = 0$. We assign this value to $\texttt{my_color} = [0,\; 999\,999,\; 0,\; 0]$. 1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$. 1. $\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: ``` 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 ``` {: file='Input'} 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: ```dart 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> get_printers_input() { // The result will be a list of lists of integers. List> 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 input_split = input_line.split(' '); // We create a new list of integers, consisting of the four integers // that we have read. List 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. ```dart List give_color_x(List> printers, int color_pos) { // Return the color on position `color_pos`. return [ printers[0][color_pos], printers[1][color_pos], printers[2][color_pos] ]; } List return_solution(List> printers) { List 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().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.
O     O     O
o o o
...

## 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.