385452A - Minimum Process

The constraints were generous enough that implementing the process as described could pass, but there is a shorter solution:

Notice that when we apply the function to any array, the minimum value in the array never changes. So the last element remaining must be equal to the minimum element in the original array.

Implementation: 160381292 Author: BucketPotato

385452B - A, B, X (Easy Version)

Let $$$d=|a-b|$$$. Then, $$$x$$$ can be included in the set if and only if $$$|a-x|$$$ divides $$$d$$$.

First, let's show it's always possible to add $$$x$$$ when $$$|a-x|$$$ divides $$$d$$$. WLOG say that $$$a \lt b \lt x$$$. Then, using the operation, we can add $$$2b-a = b + (b-a) = b + d$$$ to the set. Next, we can add $$$2(b+d)-b = b+2d$$$ to the set. Continuing on, we can add all $$$b + kd$$$ where $$$k$$$ is an integer to the set. Similarly, if $$$x \lt a$$$, then we can do these operations reversed.

Now, let's show that if $$$|a-x|$$$ does not divide $$$d$$$, then it is impossible to add $$$x$$$. We can do this through induction. Say that for all values $$$v$$$ in the set, $$$|v - a|$$$ divides $$$d$$$. Now, let's say we perform the operation with integers $$$p$$$ and $$$q$$$, adding $$$2q - p$$$ to the set. We can rewrite $$$p = a + kd$$$ for some integer $$$k$$$, and $$$q = a + ld$$$ for some integer $$$l$$$. Then, we will be adding $$$2a + 2kd - a - ld = a + (2k - l)d$$$ to the set, which also has a difference with a divisible with $$$d$$$.

Implementation: 160381334 Author: EndlessVoid

385452C - Big Loop

First, the answer is bounded above by $$$n-1$$$. If we ever are at an index $$$i$$$ such that $$$|a_i| = n$$$, then the next move will always move us out of the board, setting our score to $$$0$$$. So, it is impossible to attain a score greater than $$$n-1$$$.

Now, we show how to construct a solution with score $$$n-1$$$ for all $$$n \ge 4$$$. We start with $$$a_1 = n-1$$$. Then, we have $$$a_n = -(n-2)$$$. And so on, with $$$a_2 = n-3$$$, $$$a_{n-1}=-(n-4)$$$... Eventually, we will left $$$2$$$ elements, and we will need to fill them in with values $$$1$$$ and $$$n$$$. We can set the index we are currently at to $$$1$$$ or $$$-1$$$, depending on which was visited already, and the other to $$$n$$$.

Intuitively, this solution is "jumping" around the array: first to last to first to last, cutting down the problem. One implementation note: the cases for the last $$$2$$$ elements is different depending on whether $$$n$$$ is odd or even. You can check these cases rather easily by trying to construct the outputs for $$$n = 4$$$ and $$$n = 5$$$ on paper.

Implementation: 160381345 Author: pocafup

385452D - ABC Subarrays

Note that since $$$s$$$ is sorted, $$$f(s')$$$ for any substring $$$s'$$$ will be $$$A' \cdot B' \cdot C'$$$, where $$$A'$$$, $$$B'$$$, and $$$C'$$$ are the number of characters A B and C in $$$s'$$$ respectively. First, if any of these characters do not appear in the entire string, the answer is $$$0$$$. Next, notice that any substring with $$$f(s') \gt 0$$$ must also contain all the B's in the string, since it cannot contain both an A and a C without also containing the B's.

Let's iterate over the number of A's. Let's say that $$$A' \cdot B' = v$$$, then we want to count how many integers $$$C'$$$ satisfy $$$1 \le C' \le C$$$ and $$$v \cdot C' \gt k$$$. We can do this with simple floor division.

Implementation: 160381361 Author: BucketPotato

385452E - Christmas Tree

An ancestor of a node $$$x$$$ is any node on the path from node $$$x$$$ to node $$$1$$$ ($$$x$$$ is also an ancestor of itself).

For some node $$$x$$$, let's count how many times any ancestor of $$$x$$$ appears in the set. Call this value $$$v_x$$$. If $$$v_x$$$ is even, the node will end up turned off. Otherwise, it will end up turned on.

Let's say we know $$$v_x$$$ already. How can we compute $$$v_y$$$, for some child of $$$x$$$? We can simply count the number of times $$$y$$$ appears in the set, and add it to $$$v_x$$$ to get $$$v_y$$$.

