Jonathan Sumner Evans
Sumner Evans
Software Engineer at Automattic working on Beeper

Mines High School Programming Competition 2021

Written by Human, Not by AI

For the last four 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 and 2020 competitions on this blog. This year, I wrote one of the problems and helped with some of the administrative backend. I also hosted a live broadcast during the competition with another CS@Mines alum, Sam Sartor which you can view on YouTube. In the broadcast, we provided commentary on the competition, hosted interviews with problem authors, and talked to former HSPC and ICPC contestants.

 CS@Mines High School Programming Competition 2021

Similar to the 2020 competition, due to the ongoing COVID-19 lockdowns, the competition was held remotely. As such, we were again unable to enforce a no-internet rule as we are able to during on-site competitions. Luckily, the problems are all unique, and written by Mines students and Mines alum specifically for the competition which makes it very difficult to search the internet for answers.

The competition saw a total of 55 teams from all around the nation, the most ever in a CS@Mines HSPC. The problems ranged in difficulty from a problem requiring contestants to perform very basic arithmetic, to a problem that required the use of dynamic programming.

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). Additionally, this year for the first time interviews with (most of) the problem authors are also available.

Competition Highlights

You can view full standings for the competition at: https://mines21.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, and all but one team solved at least four problems.
  • Five teams solved all thirteen of the problems.
  • The top three teams were from out-of-state.
  • River Hill High School won both first and third place. Both teams solved all of the problems in the first ninety minutes.
  • Teams from Colorado won fourth and fifth place, with Rocky Mountain High School taking fourth, and STEM School Highlands Ranch (winners last year) taking fifth.
  • PEN A Team (second place) came back for second in the 124th minute, winning on time because they only had one incorrect submission as compared to River Hill High School Team 2 who had nine incorrect submissions.
  • The Fellowship of the String (fifth place) solved problem M in the 206th minute, four minutes before the end of the competition.

The Problems

Warning

The rest of this post should be treated like a solutions manual. I hope that this is an extremely helpful resource when you get stuck, but you should try to solve each of the problems before reading the solutions. There’s no magic amount of time that you should try to solve the problem before looking at the solution sketch, but I think a good rule of thumb is after you’ve tried at least three ideas on your own, then you can read at the solution sketch.

Remember: You will not learn anything if you just read the explanations!

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

  • A: M-Climb – Basic arithmetic.
  • B: 13 Floors – Use an if statement.
  • C: Rolling the Dice – Simple arithmetic
  • D: Tall Enough – Verify that all numbers in a list are greater than a constant.
  • E: Marble Maze – State machine with a time-step simulation.
  • F: Follow the Prize – Simple state machine.
  • G: Alphabet Soup – Simple set subtraction.
  • H: Powering Teslopolis – Calculate grid adjacencies.
  • I: Tic-Tac-Toe – Determine who won a tic-tac-toe game.
  • J: Quadratic Autopilot – Solve for the coefficients of a parabola.
  • K: Knight Walk – Breadth-first search (BFS).
  • L: Math in Another Universe – Math evaluation with different precedence.
  • M: Delivery Driver – Dynamic programming.

Problem A was designed to be the easiest problem, while M was intended to be the hardest problem. 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. Interviews with the problem authors of each problem are also provided.

I do not try and build up from first principles in each of these explanations (and corresponding videos). 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.

Slightly less detailed solution sketches were presented at the closing ceremonies which can be viewed below.

 CS@Mines HSPC 2021 Solution Sketch Presentation

A - M-Climb

Descriptionhttps://mines21.kattis.com/problems/mines21.mclimb
AuthorJack Garner
Attempts71
Correct55
Percentage100%
Conceptbasic operations on variables

M-Climb was designed to be a very trivial problem. It was inspired by the annual M-Climb tradition at Mines where freshmen hike up Mount Zion to the big M with 10-pound rocks from their hometown, and then whitewash the M (and themselves). All while singing the fight song over and over very loudly.

For this problem, you must multiply \(m\) (the number of rocks) by \(n\) (the cost of a litre of paint). This gives you the total price of paint for painting the M because each rock requires 1 litre of paint.

 CS@Mines HSPC 2021 Interview with Jack Garner (Contest Organizer and Problem Author)

B - 13 Floors

Descriptionhttps://mines21.kattis.com/problems/mines21.13floors
AuthorColin Siles
Attempts73
Correct55
Percentage100%
Conceptconditionals (if statements)

This problem was intended to be a fairly trivial problem as well. It involves using an if statement to determine if the given number is greater than or equal to 13. If it is, then print the number plus one. If it is not, then print the number.

 CS@Mines HSPC 2021 Interview with Colin Siles (Problem Author)

