# Mines High School Programming Competition 2019

Source: https://sumnerevans.com/posts/school/2019-hspc/
Published: 2019-04-15
School, High School Programming Competition, Competitive Programming, Mines, HSPC

For the last two years, the Mines Computer Science Department has hosted a High
School Programming Competition modelled after the
[International Collegiate Programming Contest (ICPC)](https://icpc.global/). The
Mines ACM Student Chapter does the vast majority of organization and operations
for the competition. As Chair of Mines ACM, I was responsible for a lot of the
organizational aspects of the competition.

The competition saw teams from around the Denver metro area, and even as far
away as Steamboat, come to compete by solving programming problems. The problems
ranged in difficulty from a problem requiring contestants to take two numbers
and multiply them together, to a problem where the students were required to
implement an algorithm to solve the
[Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)
problem.

In this post, I'm going to talk about a few highlights of the competition, and
the problems in the competition (with relatively detailed solution sketches).

## Competition Highlights

**You can view full standings for the competition at:**
https://mines19.kattis.com/standings

This year's competition was very exciting. All of the contestants at HSPC this
year did a great job. Here are a few highlights of the competition:

- All teams solved at least two problems.
- STEM Team 1 (1st) solved all of the problems!
- STEM Team 1 was the only team to solve both problem C and G.
- Despite not solving a problem until the 70th minute, Team 2 stormed ahead and
  reached third place.
- Neither IntrospectionExceptions (2nd) nor Team 2 (3rd) were first to solve any
  problem, but they both solved 8 problems (more problems than the 4th place
  team) which is the primary sort for the competition standings.
- The fourth place team solved three problems first (second most in the
  competition).

## The Problems

There were ten problems in the competition written by six different authors. The
problems can be viewed at https://mines19.kattis.com/problems. The following
lists each of the problems' names and a short description of the problem in the
order in which they appeared in competition:

- **A: Alliteration** -- Keep track of the most commonly seen first letter in a
  line of words.
- **B: Number Reduction** -- Output the number of steps to perform the _Colatz
  Conjecture_ on a given integer \(n\).
- **C: Classrooms and Calculators** -- Given a set of _scheduling conflicts_,
  determine the \(n^{th}\) day without a conflict.
- **D: Darts for Programmers** -- Maximize ranges around a circular array.
- **E: Tree Skiing** -- Calculate the number of Manhattan-paths (with the
  restriction of not being able to backtrack) between two points on a grid. This
  is alternatively a combinatorics problem.
- **F: Ski Traffic** -- Calculate the time required to arrive at a ski slope,
  given a set of conditions such as traffic.
- **G: Misty** -- Solve the minimum spanning tree problem.
- **H: Hack-a-Holics** -- Multiply two numbers together.
- **I: Sudoku Verify** -- Verify a Sudoku puzzle.
- **J: Rent Division** -- Calculate how much rent a set of roommates must pay to
  equal out their total contribution (where their total contribution includes
  shared, non-rent expenses).

Problem **H** was designed to be the easiest problem, while **G** was designed
to be the hardest problem. The following subsections are going to describe the
problems, sorted by their intended relative difficulty with the easiest ones
first. A few of the difficulties were miscalculated by the problem authors, and
I will mention those in each subsection. Note, these sketches will make the most
sense if you read the problem description first. Additionally, there are likely
alternative ways to solve many of the problems. I'm only presenting a single
solution for each problem here.

### H - Hackaholics

|                 |                                                         |
| --------------- | ------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.hackaholics |
| **Author**      | Sumner Evans                                            |
| **Attempts**    | 27                                                      |
| **Correct**     | 22                                                      |
| **Percentage**  | 81% (highest in competition)                            |

Hackaholics was designed as a very trivial problem. You are given three numbers,
and you have to output the product of two of them. The only real difficulty with
this problem is understanding the problem description enough to know which
numbers you care about and need to multiply, and which one you can discard.

### B - Number Reduction

|                 |                                                             |
| --------------- | ----------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.numberreduction |
| **Author**      | Jordan Newport                                              |
| **Attempts**    | 43                                                          |
| **Correct**     | 20                                                          |
| **Percentage**  | 47%                                                         |

The objective of this problem is to determine the number of steps required to
perform the _Collatz Conjecture_. The Collatz Conjecture is that for every
positive integer, if you apply the following function to the number iteratively,
you will eventually arrive at 1.

\[ f(n) = \begin{cases} n / 2 & \text{$x$ is even} \\ 3n + 1 & \text{$x$ is odd}
\\ \end{cases} \]

Another way to state the above function is "if \(x\) is even, divide by two, if
\(x\) is odd, multiply by 3 and add 1". You can read more about the Collatz
Conjecture at
[this Wikipedia article](https://en.wikipedia.org/wiki/Collatz_conjecture).

To solve the actual problem, you can just keep applying the above function on
the input until you get 1, keeping track of how many steps it takes. Then,
output the number of steps.

### F - Ski Traffic

|                 |                                                        |
| --------------- | ------------------------------------------------------ |
| **Description** | https://mines19.kattis.com/problems/mines19.skitraffic |
| **Author**      | Liam warfield                                          |
| **Attempts**    | 47                                                     |
| **Correct**     | 18                                                     |
| **Percentage**  | 38%                                                    |

This problem requires you to read in the time, day, whether the weather is bad,
whether it snowed, and whether it is a holiday. Then you have to multiply the
time by the factors specified in the problem, depending on the values of the
variables you read in.

The difficulty of this problem comes from a few sources. First, you have to
carefully read the description to make sure you understand how each of the
factors affect the time. Second, you have to handle time correctly. The easiest
way to handle time is convert it to minutes before performing the
multiplications. Then, convert back to the `H:MM` format when outputting the
time it will take to reach the ski hill.

### J - Rent Division

|                 |                                                          |
| --------------- | -------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.rentdivision |
| **Author**      | Joseph McKinsey                                          |
| **Attempts**    | 81                                                       |
| **Correct**     | 7                                                        |
| **Percentage**  | 9%                                                       |

This problem was intended to be one of the easier problems in the competition,
but it turned out to be much harder than expected (as you can see from the
success percentage). I think a lot of teams attempted to implement this by
looping and incrementing what each roommate paid until the rent and other
expenses were covered. This, is probably doable, but it is really annoying to
keep track of, and may (if done inefficiently) fail with time limit exceeded
(TLE).

To solve this problem without pulling your hair out, you need to notice that the
roommates collectively must pay \(R + \sum_i{e_i}\) dollars worth of expenses,
where \(R\) is the rent for the month, and \(e_i\) is the amount that person
\(i\) has spent on non-rent expenses. Thus, each roommate must pay a total of

\[ S = \frac{R + \sum_i{e_i}}{N} \]

worth of expenses that month. If any \(e_i > S\) (meaning that the roommate has
paid more than his fair share of the expenses) then you need to output "not
possible". Otherwise, roommate \(i\) must pay \(S - e_i\) worth of the rent to
even out his contribution to the total expenses for the month.

> [!NOTE]
>
> This problem was inspired by the author's actual apartment expenses situation
> (except, of course, the author doesn't actually need help with this
> calculation), and all of the names featured in this story are real.

### D - Darts for Programmers

|                 |                                                                 |
| --------------- | --------------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.dartsforprogrammers |
| **Author**      | Sumner Evans (Idea by Matt Iverson)                             |
| **Attempts**    | 30                                                              |
| **Correct**     | 5                                                               |
| **Percentage**  | 17%                                                             |

This problem was probably the weakest problem in the entire set as far as
quality. The problem description was very precise, but it was quite difficult to
parse the problem description, and if you misunderstood or misread even a small
part of the problem description, you could easily make an incorrect assumption.
This problem was intended to be on the easier side of the middle-of-the-pack
difficulty problems, but it ended up being slightly harder than intended and I
think that the weakness of the description contributed to that.

To solve the problem, you need to keep track of the wedge numbers in an array.
You can use this to calculate the sums of the wedge numbers between the darts on
the dartboard. The key here is that you will have to _circularly_ wrap around
the array (one easy way of doing that is to modulo by the number of wedges (20)
whenever you increment as you are going through the array). Another thing you
have to be aware of is the fact that you may need to sort the wedge numbers by
their order around the dartboard. Once you have done that, your answer is simply
the maximal sum.

### A - Alliteration

---

|                 |                                                          |
| --------------- | -------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.alliteration |
| **Author**      | Matt Iverson                                             |
| **Attempts**    | 19                                                       |
| **Correct**     | 10                                                       |
| **Percentage**  | 53%                                                      |

This problem was intended to be basically at the mid-point as far as problem
difficulty, and given the actual competition data, that was what happened.

To solve this problem, for each line of the input, you must

1. Iterate through each of the words on the line (using your language's string
   splitting function is advisable for this).
2. Use of a dictionary, or similar data structure, to count how many times each
   letter appears at the start of a word.
3. Output the letter that appears at the start of the most words on that line.
   This requires knowing how to do a maximization on the value of a dictionary
   which can be done either via a `for` loop or your language's built-in `max`
   function and an appropriate comparison function.

### C - Classrooms an Calculators

|                 |                                                                      |
| --------------- | -------------------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.classroomsandcalculators |
| **Author**      | Matt Iverson                                                         |
| **Attempts**    | 70                                                                   |
| **Correct**     | 1                                                                    |
| **Percentage**  | 1% (lowest in competition)                                           |

Despite its actual difficulty in competition, this was not intended to be one of
the hardest problems in the competition. I think that the description and sample
inputs made it very appealing to attempt with a brute force solution by
iterating through the days checking each one for whether or not they can play on
a that day. However, that is where the difficulty of this problem was hidden.
The bounds on the problem are so large that it is not possible to do that
approach. Rather, this requires you to derive a mathematical formulation for
solving the problem under the time limit.

The key observation you must make for this problem is that the pattern of
availability will repeat itself after a certain amount of days. You can
calculate the precise number of days that will be required for the pattern to
repeat (it's the least-common multiple (LCM) of \(d_1, d_2, d_3\)), but it is
actually not necessary to compute the LCM for this problem. Instead, you can
just observe that the pattern is guaranteed to repeat at least every \(\prod d_i
= d_1 \times d_2 \times d_3\) days because \(\prod d_i\) is guaranteed to be a
multiple of \(\text{LCM}(d_1, d_2, d_3)\) (proof of this is left to the reader).
We call this product the _period_.

You then need to extend the pattern for the first \(\prod d_i\) days forward
until you find the \(n^\text{th}\) day they can play. An important detail here
is that there are going to be some number of full repeats of the pattern, call
them _full periods_ (it could be 0), and then one partial repeat of the pattern:
the _partial period_. Thus, we can use math to calculate the number of days
taken up by all the full periods and add that to the number of days that we need
to go into the partial period. Stated mathematically, you can use the following
formula to perform the extension process:

\[ \underbrace{\left\lfloor\frac{n - 1}{|A|}\right\rfloor}_{1} \times
\underbrace{\prod d_i}_{2} + \underbrace{A[\underbrace{(n - 1) mod |A|}_{3}]}_4
\]

where \(A\) is an array of the day numbers which the friends can play in the
first \(\prod d_i\) days, and \(|A|\) denotes the length of \(A\). One way to
break the formula down for easier comprehension is as follows:

- **1**: the number of _full periods_ required before getting to the
  \(n^\text{th}\) day.
- **2**: the number of days per period.
- **3**: the number of days that the friends have to play in the partial period.
- **4**: the number of days into the partial period that the friends have to go
  before arriving at the \(n^\text{th}\) day.

### I - Sudoku Verify

|                 |                                                          |
| --------------- | -------------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.sudokuverify |
| **Author**      | Sumner Evans                                             |
| **Attempts**    | 22                                                       |
| **Correct**     | 12                                                       |
| **Percentage**  | 55%                                                      |

The premise of this problem is extremely simple: determine whether or not the
solution to a sudoku puzzle is valid.

The main difficulty of this problem comes from having to manipulate data
structures. It is critical that you read the input into a good data structure (a
2D array is probably one of the best data structures to use). Then, you need to
determine whether or not every row, column, and region is valid. This is
difficult because you first have to get all of the numbers in that row, column,
or region in a data structure that is easy to use. One option is to put all of
the numbers in the row/column/region into a set, and subtract that set from a
base set: \(\{1, 2,\ldots,9\}\). If there are any leftovers after the
subtraction, then the puzzle solution is invalid (there was a duplicate
somewhere in that row, column, or region).

### E - Tree Skiing

|                 |                                                        |
| --------------- | ------------------------------------------------------ |
| **Description** | https://mines19.kattis.com/problems/mines19.treeskiing |
| **Author**      | Sam Sartor                                             |
| **Attempts**    | 16                                                     |
| **Correct**     | 4                                                      |
| **Percentage**  | 25%                                                    |

This problem was intentionally written such that you could implement it in
basically any way that will give a correct answer, and it will basically never
give you a TLE. Two solutions which will work for this problem are:

- Exhaustively enumerate every single path from the start to the target,
  counting how many there are (excluding the one that your friend went on).

  You can do this using something resembling a graph traversal such as BFS or
  DFS.

- Alternatively, you can notice that for any path to reach the clearing, you
  must go north exactly of \(k\) times, and west exactly \(m\) times where \(k\)
  is the number of "N"s in the input, and \(m\) is the number of "W"s in the
  input. (Note that \(k = n - m\) where \(n\) is the length of the friend's
  path.) Thus, any given path can be described by which steps you go north (all
  non-north movements are by default going west).

  Thus, the number of paths from the start to the clearing are precisely \(n
  \choose k\) (or \(n \choose m\), they are equivalent). We can compute \(n
  \choose k\) as follows:

  \[ \binom{n}{k} = \frac{n!}{k!(n - k)!} \]

  where \(n\) and \(k\) are as defined above. It's critical, however, to
  remember that your friend has already taken one of the paths, and you cannot
  go on that path. Thus, the answer is actually \(\binom{n}{k} - 1\).

### G - Misty

|                 |                                                   |
| --------------- | ------------------------------------------------- |
| **Description** | https://mines19.kattis.com/problems/mines19.misty |
| **Author**      | Sumner Evans                                      |
| **Attempts**    | 3                                                 |
| **Correct**     | 1                                                 |
| **Percentage**  | 33%                                               |

This problem was intended to be the hardest in the competition, and I think it
was, considering so few teams even attempted to solve it (2), and only one of
them actually did solve it.

This problem is a classic problem in
[graph theory](https://en.wikipedia.org/wiki/Graph_theory) (a branch of computer
science) called the
[_minimum spanning tree (MST)_ problem](https://en.wikipedia.org/wiki/Minimum_spanning_tree).
You have to model the problem as a _weighted graph_ where the nodes (vertices)
are the houses, the edges are the paths, and the weights are the distances. Once
you have modeled the problem in this way, you then need to find a subset of the
edges (paths) in the graph which:

1. Ensures there is a path from every node (house) to every other node.
2. Does that at the minimal _cost_, that is, sum of path distances.

This subgraph will be a
[_spanning tree_](https://en.wikipedia.org/wiki/Spanning_tree) (proof left for
readers enjoyment).

This problem can be solved using a
[_greedy_ algorithm](https://en.wikipedia.org/wiki/Greedy_algorithm) which means
that you do not have to do any global optimization. The
[Wikipedia page on the MST problem](https://en.wikipedia.org/wiki/Minimum_spanning_tree)
describes many algorithms for solving this problem, but here is the outline of a
potential solution (this solution is basically
[_Kruskal's Algorithm_](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm)):

1. Sort all of the edges by length.
2. Iterate until the entire graph has been connected. On each iteration,

   1. Get the next shortest edge by length.
   2. If adding the edge would create a cycle in the tree, then ignore it.
   3. If it would not create a cycle, add it to the tree.

This is a simplistic, high-level idea of Kruskal's algorithm. That is the thing
with graph algorithms generally: the _idea_ of them is pretty simple; but the
devil really is in the details. For Kruskal's algorithm in particular, detecting
cycles is non-trivial, and is one of the most computationally expensive parts of
the algorithm. For the time limit for this problem, you can be fairly
inefficient with how you detect cycles (no need to implement something like a
[disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)
or something ridiculous like that). Storing sets of already connected vertices
is sufficient for solving this problem under the time limit, and even doing a
BFS/DFS to see if you can reach one vertex from the other vertex in the current
tree is fast enough (assuming a reasonably efficient BFS/DFS implementation).
Additionally, since the point of this problem was to make contestants implement
an algorithm, I intentionally designed the input format such that reading in the
graph would not be too difficult.

> [!NOTE]
>
> This was by far my favourite problem. I wanted to put a graph theory problem
> in the competition and I had been working on this problem for nearly a year. I
> chose the algorithm and the name of the problem at the same time because if
> you say MST really fast, it kinda sounds like "misty". After I thought of the
> algorithm and the name, I was able to then add in another of my favourite
> topics: Star Wars, and I did so without even mentioning any names.