# Mines High School Programming Competition 2022 Source: https://sumnerevans.com/posts/school/2022-hspc/ Published: 2022-04-09 School, High School Programming Competition, Competitive Programming, Mines, HSPC For the last five years, the Mines Computer Science Department has hosted a High School Programming Competition (HSPC) modelled after the [International Collegiate Programming Contest (ICPC)](https://icpc.global/). I wrote about the [2019](https://sumnerevans.com/posts/school/2019-hspc/), [2020](https://sumnerevans.com/posts/school/2020-hspc/), and [2021](https://sumnerevans.com/posts/school/2021-hspc/) competitions on this blog. This year, I wrote three of the problems and helped [Colin Siles](https://colinsiles.dev) with organizing the competition. For the first time since the 2019 competition, this year's HSPC featured in-person teams. There was also a remote option to increase the reach of the competition. Like the past two competitions, we allowed contestants to access the internet. The problems from every year are new and written by Mines students and some Mines alum specifically for the competition. Also for the first time we ran two concurrent competitions: a beginner competition and an advanced competition. The beginner competition was designed for first-year computer science students, while the advanced competition was designed for computer science students who had more experience. To allow for such a large number of teams, the problem writers created twenty unique problems: the most ever! The beginner competition featured 39 teams while the advanced competition featured 26 teams. The 65 teams came from across the nation and the total count was a ten-team increase over last year resulting the largest CS@Mines HSPC ever. 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). ## Competition Highlights **You can view full standings for each competition at the following websites:** - Beginner: https://mines22beginner.kattis.com/standings - Advanced: https://mines22advanced.kattis.com/standings This year's competition was very exciting. Here are a few highlights from the competition as a whole: - All teams solved a problem. (Though there was one team that dropped out of the competition mid-way through.) - All of the problems in both competitions were solved by at least one team. Highlights from the advanced competition include: - River Hill High School, the reigning champions, were unable to keep their hold on the top spot, but still ended up on the podium in third place with 10 problems solved. - Last year's runners up (PEN Academy) won first place. - The first place (PEN Academy) and second place (Cherry Creek High School) teams both solved 11 out of 13 problems. Cherry Creek High School made a gallant effort in the last hour to equalize solved problems with PEN Academy and were within a single bug fix of solving a 12th problem which would have allowed them to win the competition outright. However, PEN Academy held them off with a late solve of their own, and ended up holding on to first based on time. - The second place _Cherry Creek Cobras_ were the only team to solve Edgar Mine. - The eventual first place winners from PEN Academy also have the honour of first to solve any problem in the competition with their solve of problem A (Blaster's Dash) one minute into the competition. - The honour of being first to solve on a problem stretched all the way down to 13th on the scoreboard with _Cyber Wolves I_ from Grandview High School solving problem K (Toll Booths) 13 minutes into the competition. - Teams from Colorado had a strong showing with Cherry Creek High School (2nd), Regis Jesuit High School (4th), Rocky Mountain High School (6th), and Golden High School (9th) all placing in the top ten. Highlights from the beginner competition include: - Two teams (from _Future Forward at Bollman_ and _Colorado Academy_) solved all of the problems in the beginner competition. - All but five teams solved at least two problems, and all but eight solved three. - The honour of being first to solve a problem stretched all the way down to 25th on the scoreboard with _Keygen Catastrophe_ from Arapahoe High School solving problem A (Blaster's Dash) 3 minutes into the competition. - Teams from Colorado won all four top spots in the beginner competition. ## 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 > solution sketch, 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 solution sketch. > > **Remember: You will not learn anything if you just read the explanations!** There were twenty problems in the competition written by eight different authors. The problems can be viewed at https://mines22beginner.kattis.com/problems and https://mines22advanced.kattis.com/problems. The following lists the problems featured in each competition and a short description of the algorithm required to solve the problem, listed in the order in which they appeared in each respective competition: **Beginner Competition:** - **A: Blaster's Dash** -- Basic arithmetic. - **B: Knight's Move** -- 2-D grid computations with basic bounds checking. - **C: Weather Nodes** -- List processing with a two-pass algorithm. - **D: Toll Booths** -- List processing with a one-pass algorithm. - **E: Hard Rocks and Atomic Clocks** -- Modular arithmetic. - **F: Daniel's Debugging Disaster** -- Basic probability. - **G: Tic-Tac-Toe AI** -- Lots of `if` statements. - **H: Office Hours** -- Use a dictionary or array to store a summary of data, then find the maximum. - **I: 3-Puzzle** -- Determine the number of steps to solve a 3-Puzzle. - **J: Mines Meal Plans** -- More annoying `if` statements. - **K: Premier League Table** -- Summarize a series of data and print a sorted table of information. - **L: CS Building Blueprint** -- Determine the quadrilateral classification of four points in 2-D Cartesian space. **Advanced Competition:** - **A: Blaster's Dash** -- Basic arithmetic. - **B: Babel** -- Flood fill - **C: CS Building Blueprint** -- Determine the quadrilateral classification of four points in 2-D Cartesian space. - **D: Daniel's Debugging Disaster** -- Basic probability. - **E: Edgar Mine** -- Greedy interval covering. - **F: Radioactive Blastervium** -- Principle of Inclusion Exclusion - **G: Office Hours 2** -- Find the two hours in a week that will maximize the total set of students able to attend office hours. - **H: Premier League Table** -- Summarize a series of data and print a sorted table of information. - **I: Crafting Recipes** -- Use a dictionary and recursion to compute a total weight of multiple subcomponents. - **J: Ultimate License Plate** -- Advanced probability - **K: Toll Booths** -- List processing with a one-pass algorithm. - **L: Lost on Campus** -- Dijkstra's, or modified BFS. - **M: Spelling with Chemistry** -- Dynamic programming. As you can see, there were some repeats across the competition. The harder problems in the beginner competition were low and mid-tier questions in the advanced competition. In the beginner competition, the problems were ordered in estimated difficulty. The advanced competition had no such guarantee (except that the first problem would be the most trivial). Problems **E: Edgar Mine** and **J: Ultimate License Plate** were intended to be the most difficult problems in the advanced competition. 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. I do not try and build up from first principles in each of these explanations. 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. ### Blaster's Dash | | | | --------------- | ----------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.blastersdash | | **Author** | Sumner Evans | | **Beginner** | Problem A, 39/53 (74%) solved/tries, 100% solve rate | | **Advanced** | Problem A, 26/28 (93%) solved/tries, 100% solve rate | | **Concept** | basic operations on variables | > [!NOTE] Problem Summary > > This problem is inspired by Mines' mascot: Blaster the Burro. During home > football games, after each Mines touchdown (of which there are many), students > run Blaster onto the field to celebrate. **Calculate how many yards Blaster > has to run.** _Blaster's Dash_ was designed to be a very trivial problem. It involves a few simple math operations. The main difficulty of this problem is figuring out which values you need to discard and how to do input/output. After you identify that you only need the value on the second line (\(n\)), the answer is \(2 \times (20 + n)\). ### Knights Move | | | | --------------- | ---------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.knightsmove | | **Author** | John Henke | | **Beginner** | Problem B, 21/48 (44%) solved/tries, 54% solve rate | | **Concept** | 2-D grid computations with basic bounds checking | > [!NOTE] Problem Summary > > Given the location of a knight on a chess board, **calculate the squares where > a knight could move to.** This problem's difficulty was slightly miscalculated by the problem writer team. It should have probably been the fourth or fifth problem instead. The concept of the problem is fairly simple, but there are a few annoying things that must be considered when solving the problem: 1. You need to parse the algebraic notation. Indexing into the input string to get the file (the letter) and the rank (the number) is sufficient. It is also useful to convert the letter to a number to allow for easier computations. 2. Then you need to calculate all of the knight's moves away from the cell. This can be done using hard-coded offsets. 3. For each of the possible moves, you need to make sure that you don't print board cells that are off of the board. This involved a few `if` statements to check that your rank and file values were within the correct ranges. 4. Lastly, you need to print out the possible squares in the proper order (row-major), from top-left to bottom-right. The order of your checks can be hard-coded. ### Weather Nodes | | | | --------------- | ----------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.weathernodes | | **Author** | Ryan Mapes | | **Beginner** | Problem C, 31/132 (23%) solved/tries, 79% solve rate | | **Concept** | list processing with a two-pass algorithm | > [!NOTE] Problem Summary > > Given a set of temperature readings, **determine how many are over 10 degrees > from the average of all the readings.** This problem requires that you read the input into an array and then make two passes across the it. (It is probably easiest to use a `for` loop for this.) On the **first pass**, you need to calculate the sum of all of the readings (for calculating the average). A counter variable and a `for` loop will suffice, however if your language has a `sum` function, using it will reduce the risk of typos. After the first pass, you can save the average as a variable for the **second pass** where you need to determine how many of the values are too far away from the average. Using your programming language's _absolute value function_ is probably useful here. The problem bounds guarantee that you don't have to worry about floating point precision. ### Toll Booths | | | | --------------- | --------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tollbooths | | **Author** | Joseph Claver | | **Beginner** | Problem D, 22/117 (19%) solved/tries, 56% solve rate | | **Advanced** | Problem K, 25/59 (42%) solved/tries, 96% solve rate | | **Concept** | list processing with a one-pass algorithm | > [!NOTE] Problem Summary > > You are going through a series of toll booths where some of the booths take > money, and some give money. **Determine the minimum amount of BlasterBucks > required in order to pass through all the toll booths in sequence.** This problem requires looping through all of the tolls in the input, keeping track of how much money you have at each toll. The amount you need at the start is the maximum amount of "debt" you accrue after any toll booth. Make sure you initialize this value to 0 so you don't give a negative answer if all booths give you BlasterBucks. ### Hard Rocks and Atomic Clocks | | | | --------------- | ----------------------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.hardrocksandatomicclocks | | **Author** | Ryan Mapes | | **Beginner** | Problem E, 31/56 (55%) solved/tries, 79% solve | | **Concept** | modular arithmetic | > [!NOTE] Problem Summary > > Given the number of seconds since midnight, **how many whole minutes can you > sleep before waking up to reset the drill within one minute of the turn of the > next hour?** This problem requires the use of the **modulo** operator to convert from seconds after midnight to seconds after the current hour. Then, use integer division to calculate the number of minutes after the current hour. Lastly, determine the number of minutes to sleep by subtracting the number of minutes after the current hour from 60. Thus, the final answer is: \[60 - \left\lfloor\frac{S \mod (60 \times 60)}{60}\right\rfloor\] where \(S\) is the number of seconds since midnight. ### Daniel's Debugging Disaster | | | | --------------- | ----------------------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.danielsdebuggingdisaster | | **Author** | Sumner Evans | | **Beginner** | Problem F, 11/14 (79%) solved/tries, 28% solve rate | | **Advanced** | Problem D, 19/28 (68%) solved/tries, 73% solve rate | | **Concept** | basic probability | > [!NOTE] Problem Summary > > Given \(N\) sequential requests, each with a \(K\%\) probability of failing, > and up to \(R\) retries of the entire sequence of requests, **what is the > probability that one of the sequences of** \(N\) **requests succeeds?** This problem can be reduced to finding the probability that at least one of the \(R\) sequences of requests succeeds. **In general, the probability that at least one event from a sequence succeeds is one minus the probability that none succeed.** First, the probability that a single sequence of \(N\) requests succeeds is: \[P_{\text{sequence}} = (1-K)^N.\] Then, the probability that none of the \(R\) sequences succeeds is given by: \[P_{\text{all fail}} = (1 - P_{\text{sequence}})^R.\] And finally the probability that at least one of the \(R\) sequences succeeds is: \[1 - P_{\text{all fail}}.\] ### Tic-Tac-Toe AI | | | | --------------- | ---------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tictactoeai | | **Author** | Sumner Evans | | **Beginner** | Problem G, 16/58 (28%) solved/tries, 41% solve rate | | **Concept** | many annoying conditionals | > [!NOTE] Problem Summary > > Given a tic-tac-toe board and the next player, **provide the winning move.** This problem requires looking at all the possible winning combinations of a tic-tac-toe board (rows, columns, and diagonals) and determining if the player can play a single move to complete said combination by putting their mark on a single empty square. It is necessary to store the board state in a 2-D structure (array of strings, 2-D array of characters, etc.). This problem is small enough that hard-coding is doable (albeit painful), however more clever solutions can check the win conditions using loops. ### Office Hours | | | | --------------- | ---------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.officehours | | **Author** | Ethan Richards | | **Beginner** | Problem H, 5/20 (25%) solved/tries, 13% solve rate | | **Concept** | dictionaries | > [!NOTE] Problem Summary > > Given a list of hours that each student is available, **determine the best > single hour to host office hours during the week.** This problem is probably easiest to solve using a _dictionary_ where the key is the day and time, and the value is the number of students available at that time. Then, iterate over the key-value pairs of the dictionary and determine which pair has the highest value (number of students available at that time). Then, print out the key (day and time). If you didn't know about dictionaries, this problem is also doable using an array (or array of arrays) representing each of the days/hours in a week as well. ### 3-Puzzle | | | | --------------- | ------------------------------------------------------------------------------------ | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.3puzzle | | **Author** | Adam Sandstedt | | **Beginner** | Problem I, 7/18 (39%) solved/tries, 18% solve rate | | **Concept** | sum of Manhattan distances (or BFS) | > [!NOTE] Problem Summary > > Given a 3-puzzle state, **calculate how many moves it would take to solve a > 3-puzzle.** For a 3-puzzle, the optimal number of moves to solve the 3-puzzle is given by the Manhattan distance of each tile to its desired destination. (Note, this doesn't extend to larger versions of the puzzle such as a standard 15-puzzle.) Thus, the simplest solution is to calculate the sum of the Manhattan distances. Alternatively, you can solve this by performing a BFS where each node is a puzzle state, and each neighbor is a state where one tile has been moved. ### Mines Meal Plans | | | | --------------- | ------------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.minesmealplans | | **Author** | Ethan Richards | | **Beginner** | Problem J, 20/61 (33%) solved/tries, 51% solve rate | | **Concept** | a few conditionals (`if` statements) inside a loop | > [!NOTE] Problem Summary > > Given what meal plan a student has, and how many meal swipes they've used, > **determine their options for their next meal.** The solution requires that you use a loop over all of the students, and for each you must determine how many swipes and how much munch money they have left. Then, use a series of conditionals (`if` statements) to determine the corresponding output. ### Office Hours 2 | | | | --------------- | ----------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.officehours2 | | **Author** | Colin Siles | | **Advanced** | Problem G, 3/6 (50%) solved/tries, 12% solve rate | | **Concept** | use a dictionary of sets, and perform \(\mathcal{O}(n^2)\) set unions | > [!NOTE] Problem Summary > > Given the days and times that students are available, **determine the two > times such that the most number of students will be available during at least > one of the times.** To solve this problem, you must consider the number of students that are available in every pair of times. The first step is to store the available students for each time period in a _dictionary of sets_ where the key is the day/time and the value is the number of students. Then, find the union of each pair of day/time sets (using an \(\mathcal{O}(n^2)\) loop). Most programming languages have built-in set union functions. The pair that results in the largest union is the solution. > [!WARNING] > > Note that finding the two times for which the most number of students are > available is not a correct solution! If the same set of students were > available for both of these periods, then a better solution could be found by > using any time period where a different student is available. ### Premier League Table | | | | --------------- | ----------------------------------------------------------------------------------------------- | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.premierleaguetable | | **Author** | Ethan Richards | | **Beginner** | Problem K, 2/5 (40%) solved/tries, 5% solve rate | | **Advanced** | Problem H, 11/25 (44%) solved/tries, 42% solve rate | | **Concept** | use a dictionary and perform some data processing and output formatting | > [!NOTE] Problem Summary > > Given a list of scorelines of soccer games, **print a table showing the > rankings of all of the teams.** The first step is reading the game scorelines to determine the number of points each team has and what their goal differential is (by adding the goals for, minus goals against). The best way to do this is using a _dictionary_ where the key is the team name, and the value is some structure that holds the team's points and goal differential. The best structure to use depends on your language and personal preference, but a tuple, struct, or class (or your language's equivalent) is probably the best option. Once you've calculated the dictionary, you need to use your programming language's _sort_ function with a _custom sort function_ to sort the dictionary key-value pairs. In Java, you can implement the `Comparator` interface. In Python, if you store the values as tuples, the Python `sort` function automatically sorts by the first index, then the second index, etc. Lastly, you have to print the sorted list in the correct format. ### CS Building Blueprint | | | | --------------- | ------------------------------------------------------------------------------------------------ | | **Description** | https://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.csbuildingblueprint | | **Author** | Colin Siles | | **Beginner** | Problem L, 2/8 (25%) solved/tries, 5% solve rate | | **Advanced** | Problem C, 3/33 (9%) solved/tries, 12% solve rate | | **Concept** | trigonometry or linear algebra on a set of points | > [!NOTE] Problem Summary > > Given four (potentially unordered) points in the \(x, y\) Cartesian plane > representing the four vertices of a valid quadrilateral, **determine the > classification of the quadrilateral formed by the points.** There are many ways to solve this problem. Here is one way: 1. Order the points by using trigonometry to determine the angle a line connecting each point to the origin would make with the \(x\)-axis 1. Determine vectors that represent each side of the shape 1. Determine the length of each side of the shape 1. Determine which sides are orthogonal to one another by using the property that the dot product of two orthogonal vectors is 0 1. Determine which sides are parallel to one another by using the property that the cross product of two parallel vectors is 0 1. Use these properties to classify the shape by the provided definitions Most languages have built-in trigonometric functions in their corresponding math libraries. If you don't know any linear algebra, all of the computations can be done using trigonometry. For example, you can calculate and compare the slope of each of the sides of the quadrilateral to determine parallelism (this has the downside of having to deal with vertical lines as a special case). Calculating whether or not an angle is a right angle is possible using pure trigonometry as well. ### Crafting Recipes | | | | --------------- | -------------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.craftingrecipes | | **Author** | Ryan Mapes | | **Advanced** | Problem I, 11/41 (27%) solved/tries, 42% solve rate | | **Concept** | use a dictionary and recursion | > [!NOTE] Problem Summary > > Given the costs of raw materials and recipes for building intermediate > components, **determine the total cost of a "Capstone" contraption.** This problem is solved using _recursion_. The raw materials have known costs and serve as the base cases. In the recursive case, consider all of the components of the part. For each component, multiply the quantity by the cost of the component (calculated recursively). Then, sum the costs to determine the cost of the part. > [!NOTE] > > Memoization was not necessary to solve this problem under the time constraints > as long as your recursive function is reasonably efficient. ### Spelling With Chemistry | | | | --------------- | -------------------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.spellingwithchemistry | | **Author** | Adam Sandstedt | | **Advanced** | Problem M, 4/31 (13%) solved/tries, 15% solve rate | | **Concept** | dynamic programming | > [!NOTE] Problem Summary > > Given a set of element names and a list of words, **determine how many ways > each of the words can be written using the element names.** This problem requires [_dynamic programming_](https://en.wikipedia.org/wiki/Dynamic_programming), a technique for optimizing _recursive_ algorithms. The first step to a dynamic programming problem is to find the recursive formulation for the problem. The following is a recursive formulation for the problem: > [!NOTE] Recursive Formulation > > Let \(P(w)\) be the number of ways that you can spell the string \(w\) with > the given element names and \(E\) be the set of element names. Let \(a - b\) > denote the string \(a\) with the string \(b\) removed from the front. Then, > > \[ \begin{align*} P(\texttt{""}) &= 1 \\ P(w) &= \sum_{n \in E} \begin{cases} > 0 & w\ \text{does not start with}\ n \\ P(w - n) & \text{otherwise} > \end{cases} \end{align*} \] One way to think of the above recursive formulation intuitively is to focus only on what happens at the _start_ of the word \(w\). If the start of \(w\) doesn't correspond to an element name, then there are 0 ways to spell the start of that word with the given element. If the start of \(w\) _does_ correspond to one of the element names, then the number of ways that you can create the rest of the word (without the element name) needs to be added to the count of the ways you can spell the current word. The key insight from dynamic programming is that \(P\) is called many times with the same input, so you can _cache_ (save and not recompute later) the results of \(P\). This can be accomplished via a table or [memoization](https://en.wikipedia.org/wiki/Memoize) (using a dictionary to store the function input to its corresponding output). > [!WARNING] > The output of \(P\) can get _very_ large (larger than the size of a 32-bit > integer). You need to use a `long` to prevent overflow. ### Lost on Campus | | | | --------------- | ----------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.lostoncampus | | **Author** | Joseph Claver | | **Advanced** | Problem L, 3/8 (38%) solved/tries, 12% solve rate | | **Concept** | Dijkstra's shortest path algorithm | > [!NOTE] Problem Summary > > Given a 2D map, **determine the minimum number of doors that must be passed > through to reach an exit.** This problem is solved most easily with Dijkstra's algorithm, which finds the shortest path between two points in a weighted graph. If you solve using Dijkstra's, the graph needs to be modelled where each transition through a cell with a door has a cost of 1, and all other transitions have a cost of 0. Alternatively, you could use BFS/flood fill to convert the map into an unweighted graph where each node represents a "room" (a collection of cells that can be accessed without passing through a door), and all edges represent doors between such rooms. The minimum number of doors can be computed by performing BFS on this graph. ### Babel | | | | --------------- | ---------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.babel | | **Author** | John Henke | | **Advanced** | Problem B, 4/35 (11%) solved/tries, 15% solve rate | | **Concept** | flood fill | > [!NOTE] Problem Summary > > Given a 2D map containing regions, and many pairs of points, **determine if > each pair of points are contained within the same region.** The key difficulty with this problem is that the number of pairs of points that can be given in the problem is large (up to 1,000) and the map is also large (up to 1,000,000). Because of this, _the naive solution of performing a BFS (or any traversal, even an efficient one such as A\*) for each query will not be fast enough._ The queries must be able to be performed in amortized constant time. To accomplish this, you can pre-compute the region that every point is in, and then the query can just check whether the region of the two points is the same. To determine the cells within a region, you can perform a flood fill on the region, marking each cell within the region with an integer "region ID". You can pre-compute all regions, and then each of the queries will be constant time or you can compute the regions only when necessary. ### Edgar Mine | | | | --------------- | -------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.edgarmine | | **Author** | John Henke | | **Advanced** | Problem E, 1/10 (10%) solved/tries, 4% solve rate | | **Concept** | reduce to the _minimum segment cover_ problem | > [!NOTE] Problem Summary > > Given a set of light bulbs, their heights, and brightnesses, **determine the > minimum number of lights that must be turned on to light an entire mine shaft > to a given brightness.** This problem reduces to the _minimum segment cover_ problem which has a \(n \log n\)-time solution. The minimum segment cover problem asks what is the minimum number of segments (closed intervals) required to fully cover an interval (that is, ensure that every point within the interval is within at least one segment). To compute the segments, you must apply the math given in the problem to calculate the span of the mine-shaft floor that the light bulb illuminates to the required level. This requires using the Pythagorean theorem using the maximum distance at which the light is bright enough to satisfy the lighting requirement as the hypotenuse. Once the segments are computed, any efficient solution to the minimum segment cover problem can be used. There is a \(n \log n\)-time greedy solution which is as follows: 1. Sort the list list of the segments 1. Keep track of the leftmost uncovered point (it will start as the entrance of the mine shaft in this problem, 0) 1. Select the segment that extends furthest to the right that covers the leftmost uncovered point. 1. Set the leftmost uncovered point to the rightmost point of the selected segment. 1. Repeat steps 3-4 until the entire interval is covered. ### Radioactive Blastervium | | | | --------------- | --------------------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.radioactiveblastervium | | **Author** | Joseph Claver | | **Advanced** | Problem F, 7/116 (6%) solved/tries, 27% solve rate | | **Concept** | the principle of inclusion-exclusion | > [!NOTE] Problem Summary > > Given a list of intervals for when a particle emits radiation, **determine the > number of unique instances at which radiation is emitted.** For this problem, the naive solution of enumerating the sets and computing their union is too slow, since the interval is too large to enumerate. The problem has a time limit of 1 second, which is realistically enough to do somewhere between \(10^6\) and \(10^7\) iterations (you may be able to push it slightly higher with very efficient loops) but this is still far away from the \(10^{15}\) maximum interval size. This problem can be solved using the [_principle of inclusion-exclusion_](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) which is a way of computing the cardinality of unions of sets _without enumerating the sets_ or when you only are able to compute size and intersection of the sets. In the simplest case, the size of the union of two sets is the sum of the sizes of the sets minus the size of the intersection of the sets (to avoid double-counting items in both sets): \[ |A \cup B| = |A| + |B| - |A \cap B| \] In the case of three sets, you add the size of each set, subtract the size of the intersection of every pair of sets, then add the size of the intersection of all three sets. This pattern can be extended for more than three sets, with the sign alternating for each group of terms. \[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C \] For this problem, each interval has a corresponding set containing all the times it would emit radiation. Then, to compute the above equation: - The cardinality of any given set can be found be dividing the length of the time frame, \(T\), by the interval period. - The cardinality of an intersection of a set of interval periods is the same as the cardinality of a single interval period whose product is the lengths of the original intervals. The next challenge is to compute the combinations for each "level" of the equation. Many languages have utilities to compute combinations of elements (and it's highly recommended that you use such utilities because computing combinations is quite difficult to program). After all of this, the cardinality of the union of all of the interval periods is the number of particles that get emitted. ### Ultimate License Plate | | | | --------------- | ------------------------------------------------------------------------------------------------- | | **Description** | https://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.ultimatelicenseplate | | **Author** | Mohammed Alnasser | | **Advanced** | Problem J, 2/27 (7%) solved/tries, 8% solve rate | | **Concept** | complex combinatorics | > [!NOTE] Problem Summary > Given the maximum number of times certain characters can appear in a license > plate of a given length, **determine the number of unique, valid license > plates.** We can calculate the number of unique license plates with exact counts for certain characters by calculating the number of permutations with repetition. The number of permutations for a total of \(n\) items with \(n_i\) repetitions of the \(i^{\text{th}}\) item is: \[ \frac{n!}{n_1!n_2! ... n_k!} \] Naively, we could thus iterate over every possible combination of the exact number of times characters appear in the license plate, discarding combinations that would contain too many letters, while summing up the number of license plates for combinations that are valid. But this is too slow. This problem requires that you find a clever way to add up the number of possible license plates. For example, instead of discarding combinations that would contain too many characters, you must avoid iterating over them at all. Alternatively, a recursive solution exists to count the number of 1-length license plates, and then build upwards to the complete license plate.