A — Circle

The area of a circle with radius $$$r$$$ is $$$r^2 \pi$$$, while the area of a circle with radius $$$1$$$ is $$$\pi$$$. The answer is thus $$$\frac{r^2 \pi}{\pi} = r^2$$$, so we can simply print $$$r \cdot r$$$.

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

B — Echo

First, the answer is obviously no if $$$N$$$ is odd. Otherwise, we can directly check whether the strings created by the first and last halves of $$$S$$$ are the same. One way to do this is to iterate over all positions $$$i$$$ from $$$0$$$ to $$$\frac{N}{2}-1$$$ (remembering that the positions in a string are zero-indexed) and check whether position $$$i$$$ stores the same character as position $$$i + \frac{N}{2}$$$. If this isn't the case for some $$$i$$$, the answer is no. If, on the other hand, this holds for all $$$i$$$, the answer is yes.

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

C — Average Length

The key to this problem is the C++ STL next_permutation function. (Some other languages may have similar methods; some do not.) If you aren't familiar with this function, running next_permutation(vec.begin(), vec.end()) rearranges the elements in the vector vec into the next lexicographically higher permutation, returning true if this was possible or false if vec is already in its lexicographically highest possible arrangement (which occurs when it is sorted in decreasing order). The function runs in $$$O(N)$$$.

We can use this function to generate all possible permutations of $$$N$$$ elements in $$$O(N \cdot N!)$$$. Then, for each permutation, we can easily compute the distance between each consecutive pair of points and add them to the answer. Finally, we divide the answer by $$$N!$$$ to get our average and print it.

If you're using a language that doesn't support a function like this: first of all, you should probably learn C++, but secondly, there are also other ways to generate the permutations. One fairly simple way to do this is recursive backtracking, storing an array containing the elements used so far in our current permutation and iterating over all possible remaining elements. This can be implemented efficiently, but even an extremely inefficient implementation runs in $$$O(N^3 \cdot N!)$$$, which, given $$$N \leq 8$$$, should run in time.

Runtime: $$$O(N \cdot N!)$$$. Click here for my submission.

Fun fact: There's also an $$$O(N^2)$$$ solution to this problem relying on a slightly more clever insight. Note that element $$$i$$$ will appear immediately before element $$$j$$$ in $$$(N-1)!$$$ of our permutations, since there are $$$N-1$$$ ways to position $$$i$$$ and $$$(N-2)!$$$ ways to arrange the remaining $$$N-2$$$ elements. Thus, we can add the distance from point $$$i$$$ to point $$$j$$$ multiplied by $$$\frac{1}{N}$$$ to our answer, since it will appear in $$$\frac{1}{N}$$$ of our permutations. The total sum over all ordered pairs $$$(i, j)$$$ with $$$i \neq j$$$ is our answer.

D — Knight

First, note that $$$X+Y$$$ must be a multiple of three for any paths to exist, since both of our moves increase the sum of our coordinates by $$$3$$$. If this does not hold, the answer is zero. Then, we must take $$$K = \frac{X+Y}{3}$$$ moves. Suppose that we take $$$N$$$ moves that increase our coordinates by $$$(2, 1)$$$ and $$$K-N$$$ moves that increase our position by $$$(1, 2)$$$. Then, in order to reach $$$X$$$ as our x-coordinate, we must have that $$$2N + K-N = X$$$, so $$$N = X - K$$$. Then, we must take $$$K - N$$$ moves that increase our position by $$$(2, 1)$$$. Note that if $$$X-K$$$ or $$$2K-X$$$ is less than zero, we obviously cannot make a negative number of moves in one direction, so our answer is zero. (This will occur if one of $$$X$$$ and $$$Y$$$ is more than double the other.)

Now, note that the order of our moves doesn't affect our final outcome. Thus, we need to make $$$K$$$ moves, of which $$$N$$$ are one type and $$$K-N$$$ are the other. The number of ways to do this is simply $$$\dbinom{K}{N}$$$, or, in terms of our original variables, $$$\dbinom{\frac{X+Y}{3}}{\frac{2X-Y}{3}}$$$, which is our answer. The choose function can be computed in $$$O(X+Y)$$$.

Runtime: $$$O(X+Y)$$$. Click here for my submission. The logic I used is slightly different from what was described here, but it is ultimately equivalent to this solution.

E — All-you-can-eat

We employ dynamic programming. One key insight here is that the timing condition is equivalent to eating some dishes that take a total of no longer than $$$T-1$$$ minutes, followed by one final dish whose time constraint doesn't matter.

Let $$$dp[i][j][k]$$$ be the greatest happiness we can achieve if we've eaten dishes taking a total of $$$i$$$ minutes to consume and we've taken some subset of the first $$$j$$$ dishes. $$$k$$$ is $$$1$$$ if we've already taken a dish and ignored its time constraint and $$$0$$$ if not. Then, we can transition from $$$dp[i][j][k]$$$ to $$$dp[i+A_i][j+1][k]$$$ or, if $$$k = 0$$$, to $$$dp[i][j+1][1]$$$, and add $$$B_i$$$ happiness in the process. Additionally, since we can waste time, skip a dish, or not bother to eat an extra dish with no cost, we can also transition to $$$dp[i+1][j][k]$$$, $$$dp[i][j+1][k]$$$, or $$$dp[i][j][k+1]$$$ with no happiness increase. Of course, each $$$dp$$$ value should be the maximum possible over all ways to transition to it.

From here, our answer is $$$dp[T-1][N-1][1].$$$

Runtime: $$$O(N^2)$$$, as we have $$$O(N^2)$$$ states and $$$O(1)$$$ transitions in our DP table. Click here for my submission. Note that I used a 2D DP table storing rows corresponding to $$$i$$$ and $$$k$$$. My loop iterating over $$$x$$$ corresponds to $$$j$$$ in this table.

F — Laminate

Again, we use dynamic programming. Let $$$dp[i][j]$$$ be the minimum cost of painting the first $$$i$$$ columns given that we've changed $$$H_i$$$ for $$$j$$$ of them, given that column $$$i$$$ has not had its $$$H_i$$$ changed.

Let's figure out the transitions. Suppose we want to reach $$$dp[i][j]$$$, and the last $$$k$$$ columns before column $$$i$$$ will have their heights changed. In this case, our last painted column is $$$i-k-1$$$, so our previous state was $$$dp[i-k-1][j-k]$$$. Now, if the height of column $$$i$$$ is less than or equal to the height of $$$i-k-1$$$, we can set the height of all adjusted columns in the middle to the height of column $$$i$$$ and then paint all of these columns using some of the same strokes we used for column $$$i-k-1$$$, so the cost of this transition is zero. Otherwise, we can use $$$H_{i-k-1}$$$ strokes to start painting column $$$i$$$ but will need $$$H_i - H_{i-k-1}$$$ more to finish, so this is the cost of our transition.

There are several ways to compute the final answer from this DP table, though the constraint that column $$$i$$$ must not have had its height modified is bothersome since it could be that the best solution involves modifying the last column's height. Probably the easiest way to get around this is to add an extra column with $$$H_i = 0$$$ at the end--given our cost scheme, this will never increase the height, nor will it be advantageous to change the height of this column. Then, our answer is $$$dp[N][K].$$$

Runtime: $$$O(N^2K)$$$, since each of our states has $$$O(N)$$$ transitions. Click here for my submission.

Feel free to post below if you have any questions or comments.