Mines High School Programming Competition 2023

Above Sea Level

The solution is to read the input (which is given in meters) as a floating point number, subtract 0.3, and output it.

You need to subtract because as the sea level rises, the elevation of all objects on land decreases.

Driving Dilemma

For this problem, you need to determine if Rishi will travel at least \(D\) feet in \(T\) seconds going at \(S\) miles per hour.

You need to do some unit conversions in order to make this comparison. It is recommended to convert the speed to feet per second.

Then if \(T \times S \geq D\) Rishi "MADE IT" otherwise output "FAILED TEST".

MIR Cipher

For each character, shift it by the shift amount, print it, then double the shift amount. Main gotchas:

• The shift amount will quickly become greater than the length of the alphabet so you will need to wrap around by doing all operations under \(\pmod{26}\).
• You need to use 64-bit integer to store the shift amount!

It is recommended to subtract from the ASCII value of the letters before performing the Cæsar cipher so that A is 0, B is 1, etc. This allows the modular arithmetic work naturally.

Sarah's Sandwich Shop

You need to convert everything to lower case (or upper case), then loop over all of the characters in the string and determine the number corresponding to the letter.

One of the cleanest ways to determine the number corresponding to the letter is by creating a dictionary to store a mapping of letters to numbers.

Alternatively, you can just write 26 switch cases or if statements.

Mines Football

Store the current maximum score, current minimum score, current maximum total month, and current minimum total month (minimum values should be initialized to INT_MAX).

Loop through the scores for each month to sum up the scores for the month. Use that to update the current minimum and maximum total month scores.

Either in the same loop or in a separate loop, iterate through each of the individual scores in the month and update the current maximum and minimum scores.

Cookie Monster Concussion

The problem can be solved by implementing the algorithm provided in the problem statement. It may have been useful to interpret the input as a string of digits rather than an integer to avoid overflow on 32-bit integers.

Note that running the provided algorithm on a number \(C\) is equivalent to computing \(C \mod 9\), except that the algorithm outputs \(9\) if \(C \mod 9 = 0\).

Compass Rose

First, handle the special cases of due north/east/south/west. Then, the easiest way to solve this is by dividing the problem up per-quadrant. You can determine which quadrant of the compass rose you are dealing with looking at the last two characters of the heading.

Once you know the quadrant, the preceding characters (going right to left) add specificity to the heading.

The most intuitive way to think about how each subsequent preceding character adds specificity is in terms of a binary search. Each character "pulls" the bounds towards that cardinal direction.

For example, if you have the heading NE (\(45^{\circ}\)) it can be thought of as the mid-point between \(0^{\circ}\) (N) and \(90^{\circ}\) (E).

If we prepend N to NE to get NNE, we "pull" the bounds towards the north, and we get the mid-point between \(0^{\circ}\) (N) and \(45^{\circ}\) (NE) which is \(22.5^{\circ}\).

There is no great way to do this entirely generically for all four quadrants, and some amount of special-casing per quadrant will be necessary. One special case is the northwest quadrant where you have to use \(360^{\circ}\) as your "north" value rather than \(0^{\circ}\).

Computer Imaging

It's useful to think about this problem as a scheduling problem, where computers are scheduled onto flash drives. The input size for this problem is small enough that a greedy simulation is fast enough.

• Keep track of the total amount of time each flash drive images a computer (initially zero for each drive).

• For each computer we need to image, we determine which flash drive it should be scheduled on.

  We choose the flash drive based by determining which one will minimize the total time. To do this, we iterate over each flash drive and consider the total time if we scheduled the next computer on that flash drive.

  We select the flash drive that resulted in the lowest total time (choosing arbitrarily if multiple options yield the same minimum time), and increment the total amount of time that flash drive images a computer accordingly.

  

• After we complete this procedure for each computer, the maximum amount of time that any flash drive is imaging a computer is the minimum amount of time it would take to image all computers.

  Scheduling any computer on a different flash drive would necessarily increase the total time (or at least leave it unchanged), per the nature of the greedy simulation.

If \(N\) is the number of computers, and \(M\) is the number of flash drives, this solution is \(\mathcal{O}(NM)\). This is fast enough since both \(N\) and \(M\) are less than or equal to \(1\,000\).

The problem can also be solved by doing a linear search of the total time, starting from 0, to determine the smallest time when the required number of computers are imaged. If there are \(M\) flash drives, and the \(i^{\text{th}}\) flash drive takes \(t_i\) seconds to image a computer, then the total number of computers that can be imaged in \(T\) seconds is

Note that there are more efficient solutions, which are required for the more difficult form of this problem.

Fixing Figures

The cleanest approach is to notice that the textual representation of each set of 3-digits is the same, with an added postfix for thousands/millions.

With this insight, you can solve printing for \([0, 999]\) and then use that solution for the hundreds place, the thousands place, and the millions place.

There are some highly annoying edge cases such as numbers from \([0, 19]\) and double-digit numbers with hyphens.

Paper Pile Pandemonium

To solve this problem, simulate the provided sequence of operations on the initial state of the stacks, and then output the final state.

The simulation must keep the sheets in order when they were moved between piles, and not reverse their order.

The size of the inputs is small enough that no special data structures are required: dynamic arrays to represent each stack is sufficient.

Noise Reduction

The bounds of this problem are such that you can just try every group size up to \(N/2 + 1\) and see if the group size works.

In order to determine if a group size \(g\) works, split the dataset into groups of size \(g\) (discarding any extraneous readings) and compute the average of the readings within each group.

Keep track of the previous group's average, and if the difference is above \(T\), then the group size is too small.

Telescope Targeting

To find where the reference image appears in the current view, create 4 nested for loops:

