Mines High School Programming Competition 2020

A - Flatter Land

Flatter Land was designed as a very trivial problem. It was inspired by the current COVID-19 crisis where the government is mandating social distancing of 6 feet. For this problem, you are given a 1-dimensional space, and you have to spread out all \(n\) "people" in Flatter Land by exactly \(x\) feet. You are required to determine how far away the two people on either end of the line of people are from each other. The equation for this is \((n - 1) \times x\) because there are \(n - 1\) gaps of size \(x\) between the people on either end of the line.

H - Work From Home

This problem was intended to be a fairly trivial problem as well. It involves performing some very basic unit conversions/dimensional analysis to calculate the total cost of electricity. There is one additional complexity which is that you have to always round up if you have a fractional dollar. You never round down. The best way to do this is to use your language's ceiling function.

F - Late Larry

This problem was intended to be fairly simple as well, however in competition, it ended up being harder than expected. The difficulty of this problem is manipulating time in 12-hour format. There are quite a few annoying edge cases that you have to deal with, especially regrading 12:00 AM/PM. One of the best ways of handling the edge cases is to write a function which converts any given time into minutes after midnight (12:00 AM) and then perform the time-subtraction on the minutes, making sure to modulo the answer to achieve a wraparound. Then, convert the minutes-after-midnight back to a properly formatted time.

I - Skittles

This problem involves two main steps:

1. Determine the number of Skittles of each flavour that are in the bag. This is best done by iterating through the characters in the input string and using a dictionary to store the number of Skittles of each flavour.
2. Determine how many batches of each size can be eaten. One way to do this is to look at the flavour of skittle that would run out first. That is the bound on how many batches of Skittles of a given size Megan can eat. You will probably have to implement a "minimum value greater than zero in the dictionary" function to accomplish this.

C - CDOT Pathfinder

This problem is another problem that involves some dimensional analysis to determine how much time it will take to go on a certain path. Then, you have to minimize the travel time between each city. This will likely require you to use nested for loops. One difficulty is making sure that you correctly pair the distance and average speed values together.

K - Snails

This problem is a modification of the Fibonacci sequence (to help stymie people searching the internet for the sequence). Although the formula is given in the problem as a recursive formulation, if you implement it recursively, it will be too slow due to the high upper bound on the number of elements in the sequence. Instead, you need to either memoize (not a misspelling) the results of your recursive computations, or store the last four elements of the sequence a buffer.

Additionally, you must use a data type that can hold 64-bit integers. Most languages call this data type a long (for "long integer"). If you don't use such a data type, some of the values for the sequence will exceed the size of a 32-bit integer and you will experience integer underflow.

J - Mountain Bike Trail

This problem ended up being the most difficult in the competition with no teams solving it. The main factor that causes this problem to be difficult is having to solve it efficiently. You have to notice that you basically need to "collapse" each group. For example, if you have the sequence:

3 back
2 back
1 back
just me

that can collapse into a single group. However, there may be many other groups that could interrupt this sequence.

The way to solve this efficiently is to store whether or not a person who is "n back" can be included in a group that has been previously seen. For example, if you see a "3 back", then you know that if someone down the trail says "2 back", that person can be part of the same group. You must also consider the fact that there could be multiple groups that can have somebody say "n back" at any given time. If you have a sequence:

3 back
3 back

then the next two people who say "2 back" can be rolled up into the previous groups. However, the third person down the trail who says "2 back" cannot be rolled up into a previous group. You can use an array to store this information efficiently.

L - Magic Maze

This problem is a classic stack problem. Effectively, you have to store dictionaries (mappings) of input direction to actual direction in a stack. Whenever a transformation action is seen, a new mapping of input direction to actual direction is added to the top of the stack. Whenever a move action is seen, you should use the mapping is at the top of the stack to determine what the actual direction to go is. Un-transform actions become trivial in this setup, because you can just remove the top \(n\) elements from the stack.

E - Encrypted Counting

This problem involves implementing a function to iteratively determine the look-and-say representation of a given number. Despite its appearance as a number-oriented problem, this is actually a string processing problem. It is effectively a version of the run-length encoding encoding problem.

The main way of determining the look-and-say representation/RLE encoding of a number is to iterate through the string, storing the current character and how many times that character has been seen. When the character changes, then that data should be appended to the result string, the count and character should be reset, and then continue to iterate through the string.

D - Paint Bucket

This problem requires using a flood fill algorithm to determine which cells to colour in. A flood fill algorithm is similar to a BFS or DFS, but instead of searching for a specific node, you are searching for all nodes (cells) that fulfil a certain property. In this case, that property is that the colour is the same as the start cell. Like a BFS or DFS, the flood fill algorithm requires you to store cells to visit in a stack or queue, and you have to be sure to not re-visit cells.

An additional challenge with this problem is outputting the values in the correct order. This is probably best accomplished using a custom sort function in whatever language you are using.

B - Broken Clock

This problem has two primary sub-problems: the first thing that you need to figure out is what digits may be displayed in each spot in the clock, then you need to enumerate the possible times in-order. There are many ways to accomplish each of these problems, but I'll present one of the more elegant (in my opinion) ways (although, it may not necessarily by the fastest).

1. Use set unions and intersections to determine what the possible numbers for each digit are.

   Associate each of the segment numbers with the set of numbers that must have that segment lit, and a set of numbers that must not have that segment lit. For example, Segment 1 must be lit for 0, 2, 3, 5, 6, 7, 8, and 9, but it cannot be lit for 1 or 4.

   If an segment is illuminated, then all of the numbers associated with that segment could be possible. You can use set intersections to determine this. If a segment is definitely not illuminated (not broken, and not lit), then none of the numbers where that segment is not lit can be included. You can determine this using set subtraction.

2. Use recursion to generate possible times in-order. In this solution, the recursion would return a sorted list of possibilities of the rest of the time string and the base-case would be a list of the possibilities for the right-most digit.

   You still have to filter out "impossible" times such as 25:00:00, but that is relatively easy once you've actually enumerated the possible times.

One catch with this problem is that there are a few interesting edge cases in determining whether or not the time is valid, particularly with the one's place of the hours section.

G - Tax Calc

This problem is a simplified stack calculator. It's simplified because the input input for this problem is given in a very easily parsable manner and the stack is only ever one deep.

All of the tokens in the input (parentheses, numbers, operators, etc.) are separated by spaces. Whenever you see a ( token, you are guaranteed that the next token will be an operator. That will determine what you need to do with the rest of the numbers until the ) token. That means that each set of parentheses defines a new context where the operator is applied to all of the operands and you may have nested contexts, where the result of an inner context gets plugged back in to an outer context.

This is a classic stack problem, since, once you've computed the result of an inner computation, you only care about the result of the inner computation, and you can simplify that entire context into a single value.

This problem can be solved using an explicit stack, or using an implicit stack using recursion.