A — Harmony

Without loss of generality, let $$$A < B$$$. Then, we have three cases:

• $$$K$$$ is less than $$$A$$$. This gives $$$A - K = B - K$$$, which gives $$$A = B$$$, which is false.
• $$$K$$$ is greater than $$$B$$$. This gives $$$K - A = K - B$$$, which is also false.
• $$$K$$$ is between $$$A$$$ and $$$B$$$. This gives $$$K - A = B - K$$$, which gives $$$2K = A+B$$$.

Thus, we must have $$$2K=A+B$$$. If $$$A+B$$$ is odd, there is thus no solution. If $$$A+B$$$ is even, our answer is $$$\frac{A+B}{2}$$$. It is easy to verify that this number is indeed between $$$A$$$ and $$$B$$$.

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

B — 0 or 1 Swap

Let $$$K$$$ be the number of positions $$$i$$$ at which $$$p_i \neq i$$$ (using 1-indexing). If $$$K = 0$$$, the answer is yes, as we can simply leave the permutation as is. If $$$K = 2$$$, the answer is also yes: swap the two misplaced elements. (Notice that we can never have $$$K = 1$$$, as if any element is put in the wrong position, the element that was meant to be in that position must also be misplaced.)

If $$$K > 2$$$, the answer is no: our swap can only affect two elements and can thus only correct at most two misplacements. We can thus simply compute $$$K$$$ and check whether it is at most two to get our answer.

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

C — City Savers

We employ a greedy strategy. Notice that the first hero is the only one who can attack monsters in the first city. Therefore, the first hero should attack as many monsters in the first city as possible, only moving on to the second city after all the monsters in the first city are eradicated. Then, after the first hero attacks, the second hero is now the only remaining hero who can attack the monsters in the second city, so the second hero should prioritize second-city monsters over third-city monsters.

This logic extends to the following strategy. Process the heroes in increasing order of $$$i$$$. Let each hero start by attacking as many monsters as possible in city $$$i$$$. Then, if they can still kill more monsters after all the monsters in city $$$i$$$ are defeated, our hero can use their remaining energy to attack the monsters in city $$$i+1$$$.

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

D — Digits Parade

Let $$$dp[i][j]$$$ be the number of ways to create an $$$i$$$-digit number consistent with the first $$$i$$$ digits of the given pattern and congruent to $$$j$$$ modulo $$$13$$$. As our base case, $$$dp[0][i] = 0$$$ for $$$i$$$ from $$$1$$$ to $$$12$$$, and $$$dp[0][0] = 1$$$ (as our length-zero number has value zero and thus is zero mod $$$13$$$.)

Notice that appending a digit $$$k$$$ to the end of a number that's $$$j$$$ mod $$$13$$$ gives a number that's congruent to $$$10j+k$$$ mod $$$13$$$. We use this fact to perform our transitions. For every state $$$dp[i][j]$$$ with $$$i < N$$$, iterate over the possible values of $$$k$$$. (If $$$S[i] = \, ?$$$, there will be ten choices for $$$k$$$, and otherwise there will only be one choice.) Then, we add $$$dp[i][j]$$$ to $$$dp[i+1][(10j+k) \, \% \, 13].$$$

To get our final answer, we can simply print $$$dp[N][5].$$$

Runtime: $$$O(N).$$$ Notice that this will have a weak constant factor, with $$$13$$$ states in every row of our DP table and up to $$$10$$$ transitions for each state, but our algorithm is still easily fast enough. Click here for my submission.

E — Golf

Let's assume $$$X$$$ and $$$Y$$$ are at least zero, for simplicity. (If $$$X$$$ and/or $$$Y$$$ is negative, we simply multiply the appropriate values in our output by $$$-1$$$.)

Let $$$N$$$ be the minimum number of moves we need. Then, the total Manhattan-distance across all of our moves is $$$NK$$$. Additionally, in the end, we must move $$$X+Y$$$ further in positive directions than in negative directions. Therefore, if $$$A$$$ and $$$B$$$ are the total distances we move in positive directions and negative directions, we must have $$$A+B = NK$$$ and $$$A-B = X+Y$$$. Solving gives $$$A = \frac{NK + X + Y}{2}$$$ and $$$B = \frac{NK - X - Y}{2}$$$. Since we can only move to integer points, these must both be nonnegative integers.

We use these facts to make the following observations.

• If $$$K$$$ is even and $$$X+Y$$$ is odd, there is no solution. This is because $$$NK + X + Y$$$ will be the sum of an even and an odd, and will thus be odd, so the result when it is divided by two won't be a fraction.
• We must have that $$$NK \geq X+Y$$$ and that $$$NK = X+Y$$$ mod $$$2$$$. Both of these are implied by the fact that $$$B$$$ is a nonnegative integer. The former also should be intuitive: if we move less than $$$X+Y$$$ distance, there is no way we can get to $$$(X, Y)$$$.
• If $$$N = 1$$$, then we must have $$$X+Y = K$$$, as we can only move to a point with $$$X+Y = K$$$ in a single move.

