# Mines High School Programming Competition 2020 Source: https://sumnerevans.com/posts/school/2020-hspc/ Published: 2020-04-25 School, 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)](https://icpc.global/). I wrote about last year's competition in [this post](https://sumnerevans.com/posts/school/2019-hspc/). 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.
Mines HSPC 2020 Problem A: Flatter Land Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=WnW_XFnU3KM)
### 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.
Mines HSPC 2020 Problem H: Work From Home Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=Otau4U8M6Kk)
### 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](https://youtu.be/z6uFZfZ5GWI?t=687) in > the video.
Mines HSPC 2020 Problem F: Late Larry Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=z6uFZfZ5GWI)
### 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: 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.
Mines HSPC 2020 Problem I: Skittles Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=nscAF6-Q-Mo)
### 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.
Mines HSPC 2020 Problem C: CDOT Pathfinder Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=lTcAA0ohT_g)
### 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_](https://en.wikipedia.org/wiki/Memoization) (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.
Mines HSPC 2020 Problem K: Snails Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=qt4L7XYMEqY)
### 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_](https://en.wikipedia.org/wiki/Look-and-say_sequence) 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_](https://en.wikipedia.org/wiki/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_](https://en.wikipedia.org/wiki/Flood_fill) algorithm to determine which cells to colour in. A flood fill algorithm is similar to a [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) or [DFS](https://en.wikipedia.org/wiki/Depth-first_search), 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.
Mines HSPC 2020 Problem D: Paint Bucket Solution and Explanation [Watch on YouTube](https://www.youtube.com/watch?v=VOOLq6ed0wI)
### 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). 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 | | | | --------------- | --------------------------------------------------- | | **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_.