Mines High School Programming Competition 2021

A - M-Climb

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.

B - 13 Floors

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.

C - Rolling the Dice

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:

D - Tall Enough

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.

G - Alphabet Soup

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!.

I - Tic-Tac-Toe Solver

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.

F - Follow the Prize

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.

E - Marble Maze

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.

H - Powering Teslopolis

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.

J - Quadratic Autopilot

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.

We were unable to get an interview with David.

K - Knight Walk

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!

L - Math in Another Universe

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.

M - Delivery Driver

This problem requires dynamic programming [1], 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:

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, c1)\), and \(P(d+1, c2)\).
2. Via a technique called memoisation [2] 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.