We claim that the first observation is the only case in which the answer is $$$-1$$$ and the latter two observations are the only restrictions on $$$N$$$. Therefore, the answer is the least $$$N$$$ that satisfies the latter two observations' requirements. To prove this, we simply give the construction, which is necessary to finish anyway.

We start by dealing with our negative movement. While $$$B$$$ remains greater than $$$K$$$, simply move $$$K$$$ in the negative direction of whichever coordinate is currently closer to our goal. Once $$$B$$$ is at most $$$K$$$, we move $$$B$$$ in the negative direction of the coordinate closer to the goal, as before, and $$$K - B$$$ in the positive direction of the other coordinate.

Afterwards, we have moved exactly $$$B$$$ units in the negative direction, so we know the rest of our movement must be in the positive direction. We can therefore simply increase $$$x$$$ by $$$K$$$ until it reaches $$$X$$$, and then switch to increasing $$$y$$$ until it reaches $$$Y$$$.

You may be asking yourself why in our first step, we need to move in whichever direction is currently closer to the goal. The reason is that this protects us from forcing ourselves into unnecessary waste. As an example, suppose that $$$X=8$$$, $$$Y=0$$$, and $$$K=5$$$. We can compute by the above rules that $$$N = 2$$$, $$$A = 9$$$, and $$$B = 1$$$. Since we're currently at $$$(0, 0)$$$, we have distance $$$8$$$ from the goal in the $$$X$$$ direction and distance $$$0$$$ from the goal in the $$$Y$$$ direction. Our algorithm tells us to take our negative step in the $$$Y$$$ direction while using the rest of our movement to increase $$$X$$$. This takes us to $$$(4, -1)$$$. Our next move is then to $$$(8, 0)$$$, as desired. If we took our negative step in the $$$X$$$ direction, we would get to $$$(-1, 4)$$$ or $$$(-1, -4)$$$, which leads to wasted movement in the $$$Y$$$ direction. There is no one-step path from either of these points to $$$(8, 0)$$$.

Runtime: $$$O(N)$$$. Our limiting factor is the need to reconstruct our steps. We can bound $$$N$$$ as $$$O(X+Y)$$$, so this is fast enough. Click here for my submission.

F — Strings of Eternity

For simplicity, we let $$$N = |S|$$$ and $$$M = |T|$$$.

Let's try to understand the setup here. We can reformulate the problem: we want to find the greatest $$$i$$$ for which the concatenation of $$$i$$$ copies of $$$T$$$ appears somewhere in an infinite concatenation of $$$S$$$.

One key observation is that it never matters which copy of $$$S$$$ we're in: we can define our state simply as the position of $$$S$$$ we're in after adding a copy of $$$T$$$ to our concatenation.

This motivates the following first step. Concatenate copies of $$$S$$$ until the resulting string has length of at least $$$N+M$$$. Then, using any efficient string matching algorithm (I successfully used Rabin-Karp), determine which of the $$$N$$$ positions in $$$S$$$ could be the start of a copy of $$$T$$$.

We now reformulate this as a graph problem. Notice that if we start a copy of $$$T$$$ in position $$$i$$$ on $$$S$$$, the next copy of $$$T$$$ would start at position $$$(i+M) \, \% \, N$$$. We build a directed graph where each node represents one of the $$$N$$$ positions in $$$S$$$. If position $$$i$$$ could be the start of a copy of $$$T$$$, we add an edge from $$$i$$$ to $$$(i + M) \, \% \, N$$$.

The answer is now the length of the longest path in this graph, as traversing an edge represents adding a copy of $$$T$$$. This is a fairly standard problem. We can solve it using a similar algorithm to topological sort. Maintain a queue of vertices we are currently able to process, and store arrays maintaining the lengths of the longest paths ending at each node and whether each node has been visited. To start, consider every vertex with indegree zero. Add these vertices to the queues and set the lengths of their longest paths to zero.

When we visit a node, mark this node as visited, then subtract one from the indegree of the vertex at the end of this vertex's edge (if the vertex does have an edge). Then, set the longest path to this next vertex as the maximum of its previous value or one plus the longest path to our starting vertex. If the indegree of the next vertex is now zero, add it to the queue.

At the end of our process, the length of the longest path is infinity if and only if some vertex has never been visited (as this occurs exactly when our graph contains a cycle). If every vertex has been visited, our answer is the highest value in our distance array.

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

If you have any questions, please feel free to post them below!