A — 9x9

We can simply directly implement the procedure given in the problem. Print $$$AB$$$ if $$$A$$$ and $$$B$$$ are less than $$$10$$$ and $$$-1$$$ otherwise. One particularly fast way to do this is to use the ternary operator, which takes a boolean expression and two values as inputs and returns the first value if the expression is true and the second value otherwise. In C++, this looks like

$$$\texttt{A < 10 && B < 10 ? A*B : -1}$$$.

Runtime: O(1). Click here for my submission.

B — 81

Since we're only considering pairs of numbers from one through nine, we can simply iterate over every pair of numbers from one to nine and check if each pair multiplies to $$$N$$$. As soon as we find such a pair, we output Yes and exit the program. If we reach the end of the loop, we can then print No, since we've checked every possible pair and found that none of them work.

Notice that we could also iterate over all numbers from $$$1$$$ to $$$9$$$, and for each number $$$i$$$, check if $$$N$$$ is divisible by $$$i$$$ and, if so, whether $$$N / i$$$ is between $$$1$$$ and $$$9$$$. However, this would take longer to implement, and with so few values to check, the above approach is efficient enough anyway. This is a good example of a problem where it's better to quickly implement a trivial solution than to waste time coming up with a more efficient idea.

Runtime: Technically $$$O(1)$$$, though our loop will iterate $$$81$$$ times (or $$$45$$$, if you only iterate over pairs $$$(i, j)$$$ with $$$j \geq i$$$). Either way, it will run very quickly. Click here for my submission.

C — Walk in Multiplication Table

Note that we can walk to any pair $$$(i, j)$$$ in $$$i+j-2$$$ steps. Thus, we simply need to find the pair $$$(i, j)$$$ with $$$ij = N$$$ that minimizes $$$i+j$$$. Luckily, we can enumerate all possible pairs $$$(i, j)$$$ and check them in $$$O(\sqrt{N})$$$. To do this, without loss of generality, we can assume $$$i \leq j$$$, and we must have $$$i \leq \sqrt{N}$$$ since $$$N = ij \geq i^2$$$, so $$$\sqrt{N}^2 \geq i^2$$$, so $$$\sqrt{N} \geq i$$$. Thus, we can iterate over all possible values of $$$i$$$ from $$$1$$$ to $$$\sqrt{N}$$$ and, among all working pairs $$$(i, j)$$$, we pick the lowest value of $$$i+j-2$$$ and print it.

Runtime: $$$O(\sqrt{N})$$$. Click here for my submission.

D — Water Bottle

