Mines High School Programming Competition 2024

For the last seven years, Mines ACM has hosted a High School Programming Competition (HSPC) modelled after the International Collegiate Programming Contest (ICPC). I wrote about the 2019, 2020, 2021, 2022, and 2023 competitions on this blog. The problems from every year are new and written by Mines students and some Mines alum specifically for the competition. This year, I wrote two of the problems and helped Ethan Richards with organizing the competition.

This year, we returned to an in-person only competition, however we opened up an open division to remote competitors. We also continued our open-internet policy which allowed students to access internet resources.

New this year, we decided to give special awards for teams consisting of exclusively first-time competitors.

We had sixteen different problems written by eleven authors (the highest number of authors ever).

The in-person competition featured 27 teams which is lower than some previous years, but still a great turnout. We expected more, but it turned out some had signed up for the in-person competition when they wished to compete in the open division.

In this post, I’m going to explain the problems in the competition (with relatively detailed solution sketches).

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

• In-Person: https://mines-hspc.kattis.com/contests/mines-hspc24
• Open: https://mines-hspc.kattis.com/contests/mines-hspc24-open

The Problems

There were sixteen problems in the competition written by eleven different authors (the most ever). The problems can be viewed at https://mines-hspc.kattis.com/contests/mines-hspc24/problems. The following lists the problems featured in the competition and a short description of the algorithm required to solve the problem, listed in the order in which they appeared in competition:

• A: Parking Pandemonium – Basic arithmetic.
• B: Closing Early – Modular arithmetic in a for loop.
• C: Clock Catchup – Modular arithmetic related to time.
• D: New Professor – Priority-queue or repeatedly sorted list processing.
• E: Exact Change – Modular arithmetic.
• F: Win Streak – List processing.
• G: Winning Wagers – Expected value.
• H: Warehouse Stocking – Dictionary and reverse-lookup dictionary.
• I: Trolley Troubles – 0-1 BFS or Dijkstra’s.
• J: M-Climb Road – Basic arithmetic.
• K: Purchasing Perishables – Finding optimal sequential-window size in a list.
• L: Abby’s Absolutes – Inequality check in a for loop.
• M: Mines Motor Company – Manhattan distances in a for loop.
• N: No Stragglers – Keep track of single variable state in a for loop.
• O: QWERTY – Cipher based
• P: Procrastination –

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 many of these problems.

Parking Pandemonium

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/parkingpandemonium
Author	Sumner Evans
In Competition	Problem A, 27/49 (55%) solved/tries, 100% solve rate
Concept	basic operations on variables

The solution is to read the first and third lines of input and multiply them. The only difficult thing here is ignoring the second line of input which is the temperature of the parking lot in Kelvin.

M-Climb Road

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/mclimbroad
Author	Ethan Richards
In Competition	Problem J, 26/26 (100%) solved/tries, 96% solve rate
Concept	unit conversion + basic math

Output \(\left\lfloor\frac{5280 W}{N}\right\rfloor\).

The notation \(\left\lfloor x\right\rfloor\) means round down. This can be accomplished by doing integer division in most languages.

Abby’s Absolutes

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/abbysabsolutes
Author	Levi Sprung
In Competition	Problem L, 21/40 (52%) solved/tries, 78% solve rate
Concept	conditional within a loop

Loop over each of the trips. During the \(i^{\text{th}}\) trip, if \(A_i-1 \leq N-A_i\), then Abby will buy 1 apple, so print 1. Otherwise, she will buy \(N\) apples, so print \(N\).

QWERTY

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/qwerty
Author	Byron Sharman
In Competition	Problem O, 23/29 (79%) solved/tries, 85% solve rate
Concept	string transformation

Create a map/dictionary to translate from each character typed using the ABCDEF keyboard, to what it would be on a QWERTY keyboard. Build a new string by passing each character through this map.

An alternative way to solve the problem is to create a string with the QWERTY keyboard sequence. Then, for every character in the input, determine its index in the normal alphabet (this can be accomplished by subtracting the ASCII value for 'a' from the ASCII value of the letter). Use that index to index into the QWERTY sequence string and print that character.

Exact Change

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/exactchange
Author	Jayden Pahukula
In Competition	Problem E, 25/31 (81%) solved/tries, 93% solve rate
Concept	modulo math (or repeated subtraction)

The problem requires you to use a greedy approach that uses the largest bills possible first. A greedy approach means that you should make the locally optimal decision without considering whether it’s globally optimal.

The number of 150 dollar bills is \(\left\lfloor\frac{N}{150}\right\rfloor\), and update \(N \leftarrow N - 150 \times \left\lfloor\frac{N}{150}\right\rfloor\).

Repeat until you get down to the 1 dollar bills, and output your answer.

Win Streak

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/winstreak
Author	Sumner Evans
In Competition	Problem F, 20/53 (38%) solved/tries, 74% solve rate
Concept	track longest contiguous sequence within a list

You need variables to keep track of the current win streak length and the maximum win streak length. Then, for each game:

• If your team wins, increment the current win streak by 1.

• If your team ties or loses, check if the current win streak is longer than the maximum win streak. If it is, set the maximum win streak to the current win streak.

  Then, reset the current win streak to 0.

Clock Catchup

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/clockcatchup
Author	Ethan Richards
In Competition	Problem C, 20/53 (38%) solved/tries, 74% solve rate
Concept	clock math

Let \(H_s, M_s, S_s\) and \(H_e, M_e, S_e\) be the hour, minute, and second of the start time and end time, respectively.

The hour hand cross once if \(H_s < 12 \leq H_e\), otherwise it does not cross at all.

The minute hand crosses \(H_e-H_s\) times.

The second hand crosses \(60 \times (H_e - H_s) + (M_e - M_s)\) times.

No Stragglers

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/nostragglers
Author	Keenan Schott
In Competition	Problem N, 22/25 (88%) solved/tries, 81% solve rate
Concept	track a single variable in a loop

Notice that the distinction between students, faculty, and visitors is irrelevant to the problem and can be ignored.

Initialize some variable to 0 that will be used to track how many people are currently in Mines Market. Now process the logs sequentially, for IN events, add to the total, and for OUT events, subtract from the total.

If at the end the total is 0, output NO STRAGGLERS otherwise output the total.

Purchasing Perishables

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/purchasingperishables
Author	Nathan George
In Competition	Problem K, 6/53 (11%) solved/tries, 22% solve rate
Concept	determining the optimal step-length within an array

The solution is to try each potential purchasing interval from 1 to \(N\) days and compute the cost of meals for that interval. If the interval is \(k\) days, then the cost can be expressed as:

\[ \sum_{i = 0}^{\left\lceil \frac{N}{k} \right\rceil - 1} p_{i \cdot k + 1} \cdot \min(k, N-i \cdot k) \]

But \(N\) can be as large as \(10^5\). Is this fast enough?

Yes, for each interval length \(k\), we can compute its cost in \(\mathcal{O}\left(\frac{N}{k}\right)\) time. Then, the total time to compute the cost over all intervals is

\[ \sum_{k = 1}^{N} \frac{N}{k} \]

We can show that this runs in \(\mathcal{O}\left(N \log (N)\right)\) with the following comparison:

\[ \sum_{k = 1}^{N} \frac{N}{k} \approx \int_{1}^{N} \frac{N}{x} dx = N \ln(N) \]

Closing Early

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/closingearly
Author	Kelly Dance
In Competition	Problem B, 11/84 (13%) solved/tries, 41% solve rate
Concept	modular arithmetic in a loop

We want to find the first \(k \geq 0\) where \(A_1 + A_2 + ... + A_k = R + fS\) for some other integer \(f\) representing the number of full pizzas cooked. To do this we consider both sides of this equation modulo \(S\):

\[ (A_1 + A_2 + \dots + A_k) \mod S = R. \]

To find \(k\) we can maintain a running total \(T\). Now, we can loop over the customers until \(T = R\). With each customer we update \(T \leftarrow (T + A_i) \mod S\).

Be careful about the \(k=0\) case, or the case when there is no such \(k\).

This solution runs in \(\mathcal{O}(n)\) time. \(\mathcal{O}\left(n^2\right)\) solutions are too slow.

Winning Wagers

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/winningwagers
Author	Umberto Gherardi
In Competition	Problem G, 14/45 (31%) solved/tries, 51% solve rate
Concept	expected value

Let \(T_i\) be the number of possible outcomes for the \(i^{\text{th}}\) event. The probability of correctly predicting all \(N\) events is:

\[ \frac{1}{D} = \prod_{i=1}^{N} \frac{1}{T_i}. \]

Note that since all \(T_i\) are integers, \(D\) is also an integer. Then set the expected value of the wager to \(0\):

\[ \frac{1}{D} \times W - \left(1 - \frac{1}{D}\right) \times L = 0. \]

Solving for \(W\), we get:

\[ \begin{align*} \frac{1}{D} \times W - \left(1 - \frac{1}{D}\right) \times L & = 0 \\ \frac{1}{D} \times W & = \left(1 - \frac{1}{D}\right) \times L \\ W & = D \times \left(1 - \frac{1}{D}\right) \times L \\ W & = (D - 1) \times L. \end{align*} \]

Importantly, this calculation does not require any division. No floating point math necessary.

If you attempted to use an equation that included division, you would likely have run into precision issues with your calculations.

Warehouse Stocking

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/warehousestocking
Author	Ethan Richards
In Competition	Problem H, 7/61 (11%) solved/tries, 26% solve rate
Concept	multiple dictionaries

The key here is to have two dictionaries: one to store a mapping of locations to the item they contain \((L)\), and another to store a mapping of items to a list of the locations in which that item can be found \((T)\).

Then, it’s a matter of accounting for the state updates caused by each operation.

• For each of the PUT operations, update \(L[\texttt{loc}] \leftarrow \texttt{item}\) and \(T[\texttt{item}] \leftarrow \text{append } \texttt{loc} \text{ to } T[\texttt{item}]\).

