Mines High School Programming Competition 2022

For the last five years, the Mines Computer Science Department has hosted a High School Programming Competition (HSPC) modelled after the International Collegiate Programming Contest (ICPC). I wrote about the 2019, 2020, and 2021 competitions on this blog. This year, I wrote three of the problems and helped Colin Siles with organizing the competition.

For the first time since the 2019 competition, this year’s HSPC featured in-person teams. There was also a remote option to increase the reach of the competition. Like the past two competitions, we allowed contestants to access the internet. The problems from every year are new and written by Mines students and some Mines alum specifically for the competition.

Also for the first time we ran two concurrent competitions: a beginner competition and an advanced competition. The beginner competition was designed for first-year computer science students, while the advanced competition was designed for computer science students who had more experience. To allow for such a large number of teams, the problem writers created twenty unique problems: the most ever!

The beginner competition featured 39 teams while the advanced competition featured 26 teams. The 65 teams came from across the nation and the total count was a ten-team increase over last year resulting the largest CS@Mines HSPC ever.

In this post, I’m going to give a few highlights of the competition, and then explain the problems in the competition (with relatively detailed solution sketches).

Competition Highlights

You can view full standings for each competition at the following websites:

• Beginner: https://mines22beginner.kattis.com/standings
• Advanced: https://mines22advanced.kattis.com/standings

This year’s competition was very exciting. Here are a few highlights from the competition as a whole:

• All teams solved a problem. (Though there was one team that dropped out of the competition mid-way through.)
• All of the problems in both competitions were solved by at least one team.

Highlights from the advanced competition include:

• River Hill High School, the reigning champions, were unable to keep their hold on the top spot, but still ended up on the podium in third place with 10 problems solved.

• Last year’s runners up (PEN Academy) won first place.

• The first place (PEN Academy) and second place (Cherry Creek High School) teams both solved 11 out of 13 problems.

  Cherry Creek High School made a gallant effort in the last hour to equalize solved problems with PEN Academy and were within a single bug fix of solving a 12th problem which would have allowed them to win the competition outright.

  However, PEN Academy held them off with a late solve of their own, and ended up holding on to first based on time.

• The second place Cherry Creek Cobras were the only team to solve Edgar Mine.

• The eventual first place winners from PEN Academy also have the honour of first to solve any problem in the competition with their solve of problem A (Blaster’s Dash) one minute into the competition.

• The honour of being first to solve on a problem stretched all the way down to 13th on the scoreboard with Cyber Wolves I from Grandview High School solving problem K (Toll Booths) 13 minutes into the competition.

• Teams from Colorado had a strong showing with Cherry Creek High School (2nd), Regis Jesuit High School (4th), Rocky Mountain High School (6th), and Golden High School (9th) all placing in the top ten.

Highlights from the beginner competition include:

• Two teams (from Future Forward at Bollman and Colorado Academy) solved all of the problems in the beginner competition.
• All but five teams solved at least two problems, and all but eight solved three.
• The honour of being first to solve a problem stretched all the way down to 25th on the scoreboard with Keygen Catastrophe from Arapahoe High School solving problem A (Blaster’s Dash) 3 minutes into the competition.
• Teams from Colorado won all four top spots in the beginner competition.

The Problems

There were twenty problems in the competition written by eight different authors. The problems can be viewed at https://mines22beginner.kattis.com/problems and https://mines22advanced.kattis.com/problems. The following lists the problems featured in each competition and a short description of the algorithm required to solve the problem, listed in the order in which they appeared in each respective competition:

Beginner Competition:

• A: Blaster’s Dash – Basic arithmetic.
• B: Knight’s Move – 2-D grid computations with basic bounds checking.
• C: Weather Nodes – List processing with a two-pass algorithm.
• D: Toll Booths – List processing with a one-pass algorithm.
• E: Hard Rocks and Atomic Clocks – Modular arithmetic.
• F: Daniel’s Debugging Disaster – Basic probability.
• G: Tic-Tac-Toe AI – Lots of if statements.
• H: Office Hours – Use a dictionary or array to store a summary of data, then find the maximum.
• I: 3-Puzzle – Determine the number of steps to solve a 3-Puzzle.
• J: Mines Meal Plans – More annoying if statements.
• K: Premier League Table – Summarize a series of data and print a sorted table of information.
• L: CS Building Blueprint – Determine the quadrilateral classification of four points in 2-D Cartesian space.