Note that since the constraints are large, storing the tree explicitly will be too slow. Instead, we can use the fact that the children of node $$$i$$$ are $$$2i$$$ and $$$2i+1$$$ to compute the answer without using vectors or lists of lists.

Implementation: 160381368 Author: EndlessVoid

385452F - Circular Painters

Let's look at tiles that have the value $$$i$$$. They will form a contiguous segment on the circle, and the number of them will increase by $$$1$$$ each second until the previous painter (in clockwise order) paints over the first tile that was painted with value $$$i$$$.

More formally, let's say that $$$p_x$$$ is the starting position of the closest painter in the counterclockwise direction. Then, the contribution of this painter to the answer will be $$$t \cdot i$$$ for times $$$1 \le t \le (p_i - p_x) \mod n$$$, and $$$(p_i - p_x)\mod n$$$ for times $$$t \ge (p_i - p_x) \mod n$$$.

So, the answer will be a sum of piecewise linear functions. To compute the answer quickly, let's keep track of how much the answer increases each second. Each value $$$i$$$ will cause the rate of change to increase by $$$i$$$ at $$$t=1$$$, then decrease by $$$i$$$ after $$$t=(p_i - p_x)\mod n$$$. We can quickly compute the difference array, then compute the slope of the function at each time point with prefix sums, for an overall linear time solution.

Implementation: 160381377 Author: BucketPotato

385452G - A, B, X (Hard Version)

First, if $$$|a - b|$$$ does not divide $$$|x - a|$$$, the answer is $$$-1$$$ (the full explanation is in the editorial for the easy version). Furthermore, let us ignore the cases where $$$x = a$$$ or $$$x = b$$$, since they are trivial.

Now, consider applying a function of the form $$$f(y) = \frac{y-d}{a}$$$ to all elements of $$$s$$$ (including $$$a$$$, $$$b$$$, and $$$x$$$). Then, if we previously had a number $$$v$$$ which was added as the next term in the arithmetic sequence $$$p$$$, $$$q$$$, implying that $$$v = 2q-p$$$, we would instead add to the set $$$2f(q)-f(p)$$$ which we can show is equal to $$$f(v)$$$. Therefore, applying any such function $$$f$$$ to our set results in an equivalent set. Thus, let us find some function $$$f$$$ which makes our problem more convenient. Assume WLOG that $$$a \lt b$$$.

There are two such functions we will consider. First, $$$f(y) = \frac{y-a}{b-a}$$$. Then, $$$f(a) = 0$$$, $$$f(b) = 1$$$, and $$$f(x)$$$ is an integer. We want to reduce the problem to the form $$$a = 0, b = 1, x = c$$$ for some $$$c \gt 0$$$. If $$$f(x)$$$ is negative, then we can instead use the function $$$g(y) = \frac{y-b}{a-b}$$$. It can easily be shown that exactly one of these functions will result in $$$c \gt 0$$$. Now, we will solve the problem for $$$a = 0, b = 1, x = c \gt 0$$$.

First, let us provide a lower bound on the minimum number of operations required. At time $$$t$$$, let $$$M$$$ be the maximum element in $$$s$$$, $$$m$$$ be the minimum element, and $$$w = M-m$$$. We will show that from $$$t$$$ to $$$t+1$$$, $$$w$$$ can at most double. Consider adding $$$v = 2q-p$$$ to our set. WLOG, let $$$v \gt M$$$. Then, we have that $$$v = 2q-p \leq 2M-p \leq 2M-m$$$. Hence, $$$w' \leq 2M-m = 2w$$$. Therefore, $$$w$$$ can at most double. Since $$$m \leq 0$$$, we have that $$$M \leq 2^t$$$. Therefore, it will take at least $$$\lceil{\log_2(c)}\rceil$$$ operations to add $$$x$$$ to our set.

The actual sequence can also be constructed quite easily. Clearly, the last element we add to $$$s$$$ will be $$$c$$$. The second to last will be $$$\lceil\frac{c}{2}\rceil$$$ and so forth. If $$$c$$$ is even, we will let $$$p = 0$$$, and if $$$c$$$ is odd, we will let $$$p = 1$$$. Once we have our sequence, we can simply apply $$$f'$$$ or $$$g'$$$ to convert it back to $$$a$$$, $$$b$$$, and $$$x$$$.