• Over \(M - H + 1\) possible vertical offsets
• Over \(N - W + 1\) possible horizontal offsets
• Over \(H\) rows of pixels in the reference image
• Over \(W\) pixels in the row of the reference image

If all pixels in the reference image equal the pixels in the current view, at the given offset, then the correct offset has been found.

Wikipedia Black Hole

Model the problem as a directed graph with links being the edges and pages being the nodes.

Because you need to output the smallest loop, you must use a breadth-first search (BFS) to find the loop rather than a depth-first search (DFS).

If you explore the entire graph without finding a loop back to the original page, then there is "NO BLACK HOLE".

Unit Rescue

Model the problem as a directed graph with the nodes being units and the edges being a known conversion from the two units. Note that you will always have the reverse edge since you can always invert the ratio.

Then, use BFS or DFS to find a path from the start unit to the end unit. In addition to keeping track of which nodes to visit, you will have to track the converted value (similar to a distance table used in Dijkstra's algorithm).

Planetary Computer Imaging

This is a harder version of the Computer Imaging problem given to the beginner competition. In this version of the problem, the number of computers can be very large (up to \(8 \cdot 10^9\)), so neither the greedy simulation nor the linear search is fast enough.

We can use the same formula from the linear search solution to determine how many computers are imaged in a given amount of time, but use binary search to drastically reduce the number of times we search, compared to linear search.

Since each step of binary search cuts the number of possible candidates in half, we can determine the answer amongst the \(2 \cdot 10^{11}\) possible times in only \(log_2(2 \cdot 10^{11}) \approx 38\) steps!

If we test a time and image more computers than necessary, then we can eliminate all times greater than that value, since all such times must necessarily image at least as many computers.

If we test a time and image fewer computers than necessary, then we can eliminate all times less than that value, since all such times could only possibly image fewer computers.

Basketball Modelling

This problem requires a solution technique called Dynamic Programming, which allows us to efficiently solve problems involving recursion.

Let \(f(n, m_2, m_3)\) be the expected number of points the team scores over \(n\) posessions given that they begin with an \(m_2\) percent chance of making a 2-pointer, and an \(m_3\) percent chance of making a 3-pointer. We define the function recursively.

The first step is to define a recursive definition for the expected value function.

Computing this function with the recursive definition directly is not fast enough. Because all of the inputs to \(f\) are integers, we would repeat a lot of computations. If we "memoize" the results to the function call (that is, cache the answer, and check the cache before computing), we can solve the problem efficiently. This memoization step is what advances us from simple recursion to "Dynamic Programming".

Pegs

Problem Summary

Given the state of a Peg Game, determine the number of pegs that you would end up with after optimal play.

There are three main challenges to solve this problem:

1. Modelling the problem as a graph.

   This problem requires that you model the possible moves from a given position as edges in a directed graph. The nodes of your graph represent a game state.

   By modelling the problem in this way, you can use an exhaustive search (either BFS or DFS work) to find the game state with the smallest number of pegs remaining.

2. Representing the state of the board in a comparable way.

   There are many ways to represent the state of the board, but whichever way you choose, it must be hashable so that you can put it into a "visited" set so you don't get in an infinite loop.

   Options include:

   1. Bitsets: there are only 15 pegs, so you can fit the entire board state in a 32-bit integer (or even a 16-bit one).
   2. Tuples: if your language has tuples (say, Python), you can use tuples of booleans.
   3. Custom class with hash function: you may have to resort to this in languages such as Java.

3. Finding adjacencies to a given hole.

   Finding adjacencies to a given hole is nontrivial due to the triangular nature of the board.

   Given a hole in the \((r, c)\) cell, it is adjacent to the holes at the \((r,c-1)\), \((r,c+1)\), \((r-1,c-1)\), \((r-1,c)\), \((r+1,c)\), and \((r+1,c+1)\).

   There are many other ways to represent hexagonal grids. This website has some good resources about options: https://www.redblobgames.com/grids/hexagons/

Galactic Reconstruction

This problem requires that we efficiently keep track of disjoint subsets of the colonies.

This problem can be solved using the Union Find data structure, but we will go over another solution that does not require as much prerequisite knowledge which involves merging sets of colonies using dictionaries.

We will represent each cluster as a tuple of the set of colonies within it and its wealth. We will also need a list that tracks with cluster each colony is part of. So before we process any propositions, we have these two structures:

cluster: \([(\{1\},w_1),(\{2\},w_2),(\{3\},3),\ldots]\)

lookup: \([1,2,3,\ldots]\)

We now process the propositions in order. If the current proposition is joining \(a\), \(b\) at at a cost of \(c\), we can check lookup[a] and lookup[b] to see which clusters they are part of.

If they already belong to the same cluster then you can just output that the warp gate is UNNECESSARY.

We can then check that each have enough wealth to build the warp gate using clusters[lookup[a]][1] and clusters[lookup[b]][1]. If either has wealth less than \(c\), then it is IMPOSSIBLE.

If both of these checks have passed, we output BUILT and must update our data structures to reflect this change.

To update our data structures, we choose the smaller cluster and move its elements into the larger cluster. Moving a colony to the larger cluster requires that we

1. add the colony to the larger cluster
2. update the lookup table for each of the moved colonies

We must also update the wealth of the larger cluster, which now represents their union, to be the sum of the original wealths minus twice the warp gate cost.

This algorithm is \(\mathcal{O}(n \log n)\). The most expensive part of this algorithm is moving colonies from one cluster to another.

We can derive our complexity by looking at how many times a colony can move from one cluster to another then multiplying that count by the number of colonies (\(n\)).

Since we are always moving a colony into a cluster with a size greater than or equal to the size of the previous cluster, we know that the size of the cluster a colony is part of at least doubles after every move.

Since the size is doubling, we know that there can be at most around \(\log_2(n)\) moves before there is only a single cluster.