Advanced Competition:

• A: Blaster’s Dash – Basic arithmetic.
• B: Babel – Flood fill
• C: CS Building Blueprint – Determine the quadrilateral classification of four points in 2-D Cartesian space.
• D: Daniel’s Debugging Disaster – Basic probability.
• E: Edgar Mine – Greedy interval covering.
• F: Radioactive Blastervium – Principle of Inclusion Exclusion
• G: Office Hours 2 – Find the two hours in a week that will maximize the total set of students able to attend office hours.
• H: Premier League Table – Summarize a series of data and print a sorted table of information.
• I: Crafting Recipes – Use a dictionary and recursion to compute a total weight of multiple subcomponents.
• J: Ultimate License Plate – Advanced probability
• K: Toll Booths – List processing with a one-pass algorithm.
• L: Lost on Campus – Dijkstra’s, or modified BFS.
• M: Spelling with Chemistry – Dynamic programming.

As you can see, there were some repeats across the competition. The harder problems in the beginner competition were low and mid-tier questions in the advanced competition.

In the beginner competition, the problems were ordered in estimated difficulty. The advanced competition had no such guarantee (except that the first problem would be the most trivial). Problems E: Edgar Mine and J: Ultimate License Plate were intended to be the most difficult problems in the advanced competition.

The following subsections are going to describe the problems and provide fairly detailed solution sketches for each one, sorted by their intended relative difficulty with the easiest ones first.

I do not try and build up from first principles in each of these explanations. Rather, I try and make the explanations accessible to anyone who feels like solving the problem is within their grasp, but they can’t figure out one or two of the key ideas to crack the problem. For the easiest problems, I start much closer to first principles, but as the problems get harder, I start assuming more and more base understanding of programming.

Additionally, I’m only presenting a single solution for each problem here. There are likely many alternative ways to solve each of these problems.

Blaster’s Dash

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.blastersdash
Author	Sumner Evans
Beginner	Problem A, 39/53 (74%) solved/tries, 100% solve rate
Advanced	Problem A, 26/28 (93%) solved/tries, 100% solve rate
Concept	basic operations on variables

Blaster’s Dash was designed to be a very trivial problem. It involves a few simple math operations. The main difficulty of this problem is figuring out which values you need to discard and how to do input/output. After you identify that you only need the value on the second line (\(n\)), the answer is \(2 \times (20 + n)\).

Knights Move

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.knightsmove
Author	John Henke
Beginner	Problem B, 21/48 (44%) solved/tries, 54% solve rate
Concept	2-D grid computations with basic bounds checking

This problem’s difficulty was slightly miscalculated by the problem writer team. It should have probably been the fourth or fifth problem instead.

The concept of the problem is fairly simple, but there are a few annoying things that must be considered when solving the problem:

1. You need to parse the algebraic notation. Indexing into the input string to get the file (the letter) and the rank (the number) is sufficient. It is also useful to convert the letter to a number to allow for easier computations.

2. Then you need to calculate all of the knight’s moves away from the cell. This can be done using hard-coded offsets.

3. For each of the possible moves, you need to make sure that you don’t print board cells that are off of the board. This involved a few if statements to check that your rank and file values were within the correct ranges.

4. Lastly, you need to print out the possible squares in the proper order (row-major), from top-left to bottom-right. The order of your checks can be hard-coded.

Weather Nodes

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.weathernodes
Author	Ryan Mapes
Beginner	Problem C, 31/132 (23%) solved/tries, 79% solve rate
Concept	list processing with a two-pass algorithm

This problem requires that you read the input into an array and then make two passes across the it. (It is probably easiest to use a for loop for this.)

On the first pass, you need to calculate the sum of all of the readings (for calculating the average). A counter variable and a for loop will suffice, however if your language has a sum function, using it will reduce the risk of typos.

After the first pass, you can save the average as a variable for the second pass where you need to determine how many of the values are too far away from the average. Using your programming language’s absolute value function is probably useful here.

The problem bounds guarantee that you don’t have to worry about floating point precision.

Toll Booths

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tollbooths
Author	Joseph Claver
Beginner	Problem D, 22/117 (19%) solved/tries, 56% solve rate
Advanced	Problem K, 25/59 (42%) solved/tries, 96% solve rate
Concept	list processing with a one-pass algorithm

This problem requires looping through all of the tolls in the input, keeping track of how much money you have at each toll.

