Mines High School Programming Competition 2019

H - Hackaholics

Hackaholics was designed as a very trivial problem. You are given three numbers, and you have to output the product of two of them. The only real difficulty with this problem is understanding the problem description enough to know which numbers you care about and need to multiply, and which one you can discard.

B - Number Reduction

The objective of this problem is to determine the number of steps required to perform the Collatz Conjecture. The Collatz Conjecture is that for every positive integer, if you apply the following function to the number iteratively, you will eventually arrive at 1.

Another way to state the above function is "if \(x\) is even, divide by two, if \(x\) is odd, multiply by 3 and add 1". You can read more about the Collatz Conjecture at this Wikipedia article.

To solve the actual problem, you can just keep applying the above function on the input until you get 1, keeping track of how many steps it takes. Then, output the number of steps.

F - Ski Traffic

This problem requires you to read in the time, day, whether the weather is bad, whether it snowed, and whether it is a holiday. Then you have to multiply the time by the factors specified in the problem, depending on the values of the variables you read in.

The difficulty of this problem comes from a few sources. First, you have to carefully read the description to make sure you understand how each of the factors affect the time. Second, you have to handle time correctly. The easiest way to handle time is convert it to minutes before performing the multiplications. Then, convert back to the H:MM format when outputting the time it will take to reach the ski hill.

J - Rent Division

This problem was intended to be one of the easier problems in the competition, but it turned out to be much harder than expected (as you can see from the success percentage). I think a lot of teams attempted to implement this by looping and incrementing what each roommate paid until the rent and other expenses were covered. This, is probably doable, but it is really annoying to keep track of, and may (if done inefficiently) fail with time limit exceeded (TLE).

To solve this problem without pulling your hair out, you need to notice that the roommates collectively must pay \(R + \sum_i{e_i}\) dollars worth of expenses, where \(R\) is the rent for the month, and \(e_i\) is the amount that person \(i\) has spent on non-rent expenses. Thus, each roommate must pay a total of

worth of expenses that month. If any \(e_i > S\) (meaning that the roommate has paid more than his fair share of the expenses) then you need to output "not possible". Otherwise, roommate \(i\) must pay \(S - e_i\) worth of the rent to even out his contribution to the total expenses for the month.

D - Darts for Programmers

This problem was probably the weakest problem in the entire set as far as quality. The problem description was very precise, but it was quite difficult to parse the problem description, and if you misunderstood or misread even a small part of the problem description, you could easily make an incorrect assumption. This problem was intended to be on the easier side of the middle-of-the-pack difficulty problems, but it ended up being slightly harder than intended and I think that the weakness of the description contributed to that.

To solve the problem, you need to keep track of the wedge numbers in an array. You can use this to calculate the sums of the wedge numbers between the darts on the dartboard. The key here is that you will have to circularly wrap around the array (one easy way of doing that is to modulo by the number of wedges (20) whenever you increment as you are going through the array). Another thing you have to be aware of is the fact that you may need to sort the wedge numbers by their order around the dartboard. Once you have done that, your answer is simply the maximal sum.

A - Alliteration

This problem was intended to be basically at the mid-point as far as problem difficulty, and given the actual competition data, that was what happened.

To solve this problem, for each line of the input, you must

