Let the stick lengths be $$$X, Y, Z$$$. The broken stick $$$X$$$ either forms two parallel sides or two perpendicular sides. In the first case, $$$X$$$ is even and $$$Y == Z$$$. In the second case, $$$X == Y+Z$$$. We try all choices of $$$X$$$.

A Solution

Say we dislike $$$L$$$ songs — those $$$L$$$ songs must have unique ratings $$$q_i$$$ from $$$1$$$ to $$$L$$$. To minimize the sum of $$$|p_i - q_i|$$$, we should keep $$$q_i$$$ in the same order as $$$p_i$$$.

B Solution

Optimal strategies can be described by $$$(x, k)$$$: decrease the lowest value by $$$x$$$, then set the largest $$$k$$$ values to the lowest value.

Let $$$M$$$ be the lowest value. For each $$$k = A[..i]$$$, let's find the least $$$x$$$ that we need. For $$$k = 0$$$, it is just $$$\max(0, \text{sum}(A) - K)$$$. For other $$$k$$$'s, we have the equation $$$(M-x) * (i+2) + \text{sum}(A[i+1 : -1]) \leq K$$$ which can be solved.

C Solution

We try to classify all valid strings into disjoint sets to count them. Let $$$X_i$$$ be the set of all valid strings $$$t$$$ where $$$i$$$ is the last position where $$$s[i]$$$ and $$$t[i]$$$ differ. The answer is $$$1 + \sum_i X_i$$$.

To count $$$X_j$$$, let $$$i$$$ be the lowest index so that $$$s[i..j]$$$ contains $$$k$$$ ones. If this exists, then we either have $$$j-i$$$ spaces to fit $$$k$$$ or $$$k-1$$$ ones depending on the value of $$$s[j]$$$ (it must change).

D Solution

First, $$$r_i = \sum_j s_{i,j} p_j$$$.

Now, observe $$$|x| = \max(x, -x)$$$, and $$$|x| + |y| = \max(x + y, x - y, -x + y, -x - y)$$$, etc. Using this idea, we can find the maximum surprise as the max over all $$$2^n$$$ possibilities of replacing $$$|x_i - r_i|$$$ with $$$x - r$$$ or $$$r - x$$$. This results in a sum of the form $$$c_0 + c_1 * p_1 + \cdots + c_n * p_n$$$, for which the best permutation can be chosen greedily (by the rearrangement inequality.)

E Solution

Brute forcing small values, it seems we remove at most 3 values, so let's focus on removals.

Represent every prime as a random bitmask $$$\text{mask}(P)$$$. Then with $$$\text{mask}(X * Y) = \text{mask}(X) \oplus \text{mask}(Y)$$$, we can check whether a number is probably a square with $$$\text{mask}(X) = 0$$$.

Now we can use this trivially to solve for any $$$n$$$ with $$$\leq 2$$$ removals. For the others, try removing $$$n$$$ then applying the procedure again — we can check that this works, so every answer has $$$\leq 3$$$ removals and we've found the optimal answer for all $$$n$$$.

F Solution

If the string has odd length, you can't split it into equally sized parts.

Otherwise, the parts are $$$s[:\frac{n}{2}]$$$ and $$$s[\frac{n}{2}:]$$$ and we check they are equal.

A Solution

Say a number is special if its a square or a cube.

Precalculate all special numbers $$$\leq 10^9$$$. There are only approximately $$$10^{4.5} + 10^3$$$ of them, or about 32000.

To query whether a number is special, we can either do a binary search or linear scan. Alternatively, we could order the queries.

B Solution

Greedy from right to left. Notice that in each step of the addition, to get a two digit number, the result has to be atleast 10 higher. So there is at most one choice in each addition: either you can make a 1 digit or 2 digit number, but not both.

So in the implementation, check if you can complete the addition for the result being 1 digit, or 2 digits if that fails.

C Solution

Let's binary search for the answer, reducing the question to the decision problem of if a certain value of alpha can be achieved.

In this context, each shop's item is either valuable (value >= alpha) or not valuable. Because we can only go to n-1 shops, 2 or more friends must have a valuable item at some shop. Also every friend must have a valuable item at some shop. We can check both of these conditions quickly.

D Solution

There are two conditions for the MEX to be R: * All the values at R have to be incremented by 1 (call this count(R)) * All the values <= R-1 have to be filled (call this low(R-1))

count(R) is easy to find. Note low(R)'s can be found additively with a greedy method: we always pull the largest "free" value towards R, so that low(R) = low(R-1) + (distance from largest unused value). We can keep track of these "largest unused values" using a maxheap.

E Solution

All this is window dressing for a simple round robin algorithm. Say for example, there are three tables of 5 and more tables of 4. In the first seating, seat people normally (1-5, 6-10, 11-15, 16-19, 20-23, ...). The first 15 people get to sit at the "big" tables. In the second seating, seat the next 15 people (16-30) into the big tables, by seating them (16-20, 21-25, 26-30, 31-34, ...) (circle back to 1 if you get to the last person). It's clear that the use-frequency of the big tables is kept together with this approach.

F Solution

Consider a graph where bombs are connected by an edge iff blowing up one would cause the other to blow up. Using DSU or otherwise, we can find all connected components, and also the time where all the bombs in that component would all blow up without intervention.

Now what follows is a simple array problem: if the answer is X, it means we've blown up (X+1) components and the remaining components blow up at time <= X. We can scan linearly to find the first X that satisfies the conditions.

G Solution

(Thanks @neal)

Sqrt decomposition. Let $$$r = \lfloor \sqrt{n} \rfloor + 1$$$ The idea is that jumping $$$k = Ar + B$$$ steps can be done with $$$A$$$ big steps of distance $$$r$$$, and $$$B$$$ small steps of distance $$$1$$$.

Let $$$P(x)$$$ be the permutation, and $$$Q = P^{-1}$$$, $$$\text{jump} = P^r$$$. We maintain these throughout the operations.

The query is easy, so let's focus on the swap, say swapping $$$x, y$$$. We need to update $$$P, Q, \text{jump}$$$. We can update $$$\text{jump}$$$ by maintaining $$$x, y, jx = \text{jump}(x), jy = \text{jump}(y)$$$ as all four pointers walk backwards one step at a time.

H Solution