The amount you need at the start is the maximum amount of “debt” you accrue after any toll booth. Make sure you initialize this value to 0 so you don’t give a negative answer if all booths give you BlasterBucks.

Hard Rocks and Atomic Clocks

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.hardrocksandatomicclocks
Author	Ryan Mapes
Beginner	Problem E, 31/56 (55%) solved/tries, 79% solve
Concept	modular arithmetic

This problem requires the use of the modulo operator to convert from seconds after midnight to seconds after the current hour. Then, use integer division to calculate the number of minutes after the current hour. Lastly, determine the number of minutes to sleep by subtracting the number of minutes after the current hour from 60.

Thus, the final answer is:

\[60 - \left\lfloor\frac{S \mod (60 \times 60)}{60}\right\rfloor\]

where \(S\) is the number of seconds since midnight.

Daniel’s Debugging Disaster

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.danielsdebuggingdisaster
Author	Sumner Evans
Beginner	Problem F, 11/14 (79%) solved/tries, 28% solve rate
Advanced	Problem D, 19/28 (68%) solved/tries, 73% solve rate
Concept	basic probability

This problem can be reduced to finding the probability that at least one of the \(R\) sequences of requests succeeds. In general, the probability that at least one event from a sequence succeeds is one minus the probability that none succeed.

First, the probability that a single sequence of \(N\) requests succeeds is:

\[P_{\text{sequence}} = (1-K)^N.\]

Then, the probability that none of the \(R\) sequences succeeds is given by:

\[P_{\text{all fail}} = (1 - P_{\text{sequence}})^R.\]

And finally the probability that at least one of the \(R\) sequences succeeds is:

\[1 - P_{\text{all fail}}.\]

Tic-Tac-Toe AI

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tictactoeai
Author	Sumner Evans
Beginner	Problem G, 16/58 (28%) solved/tries, 41% solve rate
Concept	many annoying conditionals

This problem requires looking at all the possible winning combinations of a tic-tac-toe board (rows, columns, and diagonals) and determining if the player can play a single move to complete said combination by putting their mark on a single empty square.

It is necessary to store the board state in a 2-D structure (array of strings, 2-D array of characters, etc.).

This problem is small enough that hard-coding is doable (albeit painful), however more clever solutions can check the win conditions using loops.

Office Hours

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.officehours
Author	Ethan Richards
Beginner	Problem H, 5/20 (25%) solved/tries, 13% solve rate
Concept	dictionaries

This problem is probably easiest to solve using a dictionary where the key is the day and time, and the value is the number of students available at that time. Then, iterate over the key-value pairs of the dictionary and determine which pair has the highest value (number of students available at that time). Then, print out the key (day and time).

If you didn’t know about dictionaries, this problem is also doable using an array (or array of arrays) representing each of the days/hours in a week as well.

3-Puzzle

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.3puzzle
Author	Adam Sandstedt
Beginner	Problem I, 7/18 (39%) solved/tries, 18% solve rate
Concept	sum of Manhattan distances (or BFS)

For a 3-puzzle, the optimal number of moves to solve the 3-puzzle is given by the Manhattan distance of each tile to its desired destination. (Note, this doesn’t extend to larger versions of the puzzle such as a standard 15-puzzle.) Thus, the simplest solution is to calculate the sum of the Manhattan distances.

Alternatively, you can solve this by performing a BFS where each node is a puzzle state, and each neighbor is a state where one tile has been moved.

Mines Meal Plans

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.minesmealplans
Author	Ethan Richards
Beginner	Problem J, 20/61 (33%) solved/tries, 51% solve rate
Concept	a few conditionals (if statements) inside a loop

The solution requires that you use a loop over all of the students, and for each you must determine how many swipes and how much munch money they have left. Then, use a series of conditionals (if statements) to determine the corresponding output.

Office Hours 2

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.officehours2
Author	Colin Siles
Advanced	Problem G, 3/6 (50%) solved/tries, 12% solve rate
Concept	use a dictionary of sets, and perform \(\mathcal{O}(n^2)\) set unions

To solve this problem, you must consider the number of students that are available in every pair of times.

The first step is to store the available students for each time period in a dictionary of sets where the key is the day/time and the value is the number of students. Then, find the union of each pair of day/time sets (using an \(\mathcal{O}(n^2)\) loop). Most programming languages have built-in set union functions. The pair that results in the largest union is the solution.

