Mines High School Programming Competition 2019

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

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.

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 (a branch of computer science) called the minimum spanning tree (MST) problem. 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 (proof left for readers enjoyment).

This problem can be solved using a greedy algorithm which means that you do not have to do any global optimization. The Wikipedia page on the MST problem describes many algorithms for solving this problem, but here is the outline of a potential solution (this solution is basically Kruskal’s 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 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.