C - Rolling the Dice

Descriptionhttps://mines21.kattis.com/problems/mines21.rollingthedice
AuthorAdam Sandstedt
Attempts92
Correct53
Percentage96%
Conceptbasic string processing and operations on variables

The math at the core of this problem is fairly easy, however, parsing is slightly non-trivial. The input format is XdY+Z, and you have to extract X, Y, and Z. The easiest way to do this is to split the string by d to get X and Y+Z, and then split the second part by +. Once split, you have to convert all of the strings to integers, and then the solution \(S\) is given by the following equation:

\[ S = \underbrace{ \frac{X + (X \times Y)}{2} }_{ \text{average of $X$ and $X \times Y$} } + \underbrace{Z}_{\text{offset by $Z$}} \]
 CS@Mines HSPC 2021 Interview with Adam Sandstedt (Problem Author)

D - Tall Enough

Descriptionhttps://mines21.kattis.com/problems/mines21.tallenough
AuthorJack Garner
Attempts81
Correct54
Percentage98%
Concepta for loop with a conditional

This problem requires the use of a loop to iterate over all of the numbers in the input. If any of the numbers are less than 48, then False should be printed. If all of the numbers are greater than or equal to 48, then True should be printed.

 CS@Mines HSPC 2021 Interview with Jack Garner (Contest Organizer and Problem Author)

G - Alphabet Soup

Descriptionhttps://mines21.kattis.com/problems/mines21.alphabetsoup
AuthorColin Siles
Attempts99
Correct50
Percentage91%
Conceptloops + a set or list

This problem requires taking a string of characters and verifying that every letter of the alphabet is present in the string, and printing the ones which are not present if there are any missing. There are many ways of accomplishing this, but one easy way is to put the characters of the input string into a set, then perform a set subtraction with a set of all of the upper-case letters. If there are any remaining letters, print them in sorted order. If there are no remaining letters, print Alphabet Soup!.

 CS@Mines HSPC 2021 Interview with Colin Siles (Problem Author)

I - Tic-Tac-Toe Solver

Descriptionhttps://mines21.kattis.com/problems/mines21.tictactoesolver
AuthorJack Garner
Attempts113
Correct44
Percentage80%
Conceptconditionals (if statements)

This problem requires you to determine which player won a tic-tac-toe game. The first challenge is reading the input into a 2-D list or array. Then, once you’ve read in the input, the easiest thing to do is hard-code the 16 win configurations with if statements. If none of the win conditions are met, then nobody has won so you should output N.

 CS@Mines HSPC 2021 Interview with Jack Garner (Contest Organizer and Problem Author)

F - Follow the Prize

Descriptionhttps://mines21.kattis.com/problems/mines21.followtheprize
AuthorColin Siles
Attempts90
Correct50
Percentage91%
Conceptloops

For this problem, you need to keep track of which cup holds the prize in a variable. Then, in a loop, go through all of the swaps in order. If at any point one of the cups being swapped matches your variable, you need to update your variable to refer to the swapped cup.

 CS@Mines HSPC 2021 Interview with Colin Siles (Problem Author)

E - Marble Maze

Descriptionhttps://mines21.kattis.com/problems/mines21.marblemaze
AuthorSam Sartor
Attempts44
Correct26
Percentage47%
Conceptconditionals + loops + 2-D arrays

The key to this problem is to keep a separate bit of state for each seesaw.

Then, move each of the \(N\) marbles step-by-step through the maze according to the rules for each grid square, toggling the seesaw states as needed. Be careful to avoid indexing mistakes, especially along the edges of the grid.

 CS@Mines HSPC 2021 Interview with Sam Sartor (Problem Author)

H - Powering Teslopolis

Descriptionhttps://mines21.kattis.com/problems/mines21.poweringteslopolis
AuthorJohn Henke
Attempts72
Correct29
Percentage53%
Conceptconditionals + loops + 2-D arrays

For this problem, you likely want to use a nested for loop to search every row and column of Teslopolis. For every cell in the grid, you need to check all of the adjacent cells (including diagnols) for a power station. Although there are alternatives, the simplest option is to create an if statement for each neighbor. If any neighbors are power cells, then the cell you’re looking at is powered. It is important not to go out-of-bounds when at an edge.

 CS@Mines HSPC 2021 Interview with John Henke (Problem Author)

J - Quadratic Autopilot

Descriptionhttps://mines21.kattis.com/problems/mines21.quadraticautopilot
AuthorDavid Florness
Attempts60
Correct21
Percentage38%
Conceptoperations on variables

