# Mines High School Programming Competition 2020

**Posted
on
in
School**
• 2779 words
• 14 minute read

Tags:
High School Programming Competition, Competitive Programming, Mines, HSPC

For the last three years, the Mines Computer Science Department has hosted a High School Programming Competition modelled after the International Collegiate Programming Contest (ICPC). I wrote about last year's competition in this post. This year, although I am no longer a student at Mines, I wrote two of the problems, and I volunteered during the competition.

Due to the current COVID-19 lockdown, the competition was held remotely, which meant that we were unable to enforce a no-internet rule as we are able to during on-site competitions. Luckily, the problems are all unique, and written by Mines students and Mines alum specifically for the competition which makes it very difficult to search the internet for answers.

The competition had a total of 30 teams from all around Colorado. The problems ranged in difficulty from a problem requiring contestants to perform very basic arithmetic, to a problem where the contestants were required to very efficiently store and simulate the state of a problem using a massive array.

In this post, I'm going to give a few highlights of the competition, and then explain the problems in the competition (with relatively detailed solution sketches). Additionally (new this year), I've included YouTube videos explaining how to solve each of the problems with live code demonstrations.

## Competition Highlights

**You can view full standings for the competition at:**
https://mines20.kattis.com/standings

This year's competition was very exciting. All of the contestants at HSPC this year did a great job. Here are a few highlights of the competition:

- All teams solved at least one problem, and all but one team solved two problems.
*Installation Wizards*(1st Place) solved 11 out of the 12 the problems!*Installation Wizards*was the only team to solve problem**G**. They were also the first to solve problems**A**,**B**,**G**,**H**,**I**, and**L**.- Team
*i*(2nd place) solved 8 problems, and were first to solve problem**K**at only 11 minutes into the competition. - There were 9 teams that solved 5 problems, but the
*Sun Devils*won third place on time. They were first to solve problem**E**. - The teams that solved 5 problems solved all of the problems except for
**B**,**D**,**G**, and**J**. - Other teams that were first-to-solve a problem were
*ACJ*(problem**C**),*Lobos*(problem**D**), and*Silver Creek Maroon*(problem**F**).

## The Problems

Warning

The rest of this post should be treated like a solutions manual. I hope that
this is an extremely helpful resource when you get stuck, but you should
*try* to solve each of the problems before reading the solutions. There's no
magic amount of time that you should try to solve the problem before looking
at the written solution sketch or watching one of the videos, but I think a
good rule of thumb is after you've tried at least three ideas on your own,
then you can read at the written solution sketch. Then, try at least three
more ideas before watching the video.

*Remember:* Reading or watching me solve the problems is not the same as
actually going through the work of solving the problems yourself. **You will
not learn anything if you just watch the videos and read the explanations!**

There were twelve problems in the competition written by eight different authors. The problems can be viewed at https://mines20.kattis.com/problems. The following lists each of the problems' names and a short description of the algorithm required to solve the problem, listed in the order in which they appeared in competition:

**A: Flatter Land**-- Basic arithmetic.**B: Broken Clock**-- Combinatorics.**C: CDOT Patfinder**-- Find the locally optimal path over \(n\) segments.**D: Paint Bucket**-- Flood fill algorithm.**E: Encrypted Counting**-- Determine how many iterations of a look-and-say function are required to get from one number to another.**F: Late Lary**-- Time parsing an manipulation.**G: Tax Calc**-- Implement a stack calculator.**H: Work From Home**-- Unit conversions, and arithmetic.**I: Skittles**-- A bunch of non-trivial dictionary operations.**J: Mountain Bike Trail**-- This problem involves efficiently storing and manipulating the state of a non-trivial "world".**K: Snails**-- Modified Fibonacci sequence requiring memoization.**L: Magic Maze**-- Keep track of a set of transformations on a stack.

Problem **A** was designed to be the easiest problem, while **G** was intended
to be the hardest problem. 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. Additionally, a
few of the difficulties were miscalculated by the problem authors, and I will
mention those in each subsection.

I do not try and build up from first principles in each of these explanations (and corresponding videos). 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 each of these problems.

A new addition this year is that each of the problems has an associated YouTube video with a detailed explanation of how to solve the problem as well as a demonstration of how to implement the solution into code.

Note

Some of the problems do not have corresponding YouTube videos yet, I'm working on it, and if you comment below which ones I should prioritize, that will motivate me to actually finish making the videos.

### A - Flatter Land

Description: | https://mines20.kattis.com/problems/mines20.flatterland |
---|---|

Author: | Jack Garner |

Attempts: | 46 |

Correct: | 30 |

Percentage: | 65% (tied for highest in the competition) |

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

Description: | https://mines20.kattis.com/problems/mines20.workfromhome |
---|---|

Author: | Jack Rosenthal |

Attempts: | 132 |

Correct: | 29 |

Percentage: | 22% |

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

Description: | https://mines20.kattis.com/problems/mines20.latelarry |
---|---|

Author: | Jared Lincenberg |

Attempts: | 93 |

Correct: | 10 |

Percentage: | 11% |

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.

Tip

If you don't know what the modulo operator is, I recommend watching my explanation starting at around 11:27 in the video.

### I - Skittles

Description: | https://mines20.kattis.com/problems/mines20.skittles |
---|---|

Author: | Sumner Evans |

Attempts: | 25 |

Correct: | 8 |

Percentage: | 32% |

This problem involves two main steps:

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

Description: | https://mines20.kattis.com/problems/mines20.cdotpathfinder |
---|---|

Author: | Jonathon Robel |

Attempts: | 22 |

Correct: | 13 |

Percentage: | 59% |

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

Description: | https://mines20.kattis.com/problems/mines20.snails |
---|---|

Author: | MachineFossil |

Attempts: | 67 |

Correct: | 5 |

Percentage: | 7% |

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.

Note

If you are using Python, you don't have to worry about integer size, since Python arbitrary-length integers. That means it will automatically expand to the necessary number of bits required to represent your integer.

### J - Mountain Bike Trail

Description: | https://mines20.kattis.com/problems/mines20.mountainbiketrail |
---|---|

Author: | Jack Rosenthal |

Attempts: | 66 |

Correct: | 0 |

Percentage: | 0% |

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

Description: | https://mines20.kattis.com/problems/mines20.magicmaze |
---|---|

Author: | Jack Garner |

Attempts: | 15 |

Correct: | 2 |

Percentage: | 13% |

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

Description: | https://mines20.kattis.com/problems/mines20.encryptedcounting |
---|---|

Author: | Fisher Darling |

Attempts: | 17 |

Correct: | 11 |

Percentage: | 65% (surprisingly tied for highest in competition) |

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

Description: | https://mines20.kattis.com/problems/mines20.paintbucket |
---|---|

Author: | Jack Garner |

Attempts: | 39 |

Correct: | 3 |

Percentage: | 8% |

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

Description: | https://mines20.kattis.com/problems/mines20.brokenclock |
---|---|

Author: | Sumner Evans |

Attempts: | 9 |

Correct: | 2 |

Percentage: | 22% |

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

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

Description: | https://mines20.kattis.com/problems/mines20.taxcalc |
---|---|

Author: | Jordan Newport |

Attempts: | 24 |

Correct: | 1 |

Percentage: | 4% |

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