Implementation: 160381406 Authors: EndlessVoid, GusterGoose27

385452H - Tree Climbing

Let's consider a DP on the tree: $$$dp[i][j][k]$$$. The first dimension, $$$i$$$, is the root of the subtree we're currently considering. The second dimension, $$$j$$$, is the number of nodes in this subtree that we've visited. The third dimension, $$$k$$$, tells us whether or not we've visited node $$$i$$$.

Notice that it is possible to visit node $$$i$$$ only if $$$i$$$ is one of the teleportation nodes, or we have visited one of its children. This gives us the transitions for the DP. Say we've already computed the DP for nodes $$$2i$$$ and $$$2i + 1$$$. We can iterate over the number of nodes we visit from each of the two subtrees, then choose to add node $$$i$$$ if it's possible. The detailed description of the transitions are in the model solution implementation.

At first, it might seem like this is a $$$n^3$$$ solution ~--- however, we can note that for any $$$2$$$ nodes $$$x$$$ and $$$y$$$, we will only check this pair of nodes once, at $$$\operatorname{lca}(x, y)$$$ (this is a common trick when doing DP on trees). So this gives an overall $$$\mathcal{O}(n^2)$$$ solution.

Implementation: 160381414 Author: pocafup

385452I - Quantum Particow

Let's say we already know that the optimal path will the sequence $$$a_1, a_2, \ldots, a_n$$$. How do we compute the expected time to touch the cow? For each point, we multiply the probability that the cow is there by the distance we've already travelled. In other words, we take $$$\sum\limits_{1 \le j \le i \le n}p_{a_i} \cdot |x_{a_j} - x_{a_{j-1}}|$$$ (where $$$x_0 = 0$$$, our starting point). Note that this sum can also be interpreted the following way: For each two adjacent points, we add the distance between them multiplied by the sum of the probabilities of points that have not yet been visited.

Also note that the optimal solution will visit points with positive coordinates in increasing order of x-coordinate, and points with negative coordinates in decreasing order of x-coordinates.

This motivates a DP solution. We will maintain $$$dp[i][j][k]$$$: this state means we've visited the first $$$i$$$ positive points and the first $$$j$$$ negative points. If $$$k=0$$$, we'll say we're at the $$$i$$$-th positive point, if $$$k=1$$$ then we're at the $$$j$$$-th negative point. To transition, we have $$$2$$$ options for which point we go to next: the $$$i+1$$$-th positive point, or the $$$j+1$$$-th negative point. We can easily find the distance between our current location and the next point, then multiply it by the sum of probabilities of points not visited. The latter value can be computed with prefix sums over the points in sorted order.

Implementation: 160381429 Author: GusterGoose27

385452J - Min or Max

First, coordinate compress the values $$$a_1, a_2, \ldots, a_n$$$. We'll keep track of the probability that the expression evaluates to each one, then we can restore the expected value easily from there. So now, we'll assume that $$$1 \le a_i \le n$$$.

We'll maintain $$$dp[i][j]$$$ ~--- the probability that $$$f_i(a_i, f_{i-1}(a_{i-1}, \ldots, f_2(a_2, a_1), \ldots ))$$$ is equal to $$$j$$$. Let's say we've computed $$$dp[x][y]$$$ for all $$$x \lt z$$$. Then, there are three cases for transitions:

1. $$$y \lt a_z$$$. Then, $$$dp[z][y] = dp[z - 1][y] \cdot \frac{x}{100}$$$.
2. $$$y = a_z$$$. Then, $$$dp[z][y] = dp[z - 1][y] + \sum\limits_{1 \le i \lt y}dp[z - 1][i] \cdot \frac{100-x}{100} + \sum\limits_{y \lt i \le n}dp[z - 1][i] \cdot \frac{x}{100}$$$.
3. $$$y \gt a_z$$$. Then, $$$dp[z][y] = dp[z - 1][y] \cdot \frac{100-x}{100}$$$.

We can do this in $$$\mathcal{O}(n\log n)$$$ using lazy segment trees (for example, with range multiply update, point add update, and range sum query) to do the transitions.

Implementation: 160381458 Author: Ecrade_

The tutorial will be added as soon as we write it Author: Ecrade_