A — Transfer

First, we compute the resulting amount of water in Cup 1. Observe that this is equal to $$$min(A, B+C)$$$. Let this value be $$$D$$$. Then, the amount transferred from Cup 2 to Cup 1 is simply $$$D - A$$$, so the amount remaining in Cup 2 is $$$C - D + A$$$.

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

B — Uneven Numbers

There are several efficient ways to approach this problem. One is to simply to count the one-, three-, and five-digit numbers less than or equal to $$$N$$$. However, because of the small maximum on $$$N$$$, a more naive approach works. Simply iterate over every value from $$$1$$$ to $$$N$$$, count its digits, and add one to the answer if the count is odd. (We can count a number's digits by repeatedly adding one to the count and dividing the number by ten until it reaches zero.)

Time complexity: $$$O(N \log N)$$$. Note that $$$O(\log N)$$$ is possible with the more efficient approach. Click here for my submission.

C — Build Stairs

We employ a greedy strategy. Process the elements in increasing order, and decrease the current element whenever we can do so without making it less than the last element. (The first element should thus always be decreased.) If at any point the current element must be less than the last element, no matter what we do, the answer is no.

The reason this strategy is optimal is that decreasing an number will make it easier (or at least as easy) to deal with the next element in the list, since any value the next element could have taken will still work when the previous number is lower, and in fact decreasing the previous number expands the range of possible values for the next set. (For example, if we have an element 3, the next element must be at least 3, but if we decrease this to 2, all the same values 3 or higher still work, but 2 does as well.)

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

D — Gathering Children

We first note that we can break up the given string into components consisting of a string of R's followed by a string of L's. Observe that no child will ever leave its component.

We thus solve the problem for each component. Within each component, a child on the left side will continually move to the right, or a child on the right side will continually move to the left, until it reaches the middle two characters, RL. At this point, the child will move between these two positions until the end of the process. With $$$10^{100}$$$ steps, we can see that all children will reach these two positions.

How can we determine how many children will land on the R and how many will land on the L? Note that one of these two characters must be in an odd position (based on its position in the original string) and the other must be in an even position. Because $$$10^{100}$$$ is even and each move changes the parity of a child's position, each child will end up in whichever position has the same parity as its original position. That means that whichever of R or L is on an odd position will get all the children in the component starting in odd positions, while the other will get all the children in the component starting in even positions.

We can implement this by using a two pointers-style technique to track the components.

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

E — Max GCD

First, can we substantially limit the possible answers to this problem? It turns out that we can: our $$$K$$$ moves keep the sum of our elements constant, so the answer must be a factor of our sum. Since our sum is at most $$$5 \cdot 10^8$$$, we can check every value less than or equal to the square root of the sum to compute a list of these factors. Now, we can simply check, for each of these factors, whether it is possible to use our $$$K$$$ operations to make all items in the list divisible by this factor. We then take the maximum of the factors for which this is possible.

To perform a check on a factor $$$F$$$, start by creating a multiset storing the values of the array modulo $$$F$$$. We'll need to decrease some of the values in the multiset and increase others so that all are equal to an element of the list $$$-F, 0, F, 2F,$$$ etc.

The key lemma is as follows: there will always exist a way to turn the smallest $$$X$$$ elements of the multiset, for some $$$X$$$, into $$$0$$$, and the remaining elements into $$$F$$$, in some number of moves. Moreover, this will be the smallest possible number of moves we could use.

In case you're interested, I'll give a proof that this is true after the solution. (The proof is relatively convoluted and hard to follow, which is why I'm emphasizing the rest of the solution first.)

Iterate over the multiset in increasing order. Maintain the number of subtractions required to decrease the elements we've seen so far to $$$0$$$ and the number of additions required to increase the elements we haven't seen yet to $$$F$$$. When these costs are equal, that's the minimum number of moves we need to achieve the factor $$$F$$$. If this minimum is at most $$$K$$$, $$$F$$$ is a possible answer. We can then simply print the maximum value $$$F$$$.

To prove existence, note that the sum of the values in the multiset must be $$$0$$$ mod $$$F$$$. Call an element "high" if we'll be raising it to $$$F$$$ and "low" if we'll be lowering it to $$$0$$$. Let the "cost" of an element be the number of additions or subtractions necessary to raise or lower it to its desired value. Call the "high cost" the sum of the costs of all high elements and the "low cost" the sum of the costs of all low elements. Note that the cost of a high element $$$i$$$ is $$$F - i$$$ and the cost of a low element $$$i$$$ is $$$i$$$.

Start with all elements being high. We maintain the difference of the high cost and the low cost. Initially, the high cost is the sum of $$$F - i$$$ over all elements. Since $$$F$$$ is $$$0$$$ mod $$$F$$$ and the sum of all $$$i$$$'s is $$$0$$$ mod $$$F$$$, this sum will be $$$0$$$ mod $$$F$$$. Express it as $$$kF$$$, for some integer $$$k$$$. Note that $$$0 \leq k \leq N$$$. The low cost, meanwhile, will be $$$0$$$, because no elements are currently low.

Suppose that we switch an element $$$i$$$ from high to low. In this case, the high cost will decrease by $$$F - i$$$ and the low cost will increase by $$$i$$$. Therefore, the difference will decrease by $$$(F-i) + i = F$$$. Therefore, if we switch the $$$k$$$ lowest elements from high to low, the high cost will be the same as the low cost. This means that it will take the same numbers of subtractions to deal with the low elements and additions to deal with the high elements, meaning that these subtractions and these additions can be our moves.

We have thus proven that this is doable. Now, we prove that it is optimal. First, note that if we're going to set all elements of the multiset to either $$$0$$$ or $$$F$$$, we minimize our costs by making the least values our low elements and the greatest values our high elements. Moreover, we can observe that it will always be inefficient to set any element to a value other than $$$0$$$ or $$$F$$$, as since our values are all between $$$0$$$ and $$$F-1$$$, moving to one of these other values will pass $$$0$$$ or $$$F$$$ and thus will cost us moves without getting any elements closer to $$$0$$$ mod $$$F$$$.

Time complexity: $$$O(\sqrt{S} + N \log N F(S))$$$, where $$$S$$$ is the sum of the $$$A_i$$$ and $$$F(S)$$$ is the maximum number of factors of any number less than $$$S$$$. While the exact value is hard to compute, it's not hard to see that with $$$N = 500$$$, $$$F(S)$$$ will be small enough to easily pass. Click here for my submission.

F — Enclosed Points

For each point, we count the number of subsets whose bounding rectangles enclose this point. Our answer is the sum of these values.

First, perform coordinate compression, mapping the X and Y-coordinates to integers from $$$0$$$ to $$$N-1$$$. Then, iterate over the points in increasing order of $$$X$$$. Additionally, maintain a segment tree, where each node represents a Y-coordinate and is $$$0$$$ if we have not seen this coordinate yet but $$$1$$$ if we have.

We solve the problem for each point using the Principle of Inclusion/Exclusion. First, the total number of rectangles is $$$2^N$$$, as we can either include or exclude each point from our subset. However, we must subtract the ones that don't contain the current point. For a rectangle not to contain the current point, all of the points in its subset must be above, below, to the left, or to the right of our current point. For each of these cases, let $$$P$$$ be the number of points satisfying its criterion. Then, we subtract $$$2^P$$$ to delete these cases.

However, we've subtracted out some cases twice. In particular, if all points are to the upper-left, upper-right, lower-left, or lower-right of our current point, we've subtracted it out twice (for example, the upper-left case was subtracted in the upper and left cases above), so we need to add $$$2^P$$$ back to account for each of these cases, where $$$P$$$ is the number of points satisfying each criterion.

The only case in which all points in a subset satisfy three or more of our subtraction criteria is the empty set (as no point can be both above and below our current point or both to the left and the right of this point). We added the empty set once in our original count, subtracted it four times, and then added it back four times in our most recent cases. We want it to count zero times, so we need to finally subtract the empty set once to get our final answer for the point.

Now, we need to compute the number of points satisfying these eight criteria. The first four are easy. A point $$$(X, Y)$$$, where $$$X$$$ and $$$Y$$$ are coordinates from $$$0$$$ to $$$N-1$$$, has $$$X$$$ points to its left and $$$N-X-1$$$ points to its right. Similarly, this point has $$$Y$$$ points below it and $$$N-Y-1$$$ points above it.

The remaining four criteria require us to use our segment tree. In particular, the number of lower-left points is equal to $$$query(0, Y)$$$ on our segment tree, as this stores the number of points to the left with Y-coordinates from $$$0$$$ to $$$Y$$$. Similarly, the number of upper-left points is equal to $$$query(Y, N-1)$$$ (or alternatively, simply the total number of left points minus the number of lower-left points). We can then compute the lower-right points by subtracting the lower-left points from the total lower points, and likewise, we can compute the upper-right points by subtracting the upper-left points from the total upper points.

Once we have these counts, we can use binary exponentiation to compute $$$2^P$$$ in $$$O(\log P)$$$ for each $$$P$$$. After we update the answer, we can update the segment tree at $$$Y$$$ to prepare for our next point.

Time complexity: $$$O(N \log N)$$$. Click here for my submission.