Jonathan Sumner Evans
Sumner Evans
Software Engineer at Automattic working on Beeper

Mines High School Programming Competition 2022

Written by Human, Not by AI

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). I wrote about the 2019, 2020, and 2021 competitions on this blog. This year, I wrote three of the problems and helped Colin Siles 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:

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.blastersdash
AuthorSumner Evans
BeginnerProblem A, 39/53 (74%) solved/tries, 100% solve rate
AdvancedProblem A, 26/28 (93%) solved/tries, 100% solve rate
Conceptbasic operations on variables

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.knightsmove
AuthorJohn Henke
BeginnerProblem B, 21/48 (44%) solved/tries, 54% solve rate
Concept2-D grid computations with basic bounds checking

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.weathernodes
AuthorRyan Mapes
BeginnerProblem C, 31/132 (23%) solved/tries, 79% solve rate
Conceptlist processing with a two-pass algorithm

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tollbooths
AuthorJoseph Claver
BeginnerProblem D, 22/117 (19%) solved/tries, 56% solve rate
AdvancedProblem K, 25/59 (42%) solved/tries, 96% solve rate
Conceptlist processing with a one-pass algorithm

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.hardrocksandatomicclocks
AuthorRyan Mapes
BeginnerProblem E, 31/56 (55%) solved/tries, 79% solve
Conceptmodular arithmetic

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.danielsdebuggingdisaster
AuthorSumner Evans
BeginnerProblem F, 11/14 (79%) solved/tries, 28% solve rate
AdvancedProblem D, 19/28 (68%) solved/tries, 73% solve rate
Conceptbasic probability

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.tictactoeai
AuthorSumner Evans
BeginnerProblem G, 16/58 (28%) solved/tries, 41% solve rate
Conceptmany annoying conditionals

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.officehours
AuthorEthan Richards
BeginnerProblem H, 5/20 (25%) solved/tries, 13% solve rate
Conceptdictionaries

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.3puzzle
AuthorAdam Sandstedt
BeginnerProblem I, 7/18 (39%) solved/tries, 18% solve rate
Conceptsum of Manhattan distances (or BFS)

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.minesmealplans
AuthorEthan Richards
BeginnerProblem J, 20/61 (33%) solved/tries, 51% solve rate
Concepta few conditionals (if statements) inside a loop

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.officehours2
AuthorColin Siles
AdvancedProblem G, 3/6 (50%) solved/tries, 12% solve rate
Conceptuse a dictionary of sets, and perform \(\mathcal{O}(n^2)\) set unions

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.premierleaguetable
AuthorEthan Richards
BeginnerProblem K, 2/5 (40%) solved/tries, 5% solve rate
AdvancedProblem H, 11/25 (44%) solved/tries, 42% solve rate
Conceptuse a dictionary and perform some data processing and output formatting

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

Descriptionhttps://mines22beginner.kattis.com/contests/mines22beginner/problems/mines22.csbuildingblueprint
AuthorColin Siles
BeginnerProblem L, 2/8 (25%) solved/tries, 5% solve rate
AdvancedProblem C, 3/33 (9%) solved/tries, 12% solve rate
Concepttrigonometry or linear algebra on a set of points

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
  2. Determine vectors that represent each side of the shape
  3. Determine the length of each side of the shape
  4. Determine which sides are orthogonal to one another by using the property that the dot product of two orthogonal vectors is 0
  5. Determine which sides are parallel to one another by using the property that the cross product of two parallel vectors is 0
  6. 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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.craftingrecipes
AuthorRyan Mapes
AdvancedProblem I, 11/41 (27%) solved/tries, 42% solve rate
Conceptuse a dictionary and recursion

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.spellingwithchemistry
AuthorAdam Sandstedt
AdvancedProblem M, 4/31 (13%) solved/tries, 15% solve rate
Conceptdynamic programming

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, 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:

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.lostoncampus
AuthorJoseph Claver
AdvancedProblem L, 3/8 (38%) solved/tries, 12% solve rate
ConceptDijkstra’s shortest path algorithm

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.babel
AuthorJohn Henke
AdvancedProblem B, 4/35 (11%) solved/tries, 15% solve rate
Conceptflood fill

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.edgarmine
AuthorJohn Henke
AdvancedProblem E, 1/10 (10%) solved/tries, 4% solve rate
Conceptreduce to the minimum segment cover problem

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
  2. Keep track of the leftmost uncovered point (it will start as the entrance of the mine shaft in this problem, 0)
  3. Select the segment that extends furthest to the right that covers the leftmost uncovered point.
  4. Set the leftmost uncovered point to the rightmost point of the selected segment.
  5. Repeat steps 3-4 until the entire interval is covered.

Radioactive Blastervium

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.radioactiveblastervium
AuthorJoseph Claver
AdvancedProblem F, 7/116 (6%) solved/tries, 27% solve rate
Conceptthe principle of inclusion-exclusion

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

Descriptionhttps://mines22advanced.kattis.com/contests/mines22advanced/problems/mines22.ultimatelicenseplate
AuthorMohammed Alnasser
AdvancedProblem J, 2/27 (7%) solved/tries, 8% solve rate
Conceptcomplex combinatorics

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.