First, note that when we take an $$$A$$$-by-$$$B$$$ rectangular cross-section, tilting it counterclockwise at an angle of $$$\theta$$$, the water will be at the height of the top-left corner. (Draw the picture yourself if it's hard to visualize this in your head.) Then, we want $$$A$$$ times the area within this rectangle at or below this height to equal $$$X$$$.

We perform casework on whether the water bottle is at least half full.

Suppose that it is not half-full. Then, examining the figure, we can observe the wet area will be a right triangle with one side of length $$$B$$$ and adjacent angle $$$90^circ - \theta$$$. We can thus express the area of this triangle as $$$\frac{B^2 \tan 90^\circ - \theta}{2}$$$, and the total volume of the water will be $$$\frac{AB^2 \tan 90^\circ - \theta}{2}$$$. Thus, we have $$$X = \frac{AB^2 \tan 90^\circ - \theta}{2}$$$, which gives $$$\tan 90^\circ - \theta = \frac{2X}{AB^2}$$$, so $$$90^\circ - \theta = \arctan \frac{2X}{AB^2}$$$ and $$$\theta = 90^\circ - \arctan \frac{2X}{AB^2}$$$.

Now, suppose that the bottle is at least half-full. Then, we can observe that the part of the rectangle not filled with water is a right triangle with one side of length $$$A$$$ and adjacent angle $$$\theta$$$. This triangle has area $$$\frac{A^2 \tan \theta}{2}$$$, so the volume of the box not filled with water is $$$\frac{A^3 \tan \theta}{2}$$$. Therefore, we have $$$A^2B - X = \frac{A^3 \tan \theta}{2}$$$, so $$$\tan \theta = \frac{2A^2B - 2X}{A^3}$$$, so $$$\theta = \arctan \frac{2A^2B - 2X}{A^3}.$$$

Now, we can simply implement these formulas. Make sure to convert from radians to degrees if your programming languages uses radians by default! You can do this by multiplying by $$$\frac{180^\circ}{\pi}$$$. (If your programming language doesn't have $$$\pi$$$ built-in as a constant, you can compute it as $$$2 \arcsin 1$$$.)

Runtime: $$$O(1)$$$. Click here for my submission.

E — Gluttony

First, an intuitive observation: we should assign the fastest eaters to the most challenging foods. One way to prove this is to note that if we have two eaters with constants $$$a \leq b$$$ and two foods with difficulties $$$c \leq d$$$, we can see that $$$max(ac, bd) = bd \leq max(ad, bc)$$$, so we are better off assigning the eater with the lower constant to the food with higher constant. We can apply this algorithm many times to prove that this ordering--fastest eaters with the highest-difficulty foods--is optimal.

So, let's sort the eaters in increasing order and the foods in decreasing order. Then, we binary search for the answer, noting that this is valid because if we can finish within some amount of time, then we can also finish within any greater amount of time. To check if some value $$$T$$$ could be the answer, note that in order to make the maximum eating time equal to $$$T$$$, we need to train all eaters for whom $$$A[i] F[i] > T$$$ until $$$A[i] = \lfloor \frac{T}{F[i]} \rfloor$$$. We can thus compute the number of training sessions required in $$$O(N)$$$. An answer is valid if at most $$$K$$$ training sessions are needed. We can then use binary search to find the least possible value of $$$T$$$ using $$$O(\log A_i F_i)$$$ of these queries, since the most time we could possibly take is $$$O(A_i F_i)$$$.

Runtime: $$$O(N \log A_i F_i)$$$. Click here for my submission.

F — Fork in the Road

Let's first compute three auxiliary arrays. First, we compute an array $$$deg$$$ such that $$$deg[i]$$$ is the number of edges coming from node $$$i$$$. Then, compute an array $$$P$$$ such that $$$P[i]$$$ is the probability that we reach node $$$i$$$ at some point in the process. To do this, we can initialize $$$P[0]$$$ (using zero-based indexing for the nodes, of course) to $$$1$$$ and all other $$$P[i]$$$ to $$$0$$$. Then, process the $$$P[i]$$$ in increasing order, and for each edge from $$$i$$$ to $$$j$$$, add $$$\frac{P[i]}{deg[i]}$$$ to $$$P[j]$$$.

Finally, we want an array $$$E$$$ such that $$$E[i]$$$ is the expected value of the number of steps it will take to reach node $$$N-1$$$ from node $$$i$$$. We can write $$$E[i]$$$ in terms of higher values of $$$i$$$ as follows, where the summation is over all vertices that can be reached from $$$i$$$:

From here, we can initialize $$$E[N-1]$$$ to $$$0$$$ and then compute the $$$E[i]$$$ values in decreasing order. Note that the computation of all of these arrays is $$$O(N^2)$$$.

Now, it should be easy to see that the answer, if we don't remove any passages, is $$$E[0]$$$. What if we remove some passage, though?

Let's say we remove a passage from $$$i$$$ to $$$j$$$. To compute the new value of $$$E[0]$$$, we compute $$$E'[i]$$$, the value of $$$E[i]$$$ if we didn't have access to this passage, and add $$$(E'[i] - E[i]) P[i]$$$ to $$$E[0]$$$. The intuition here is that this will capture all of the resulting change because if we don't reach $$$i$$$, then this will have no effect on us, but if we do reach $$$i$$$, which happens with probability $$$P[i]$$$, our expected value changes by the addition of $$$E'[i] - E[i]$$$.

Now, how can we compute $$$E'[i]$$$? One way to do this would be to simply reevaluate the formula given above, subtracting one from $$$deg[i]$$$ and considering only the other nodes. This would run in $$$O(N^3)$$$, but with a two-second time limit and a good constant factor (since there can only be about $$$\frac{N^2}{2}$$$ edges and any given vertex, on average, can only have about $$$\frac{N}{2}$$$ as its degree, so we'll take $$$\frac{N^3}{4}$$$ operations in total), this will probably be fast enough.

However, we'll present a solution that computes $$$E'[i]$$$ in $$$O(1)$$$, for an $$$O(N^2)$$$ solution in total. We're essentially trying to compute

This time, the summation is over only the values of $$$j$$$ that are still adjacent to $$$i$$$ after the removal. First, let's find this summation. To do so, subtract $$$1$$$ from $$$E[i]$$$ and multiply it by $$$E[i]$$$, which gives you the summation from the original $$$E[i]$$$. Then, subtract the $$$E$$$ value corresponding to the removed passage from the summation, giving you the new summation. Now we can multiply it by $$$\frac{1}{deg[i] -1}$$$ and add $$$1$$$, at which point we're finished. Then, we can use the value of $$$E'[i]$$$ as described above to compute our answer given the removal of a certain passage.

We can then compute the answer for every possible passage removal and print the best one.

Runtime: $$$O(N^2)$$$. Click here for my submission.