• For each of the TAKE operations, update \(T[L[\texttt{loc}]] \leftarrow \text{remove } \texttt{loc} \text{ from } T[L[\texttt{loc}]]\) and set \(L[\texttt{loc}] \leftarrow \text{nil}\).

• For each of the FIND operations, if \(T[\texttt{item}]\) exists, sort and output it. If it does not exist, output NOT FOUND.

Procrastination

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/procrastination
Author	Ethan Richards
In Competition	Problem P, 13/39 (33%) solved/tries, 48% solve rate
Concept	greedly simulation

Sort the tasks by increasing \(T_i\) and break ties with decreasing \(G_i\). This can be done using a built in sorting algorithm on pairs/tuples if \(G_i\) is placed second in the tuple and negated.

Initialize \(F=0\) to track his total grade. Now loop over the tasks with this new order as long as \(M \geq T_i\). For each task update \(M \leftarrow M - T_i\) and \(F \leftarrow F + G_i\).

Output the final grade \(F\).

Note: the reason we did not ask for the optimal set of tasks to preform to optimize the grade is because that is an NP-complete problem which means that it’s provably a hard problem.

Mines Motor Company

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/minesmotorcompany
Author	Meta Saka
In Competition	Problem M, 19/19 (100%) solved/tries, 70% solve rate
Concept	Manhattan distance in a loop

Loop over locations starting from the second location (since the first is the starting location).

Now we want to add up the distance between successive pairs of locations. Convert the characters for the X direction of each location to a number 1-26 (or ASCII), then take the absolute value of their difference and add this to the total distance. Repeat for the Y direction.

Trolley Troubles

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/trolleytroubles
Author	Jonathon Robel
In Competition	Problem I, 0/14 (0%) solved/tries, 0% solve rate
Concept	0-1 BFS or Dijkstra’s on a non-trivial graph

This is a graph modelling problem. We want to construct a graph such that finding the shortest path provides us with a path through the tracks that minimizes the number of cracks crossed.

• Nodes are track segments (\(N \times L\) total) labeled \((t,s)\) where \(t\) is the track number and \(s\) is the segment number.
• Edges are decisions we can make at each track segment (move forward or switch tracks)
• Edge Weights are the number of cracks crossed to go to the next track segment (0 if no crack or 1 if there is)

For each node \((t, s)\), create the following edges depending on the segment type of \((t, s)\):

• = pieces - create an edge to \((t, s+1)\) with weight 0.
• H pieces - create an edge to \((t, s+1)\) with weight 1.
• ^ pieces - create an edge to \((t, s+1)\) and an edge to \((t-1, s)\) both with weight 0.
• v pieces - create an edge to \((t, s+1)\) and an edge to \((t+1, s)\) both with weight 0.

It may be helpful to create a singular finish node that all \((t, L)\) nodes have a zero-cost edge to. This allows you to find the shortest path to a single node.

Now, we need to actually find a path through the graph from \((k,0)\) to the finish node. There are a couple ways to do this:

• Dijkstra’s Algorithm - This algorithm uses a priority queue to visit nodes in a uniform manner radiating from the start node.

• 0-1 BFS - This algorithm performs a normal BFS with the following modifications:

  • Use a deque (double-ended queue) instead of a queue.
  • If the edge has weight 1 enqueue to the back of the deque, if the edge has weight 0 enqueue to the front of the deque.
  • When updating the distance matrix, use the edge weight rather than hard-coding 1.

In both algorithms, you need to track the node from which each node is discovered, then perform a traceback from the finish node to construct the path.

If the parent of a node \((t, s)\) is \((t-1, s)\), then the path will include \(s\texttt{d}\) indicating a downward switch at column \(s\). The parent has a lower track number than its child, meaning that it is above the child node.

Conversely, if the parent of a node \((t, s)\) is \((t+1, s)\), then the path will include \(s\texttt{u}\) indicating an upward switch at column \(s\).

You will have to perform the traceback starting from the finish node, and output in the reversed order.

New Professor

Description	https://mines-hspc.kattis.com/contests/mines-hspc24/problems/newprofessor
Author	Mete Saka
In Competition	Problem D, 9/38 (24%) solved/tries, 33% solve rate
Concept	priority queue or repeated sorting of an array

We will simulate choosing which color shirts to wear each week. When choosing the colors for a week, we will pick the 5 colors that have the most shirts remaining. Remember to update the number of remaining shirts of these colors.

When there are \(k < 5\) distinct shirt color remaining, we can go exactly \(k\) more days before finally repeating our self or running out of shirts.

This approach can be made to run in \(\mathcal{O}(CM\log(C))\) where \(M\) is the maximum number of any shirt color and \(C\) is the number of shirt colors by utilizing a priority queue, but we set the bounds low enough that repeatedly sorting the shirt color frequency list would still be fast enough \((\mathcal{O}(C^2M\log(C)))\) assuming an \(\mathcal{O}(n \log n)\) sorting algorithm is used.