Mines High School Programming Competition 2024

Parking Pandemonium

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

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

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

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

Greedily [1] use the largest bills possible.

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

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

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

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

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:

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

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

Closing Early

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

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) \% 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

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

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

Solving for $W$, we get:

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

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

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

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

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 [2] - 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

Blake has \(S_i\) shirts of the \(i^{\text{th}}\). He wants to avoid wearing the same color shirt multiple times within the same work week (5-day weeks). How many days can he go before he must wear a shirt color he has already worn that week, or he runs out of shirts?

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.