1. Iterate through each of the words on the line (using your language's string splitting function is advisable for this).
2. Use of a dictionary, or similar data structure, to count how many times each letter appears at the start of a word.
3. Output the letter that appears at the start of the most words on that line. This requires knowing how to do a maximization on the value of a dictionary which can be done either via a for loop or your language's built-in max function and an appropriate comparison function.

C - Classrooms an Calculators

Despite its actual difficulty in competition, this was not intended to be one of the hardest problems in the competition. I think that the description and sample inputs made it very appealing to attempt with a brute force solution by iterating through the days checking each one for whether or not they can play on a that day. However, that is where the difficulty of this problem was hidden. The bounds on the problem are so large that it is not possible to do that approach. Rather, this requires you to derive a mathematical formulation for solving the problem under the time limit.

The key observation you must make for this problem is that the pattern of availability will repeat itself after a certain amount of days. You can calculate the precise number of days that will be required for the pattern to repeat (it's the least-common multiple (LCM) of \(d_1, d_2, d_3\)), but it is actually not necessary to compute the LCM for this problem. Instead, you can just observe that the pattern is guaranteed to repeat at least every \(\prod d_i = d_1 \times d_2 \times d_3\) days because \(\prod d_i\) is guaranteed to be a multiple of \(\text{LCM}(d_1, d_2, d_3)\) (proof of this is left to the reader). We call this product the period.

You then need to extend the pattern for the first \(\prod d_i\) days forward until you find the \(n^\text{th}\) day they can play. An important detail here is that there are going to be some number of full repeats of the pattern, call them full periods (it could be 0), and then one partial repeat of the pattern: the partial period. Thus, we can use math to calculate the number of days taken up by all the full periods and add that to the number of days that we need to go into the partial period. Stated mathematically, you can use the following formula to perform the extension process:

where \(A\) is an array of the day numbers which the friends can play in the first \(\prod d_i\) days, and \(|A|\) denotes the length of \(A\). One way to break the formula down for easier comprehension is as follows:

• 1: the number of full periods required before getting to the \(n^\text{th}\) day.
• 2: the number of days per period.
• 3: the number of days that the friends have to play in the partial period.
• 4: the number of days into the partial period that the friends have to go before arriving at the \(n^\text{th}\) day.

I - Sudoku Verify

The premise of this problem is extremely simple: determine whether or not the solution to a sudoku puzzle is valid.

The main difficulty of this problem comes from having to manipulate data structures. It is critical that you read the input into a good data structure (a 2D array is probably one of the best data structures to use). Then, you need to determine whether or not every row, column, and region is valid. This is difficult because you first have to get all of the numbers in that row, column, or region in a data structure that is easy to use. One option is to put all of the numbers in the row/column/region into a set, and subtract that set from a base set: \(\{1, 2,\ldots,9\}\). If there are any leftovers after the subtraction, then the puzzle solution is invalid (there was a duplicate somewhere in that row, column, or region).

E - Tree Skiing

This problem was intentionally written such that you could implement it in basically any way that will give a correct answer, and it will basically never give you a TLE. Two solutions which will work for this problem are:

• Exhaustively enumerate every single path from the start to the target, counting how many there are (excluding the one that your friend went on).

  You can do this using something resembling a graph traversal such as BFS or DFS.

• Alternatively, you can notice that for any path to reach the clearing, you must go north exactly of \(k\) times, and west exactly \(m\) times where \(k\) is the number of "N"s in the input, and \(m\) is the number of "W"s in the input. (Note that \(k = n - m\) where \(n\) is the length of the friend's path.) Thus, any given path can be described by which steps you go north (all non-north movements are by default going west).

  Thus, the number of paths from the start to the clearing are precisely \(n\) choose \(k\) (or \(n\) choose \(m\), they are equivalent). We can compute \(n\) choose \(k\) as follows:

  \begin{equation*} \binom{n}{k} = \frac{n!}{k!(n - k)!} \end{equation*}

  where \(n\) and \(k\) are as defined above. It's critical, however, to remember that your friend has already taken one of the paths, and you cannot go on that path. Thus, the answer is actually \(\binom{n}{k} - 1\).

G - Misty

This problem was intended to be the hardest in the competition, and I think it was, considering so few teams even attempted to solve it (2), and only one of them actually did solve it.

This problem is a classic problem in graph theory (a branch of computer science) called the minimum spanning tree (MST) problem [1]. You have to model the problem as a weighted graph where the nodes (vertices) are the houses, the edges are the paths, and the weights are the distances. Once you have modeled the problem in this way, you then need to find a subset of the edges (paths) in the graph which:

1. Ensures there is a path from every node (house) to every other node.
2. Does that at the minimal cost, that is, sum of path distances.

This subgraph will be a spanning tree [2] (proof left for readers enjoyment).

This problem can be solved using a greedy algorithm [3] which means that you do not have to do any global optimization. The Wikipedia page on the MST problem describes many algorithms for solving this problem, but here is the outline of a potential solution (this solution is basically Kruskal's Algorithm [4]):

1. Sort all of the edges by length.
2. Iterate until the entire graph has been connected. On each iteration,
   1. Get the next shortest edge by length.
   2. If adding the edge would create a cycle in the tree, then ignore it.
   3. If it would not create a cycle, add it to the tree.

This is a simplistic, high-level idea of Kruskal's algorithm. That is the thing with graph algorithms generally: the idea of them is pretty simple; but the devil really is in the details. For Kruskal's algorithm in particular, detecting cycles is non-trivial, and is one of the most computationally expensive parts of the algorithm. For the time limit for this problem, you can be fairly inefficient with how you detect cycles (no need to implement something like a disjoint-set data structure [5] or something ridiculous like that). Storing sets of already connected vertices is sufficient for solving this problem under the time limit, and even doing a BFS/DFS to see if you can reach one vertex from the other vertex in the current tree is fast enough (assuming a reasonably efficient BFS/DFS implementation). Additionally, since the point of this problem was to make contestants implement an algorithm, I intentionally designed the input format such that reading in the graph would not be too difficult.