Premier League Table

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.premierleaguetable
Author	Ethan Richards
Beginner	Problem K, 2/5 (40%) solved/tries, 5% solve rate
Advanced	Problem H, 11/25 (44%) solved/tries, 42% solve rate
Concept	use a dictionary and perform some data processing and output formatting

The first step is reading the game scorelines to determine the number of points each team has and what their goal differential is (by adding the goals for, minus goals against). The best way to do this is using a dictionary where the key is the team name, and the value is some structure that holds the team’s points and goal differential. The best structure to use depends on your language and personal preference, but a tuple, struct, or class (or your language’s equivalent) is probably the best option.

Once you’ve calculated the dictionary, you need to use your programming language’s sort function with a custom sort function to sort the dictionary key-value pairs. In Java, you can implement the Comparator interface. In Python, if you store the values as tuples, the Python sort function automatically sorts by the first index, then the second index, etc.

Lastly, you have to print the sorted list in the correct format.

CS Building Blueprint

Description	https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.csbuildingblueprint
Author	Colin Siles
Beginner	Problem L, 2/8 (25%) solved/tries, 5% solve rate
Advanced	Problem C, 3/33 (9%) solved/tries, 12% solve rate
Concept	trigonometry or linear algebra on a set of points

There are many ways to solve this problem. Here is one way:

1. Order the points by using trigonometry to determine the angle a line connecting each point to the origin would make with the \(x\)-axis
2. Determine vectors that represent each side of the shape
3. Determine the length of each side of the shape
4. Determine which sides are orthogonal to one another by using the property that the dot product of two orthogonal vectors is 0
5. Determine which sides are parallel to one another by using the property that the cross product of two parallel vectors is 0
6. Use these properties to classify the shape by the provided definitions

Most languages have built-in trigonometric functions in their corresponding math libraries.

If you don’t know any linear algebra, all of the computations can be done using trigonometry. For example, you can calculate and compare the slope of each of the sides of the quadrilateral to determine parallelism (this has the downside of having to deal with vertical lines as a special case). Calculating whether or not an angle is a right angle is possible using pure trigonometry as well.

Crafting Recipes

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.craftingrecipes
Author	Ryan Mapes
Advanced	Problem I, 11/41 (27%) solved/tries, 42% solve rate
Concept	use a dictionary and recursion

This problem is solved using recursion. The raw materials have known costs and serve as the base cases. In the recursive case, consider all of the components of the part. For each component, multiply the quantity by the cost of the component (calculated recursively). Then, sum the costs to determine the cost of the part.

Spelling With Chemistry

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.spellingwithchemistry
Author	Adam Sandstedt
Advanced	Problem M, 4/31 (13%) solved/tries, 15% solve rate
Concept	dynamic programming

This problem requires dynamic programming, a technique for optimizing recursive algorithms. The first step to a dynamic programming problem is to find the recursive formulation for the problem. The following is a recursive formulation for the problem:

One way to think of the above recursive formulation intuitively is to focus only on what happens at the start of the word \(w\). If the start of \(w\) doesn’t correspond to an element name, then there are 0 ways to spell the start of that word with the given element. If the start of \(w\) does correspond to one of the element names, then the number of ways that you can create the rest of the word (without the element name) needs to be added to the count of the ways you can spell the current word.

The key insight from dynamic programming is that \(P\) is called many times with the same input, so you can cache (save and not recompute later) the results of \(P\). This can be accomplished via a table or memoization (using a dictionary to store the function input to its corresponding output).

Lost on Campus

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.lostoncampus
Author	Joseph Claver
Advanced	Problem L, 3/8 (38%) solved/tries, 12% solve rate
Concept	Dijkstra’s shortest path algorithm

This problem is solved most easily with Dijkstra’s algorithm, which finds the shortest path between two points in a weighted graph. If you solve using Dijkstra’s, the graph needs to be modelled where each transition through a cell with a door has a cost of 1, and all other transitions have a cost of 0.

Alternatively, you could use BFS/flood fill to convert the map into an unweighted graph where each node represents a “room” (a collection of cells that can be accessed without passing through a door), and all edges represent doors between such rooms. The minimum number of doors can be computed by performing BFS on this graph.

Babel

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.babel
Author	John Henke
Advanced	Problem B, 4/35 (11%) solved/tries, 15% solve rate
Concept	flood fill