This problem requires solving for \(a\), \(b\), and \(c\) in terms of the input points’ coordinates. The best way to solve this is to take the three equations you are given, and just start substituting until you are able to write one of them in terms of just the coordinates. After much algebra, you will get a solution.

\[ \begin{align*} b &= \frac{ x_1^2(y_2 - y_3) + x_2^2(y_3 - y_1) + x_3^2(y_1 - y_2) }{ (x_2 - x_3)(x_1^2 - x_2^2) - (x_1 - x_2)(x_2^2 - x_3^2) } \\ a &= \frac{y_1 - y_2 - b(x_1 - x_2)}{x_1^2 - x_2^2} \\ c &= y_1 - a{x_1^2} - bx_1 \end{align*} \]

We were unable to get an interview with David.

K - Knight Walk

Descriptionhttps://mines21.kattis.com/problems/mines21.knightwalk
AuthorJohn Henke
Attempts9
Correct8
Percentage15%
ConceptBFS on an implicit graph

For this problem, you can use a breadth first search (BFS) to find the knight’s path. However, unlike a traditional BFS where you are given the full graph to traverse, for this problem, you have an implicit graph.

To do the BFS, first, you can create a queue data structure and place the starting position into it. Then, until the queue is empty, you pop off the front of the queue. You can then look at every position the knight can reach from the position you just popped off and add those to the back of your queue. Then, repeat the process of adding moves to your queue and taking off the move that’s in front. Once you’ve found the square you were looking for, you can stop adding moves to the queue, but it is important to finish processing whatever is still left in the queue so you get all the paths!

 CS@Mines HSPC 2021 Interview with John Henke (Problem Author)

L - Math in Another Universe

Descriptionhttps://mines21.kattis.com/problems/mines21.mathinanotheruniverse
AuthorMohammed Alnasser
Attempts105
Correct26
Percentage47%
Conceptbasic parsing and expression evaluation

This problem is about finding a way to parse a mathematical formula. You can start by splitting the formula on any spaces. You can then search the input for any plus or minus signs. Once you find one, replace it and it’s operands with the result of the operation. When all of the plus and minus signs are gone, you can do the same thing with multiplication and division signs. Once those are gone, you should be left with a single number.

Note

There are ways to cheese this problem by adding parentheses and using your languaguage’s eval functionality, a trick which The Fellowship of the String found and enabled them to solve this problem 34 minutes into the competition.

 CS@Mines HSPC 2021 Interview with Mohammed Alnasser (Problem Author)

M - Delivery Driver

Descriptionhttps://mines21.kattis.com/problems/mines21.deliverydriver
AuthorSumner Evans
Attempts38
Correct10
Percentage18%
Conceptdynamic programming

This problem requires dynamic programming, a technique for optimizing recursive algorithms. There are two main steps to dynamic programming:

  1. Find the recursive formulation.
  2. Determine a strategy for storing previous calls to the recursive formulation so that you don’t have to recompute values over and over again.

The following is a recursive formulation for the problem:

Recursive Formulation

Let \(P(d, c)\) be the maximum profit achievable through the rest of the sequence by working in \(c\) on day \(d\), \(p[d, c]\) be the profit for day \(d\) in city \(c\) from the table, \(T(c_1, c_2)\) be the transition cost from \(c_1\) to \(c_2\), and \(N\) be the number of days. Then,

[

\begin{align*} P(N, c) &= p[N, c] \ P(d, c) &= p[d, c] + \max \begin{cases} P(d + 1, c) \ T(c, c_1) + P(d + 1, c_1) \ T(c, c_2) + P(d + 1, c_2) \end{cases} \end{align*}

]

The key insight from Dynamic Programming is that you can cache the results of \(P\) because \(P\) will need to be evaluated with the same parameters many times. There are two main ways to make this cache:

  1. By creating an \(3 \times N\) table where the cells represent \(P\) evaluated at the corresponding day and city. Then, fill in the table in such a way that the dependencies are always evaluated before they are needed. In the recursive formulation above, the dependencies for \(P(d, c)\) are \(P(d+1, c)\), \(P(d+1, c_1)\), and \(P(d+1, c_2)\).
  2. Via a technique called memoisation which involves creating a dictionary of function inputs to function outputs. Then, at the beginning of the function, check to see if the value has already been computed and is in the dictionary. If it is, then return that, otherwise compute the value, store it in the dictionary, and then return the value.
 CS@Mines HSPC 2021 Interview with Sumner Evans (Problem Author)