The key difficulty with this problem is that the number of pairs of points that can be given in the problem is large (up to 1,000) and the map is also large (up to 1,000,000). Because of this, the naive solution of performing a BFS (or any traversal, even an efficient one such as A*) for each query will not be fast enough.

The queries must be able to be performed in amortized constant time. To accomplish this, you can pre-compute the region that every point is in, and then the query can just check whether the region of the two points is the same.

To determine the cells within a region, you can perform a flood fill on the region, marking each cell within the region with an integer “region ID”.

You can pre-compute all regions, and then each of the queries will be constant time or you can compute the regions only when necessary.

Edgar Mine

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.edgarmine
Author	John Henke
Advanced	Problem E, 1/10 (10%) solved/tries, 4% solve rate
Concept	reduce to the minimum segment cover problem

This problem reduces to the minimum segment cover problem which has a \(n \log n\)-time solution.

The minimum segment cover problem asks what is the minimum number of segments (closed intervals) required to fully cover an interval (that is, ensure that every point within the interval is within at least one segment).

To compute the segments, you must apply the math given in the problem to calculate the span of the mine-shaft floor that the light bulb illuminates to the required level. This requires using the Pythagorean theorem using the maximum distance at which the light is bright enough to satisfy the lighting requirement as the hypotenuse.

Once the segments are computed, any efficient solution to the minimum segment cover problem can be used.

There is a \(n \log n\)-time greedy solution which is as follows:

1. Sort the list list of the segments
2. Keep track of the leftmost uncovered point (it will start as the entrance of the mine shaft in this problem, 0)
3. Select the segment that extends furthest to the right that covers the leftmost uncovered point.
4. Set the leftmost uncovered point to the rightmost point of the selected segment.
5. Repeat steps 3-4 until the entire interval is covered.

Radioactive Blastervium

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.radioactiveblastervium
Author	Joseph Claver
Advanced	Problem F, 7/116 (6%) solved/tries, 27% solve rate
Concept	the principle of inclusion-exclusion

For this problem, the naive solution of enumerating the sets and computing their union is too slow, since the interval is too large to enumerate. The problem has a time limit of 1 second, which is realistically enough to do somewhere between \(10^6\) and \(10^7\) iterations (you may be able to push it slightly higher with very efficient loops) but this is still far away from the \(10^{15}\) maximum interval size.

This problem can be solved using the principle of inclusion-exclusion which is a way of computing the cardinality of unions of sets without enumerating the sets or when you only are able to compute size and intersection of the sets. In the simplest case, the size of the union of two sets is the sum of the sizes of the sets minus the size of the intersection of the sets (to avoid double-counting items in both sets):

\[ |A \cup B| = |A| + |B| - |A \cap B| \]

In the case of three sets, you add the size of each set, subtract the size of the intersection of every pair of sets, then add the size of the intersection of all three sets. This pattern can be extended for more than three sets, with the sign alternating for each group of terms.

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C \]

For this problem, each interval has a corresponding set containing all the times it would emit radiation. Then, to compute the above equation:

• The cardinality of any given set can be found be dividing the length of the time frame, \(T\), by the interval period.

• The cardinality of an intersection of a set of interval periods is the same as the cardinality of a single interval period whose product is the lengths of the original intervals.

The next challenge is to compute the combinations for each “level” of the equation. Many languages have utilities to compute combinations of elements (and it’s highly recommended that you use such utilities because computing combinations is quite difficult to program).

After all of this, the cardinality of the union of all of the interval periods is the number of particles that get emitted.

Ultimate License Plate

Description	https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.ultimatelicenseplate
Author	Mohammed Alnasser
Advanced	Problem J, 2/27 (7%) solved/tries, 8% solve rate
Concept	complex combinatorics

We can calculate the number of unique license plates with exact counts for certain characters by calculating the number of permutations with repetition. The number of permutations for a total of \(n\) items with \(n_i\) repetitions of the \(i^{\text{th}}\) item is:

\[ \frac{n!}{n_1!n_2! ... n_k!} \]

Naively, we could thus iterate over every possible combination of the exact number of times characters appear in the license plate, discarding combinations that would contain too many letters, while summing up the number of license plates for combinations that are valid. But this is too slow.

This problem requires that you find a clever way to add up the number of possible license plates. For example, instead of discarding combinations that would contain too many characters, you must avoid iterating over them at all. Alternatively, a recursive solution exists to count the number of 1-length license plates, and then build upwards to the complete license plate.