There is only one way for the leftmost piece and the rightmost piece to refer to the same object.

If $$$n=0$$$, then Alice and Bob will not fight. Since they eat $$$2$$$ pieces at a time, that means $$$n=2, 4, 6, 8, 10, ...$$$ (i.e. the even numbers) will also have them not fight.

If $$$n=1$$$, then Alice and Bob will fight over that once piece. Since they eat $$$2$$$ pieces at a time, that means $$$n=3, 5, 7, 9, 11, ...$$$ (i.e. the odd numbers) will have them fight. Since an equal number of pieces are eaten from the left and the right, we know it is the center piece that remains (when $$$0$$$-indexed, this is at index $$$\lfloor n/2 \rfloor$$$).

So, the problem is just a parity check.

For some letter, how many times does this letter occur in the substring of $$$t$$$ that begins at position $$$i$$$ and has some length $$$\mathrm{len}$$$?

You can answer this in $$$O(1)$$$ using a pen-and-paper formula (there is some standard stuff you can do since $$$t$$$ is periodic and repeats itself every $$$k^2$$$ letters) so building a histogram for all letters in some segment can be done in $$$O(k)$$$.

This is a standard use of a segment tree with lazy propagation.

The information stored in your lazy flag is the starting position $$$i$$$ of the leftmost index of this segment. The histogram for a segment can be lazily computed from its lazy flag in $$$O(k)$$$, as hinted at in the Hint.

Because $$$n \leq 10^9$$$, you will need to either need to do coordinate compression, or make your segment tree implicit (i.e. pointer based, and you only construct the children nodes when you need it).

The running time is $$$O(k \lg n)$$$ per query. You might have to do some constant factor optimization in order to pass.

You are given a single unit-radius quarter-circle arc. What is the minimum distance from $$$(h, k)$$$ to this arc?

You are given a single unit-radius quarter-circle arc and a displacement vector $$$(\Delta x, \Delta y)'$$$. The center of the quarter-circle arc can be displaced by $$$t (\Delta x, \Delta y)'$$$, where $$$t$$$ is any integer of your choice.

What choice of $$$t$$$ minimizes the distance from $$$(h, k)$$$ to this arc?

Hint 1. Draw the full circle centered at the radius of the arc. Draw a line through the center and through $$$(h, k)$$$; classically, the minimum distance from $$$(h, k)$$$ to the circle is achieved at the point where the circle intersects with this line. If this point happens to land on the arc, then the minimum distance of the arc is also exactly that point; use the distance formula and subtract $$$1$$$ (the radius of the circle). If that point does not land on the arc, then the closest point to $$$(h, k)$$$ is whichever endpoint of the arc is closer to it.

Hint 2. Because the $$$\mathrm{sqrt}$$$ function is increasing, minimizing it is the same as minimizing the thing inside it. But $$$(h - t \Delta x)^2 + (k - t \Delta y)^2$$$ is a quadratic function in terms of $$$t$$$, so it is minimized around its vertex at $$$t = -b/2a$$$. Well, there's some edge cases, but you can handle that with some if statements.

Or, alternatively, just use ternary search!

Directly simulate the string to get the full sequence of quarter-circle arcs (store the center of each one, and also direction each one is facing) that make up the Drift King's path. Simulate the entire string repeatedly until the car is facing east again (with action $$$s_0$$$ queued up next); you will only have to do this at most $$$4$$$ times.

Let $$$(\Delta x, \Delta y)'$$$ be your displacement from $$$(0, 0)$$$.

If $$$(\Delta x, \Delta y)' = (0, 0)$$$, then the car forms a closed loop. In this case, for each of the individual arcs in this path, find its distance to $$$(h, k)$$$ (using the answer to Hint 1). Take the minimum across all arcs.

If $$$(\Delta x, \Delta y)' \neq (0, 0)$$$, then the car drifts off infinitely. In this case, for each of the individual arcs in this path, find the closest it gets to $$$(h, k)$$$ (using the answer to Hint 2). Take the minimum across all arcs.

The running time is $$$O(n)$$$, potentially with a log factor if you did ternary search.

A classic math trick: Represent real tuples $$$(s, f)$$$ as points in 2D space. Then, the set of achievable points is some geometric region in space whose area we want to find.

Fix the volume $$$x$$$ of your drink. How can you compute the minimum and maximum alcohol strengths that can be made, among all drinks with this volume?

Then, convince yourself that all strengths in between the minimum and maximum can also be mixed.

Let each point $$$(x, y)$$$ in space mean a drink with a volume of $$$x$$$ and an alcohol content of $$$y$$$. The sample space of possible $$$(s, f)$$$ values corresponds to the rectangle of points with $$$0 \leq x \leq V$$$ and $$$0 \leq y \leq 1$$$. Within this rectangle, what is the total area of the points which can possibly be mixed?

To make the strongest drink possible with a given volume of $$$x$$$, greedily pour from the strongest drinks you have available, using up each bottle fully before moving on to the next one. While pouring from some given bottle with $$$a_i$$$ alcohol and $$$v_i$$$ total volume, the line traced out by this maximum is

where $$$\mathrm{prev}_a$$$ and $$$\mathrm{prev}_v$$$ are the total amount of alcohol and overall volume added by all the previous bottles before this one. The expression can definitely be simplified with some algebra, this form just communicates the most clearly that we're adding some amount of alcohol and total liquid to what has already been added so far.

The upper boundary of the feasible region thus traces out the shape of a piecewise sequence of rational functions. Similarly, the lower boundary of feasible region (i.e. the minimum strength drinks, constructed by greedily pouring from the weakest drinks we have) is also some piecewise sequence of rational functions.

All alcohol contents between the maximum and minimum strengths can also be computed. In a nutshell, consider linearly interpolating between those two points; it also always corresponds to a valid combination of drinks.

Then, the answer is

which is a simple calculus exercise. Integrate over each rational function that comprises each boundary (yes, you will have $$$\ln$$$ in your answer!).

The running time is $$$O(n \lg n)$$$.

Adding up hundreds of thousands of floating point numbers--- including a mix of positives and negatives ---is potentially numerically unstable. The prior solution, exactly as presented, will not be Accepted due to the error being too great (or at least, it didn't when I naively implemented it in Python).

The author has a much more convoluted solution linked here. The main insights are more or less the same, but great pains were taken in order to ensure provably-correct numerical stability.

Still, simpler solutions managed to pass the test data with sufficient accuracy (from both testers and in-contest participants). So you could probably figure out some simpler solution that incorporates the previous ideas while still being accurate enough . Or maybe your solution just magically gets AC without you even thinking about it, and I'm just crazy.

Only the judge has the onus of needing to be provably correct; proof by AC works for participants.

Note that $$$r \times c$$$ is quite small. The straightforward simple solution will work.

Consider the tuple $$$(\text{position of Hero A}, \text{position of Clone B})$$$. There are only up to four possible moves Hero A can make, and depending on the grid, Clone B then may or may not move.

You can just perform a BFS over all possible positions. The running time is $$$O((rc)^2)$$$ per test case, which is already fine.

When can a fold be made?

If a fold can be made... do it. Why not?

Consider a fold to be made across some axis. Both of these should hold:

• All folds along this line should be of the same kind.
• All folds on one side of the line should be the opposite of the corresponding folds on the other side of the line, across the axis of symmetry (up to the boundary of the paper).

Note that performing a fold could never potentially make a different fold invalid. Informally, making a fold only removes parts of the grid from the outside-in. The above condition will still be checking the same things, except potentially looser (i.e. fewer things to check).

Here is one "just do it" solution:

For all possible folds:

• Check if this fold is valid.
• If it is, do it.

Repeat this until no more folds can be done. The answer is YES if we end on a unit square, and NO otherwise.

There are $$$O(r + c)$$$ folds that can be made. We can naively check if each line is all H or all V, as well as check for symmetry across each axis, in $$$O(rc)$$$. Finally, you can only perform at most $$$O(r + c)$$$ folds before ending on a unit square. So, the running time is about $$$O(n^4)$$$.

This seems acceptable-but-tight, but actually our quartic bound is very lazy, and in practice, if you break early when a fold is found to be invalid, then the solution is really fast.

Suppose you have a row/column of all M or all V. You check if it is a valid fold, but it is not, because the folds on one side do not match with the folds on the other side.

Do not immediately answer NO. It is possible that this fold actually becomes valid after some more of the grid is shaved off by future folds.

Consider this example test case:

.M.
M+V
.M.
V+V
.V.
M+M
.M.
M+M
.V.
V+M
.V.

If we scan from top to bottom, the first V+V row presents an invalid fold. But after folding along the M+M row below it, suddenly it becomes valid on the next wave.

Flavorfully, just be greedy.

You need to perform at least one project in order to stop the water. But nothing is preventing you from doing more if you like.

Take all the government projects that don't cost money (i.e. $$$x_i \geq 0$$$). Why not? It's only good for you.

If you've done at least one project, you're done. If you haven't yet because everything costs money (i.e. $$$x_i \lt 0$$$ for all $$$i$$$), then you still need to do at least one project. Just pick the cheapest one and see if it can be done within budget.

Think about the parity of prime numbers. Something's fishy here.

If $$$k=1$$$, then all singleton sets are vacuously prime-spaced.

For $$$k \geq 2$$$, let's consider the elements of some subset in ascending order, and look at the gaps between consecutive values, instead of the numbers themselves. Note that these gaps must all already be prime, and also that the sum of a consecutive sequence of gaps must also be prime.

Wait a minute... most prime numbers are odd. But the sum of two odd numbers is even. The only even prime is $$$2$$$, but you can't sum up two odd primes to get $$$2$$$. Therefore it is impossible for two consecutive gaps to both be odd, i.e. one of them must be $$$2$$$.

The main idea is that we want to avoid constructing a gap whose length is even, but this is severely limiting. You can do the casework yourself, but what you'll find is...

If $$$k \leq 4$$$, then there are only a few cases. Handle them carefully. Yes, it is possible when $$$k = 4$$$ :P (many teams got that wrong during the actual contest).

Perform a double summation over all possible primes $$$p$$$ (that apply for that case) and then all possible left endpoints (i.e. the smallest value in the subset). You can simplify this summation on pen-and-paper to some prefix sums that can be precomputed.

But if $$$k \geq 5$$$, then you can show that the answer is $$$0$$$. There are no prime-spaced subsets because we will be forced to make an even-length gap (that is greater than $$$2$$$).

You can use a sieve to find all primes and twin primes in $$$O(n \ln \ln n)$$$. Then you can use binary search to answer each query in $$$O(\lg n)$$$ time.

Separately compute the contributions of each digit $$$1, 2, 3, \dots, 9$$$.

As is classic with "sum of all subarray" problems, consider some index $$$j$$$ and fix it to be the right endpoint. That is, what is the contribution of all subarrays that end in $$$j$$$?

Can you express this recursively maybe?

As hinted at, let's independently solve the problem for each of the digit values $$$d=1, 2, 3, \dots, 9$$$. That is, separately find the contribution of only the digits whose value is $$$d$$$, across all the subarrays.

We can solve the problem by DP. Let $$$dp_j$$$ be the contribution of all subarrays that end on $$$j$$$.

Let's look at what happens when we consider the digit $$$s_j$$$, and what it does to the subarrays ending on $$$j-1$$$.

• If $$$s_j \gt d$$$, then it goes to the end of the sorted subarray, "bumping" the contributions of the previous subarrays by one place value to the left. So, $$$dp_j = 10 dp_{j-1}$$$
• If $$$s_j \lt d$$$, then it goes before the $$$d$$$ digits in the sorted subarray. Nothing changes (in terms of the contribution of $$$d$$$ at least), so $$$dp_j = dp_{j-1}$$$.
• If $$$s_j = d$$$, then the sorted subarrays don't change except for this extra $$$d$$$ digit pre-pended to it.

In this last case, the contribution of this extra $$$d$$$ digit depends on its place value in the sorted subarray, i.e. on the number of pre-existing digits that are $$$\geq d$$$ in that subarray before we had pre-pended it. So, it seems we need to keep track of all that too. We have that $$$dp_j = dp_{j-1} + d \cdot c_{j-1}$$$, where

where $$$g_{j, k}$$$ is "the number of subarrays ending on index $$$j$$$ and which contain $$$k$$$ digits that are $$$\geq d$$$". This is a bit of a mouthful but I hope you can see why this corresponds to the contributions of each place value weighted by the number of times the newly-added $$$d$$$ occurs at that place value.

Anyway, we can also recursively keep track of $$$c$$$.

• If $$$s_j \geq d$$$, then $$$c_j = 10c_{j-1} + 1$$$
• Otherwise, $$$c_j = c_{j-1} + 1$$$.

You can think about why that's true. Similar to earlier, just picture everything "sliding" over nicely when a new bigger digit is introduced (and the $$$+1$$$ is because a new "empty subarray" is also introduced ending on each position).

The solution runs in $$$O(10^2 n)$$$ which is already fast enough. It's not that hard to reduce it to $$$O(10n)$$$ though, if you like.

Also, note that you don't need to actually store a memoization array. Since each layer only depends on the previous layer, you can maintain a running variable while doing a left-to-right scan.

If $$$\mathrm{deg}(u) \geq 4$$$, then Alice wins. Now there are only a few cases left to check.

Let $$$u$$$ be where Alice makes her first move. "Root" the graph at $$$u$$$. Let a child be a node connected to $$$u$$$, and let a grandchild be a node connected to a child (but not to $$$u$$$).

Let's do some case work:

• If $$$\mathrm{deg}(u) = 0$$$, Alice loses.
• If $$$\mathrm{deg}(u) = 1$$$, Alice loses.
• If $$$\mathrm{deg}(u) = 2$$$, Alice wins iff each child has two grandchildren attached to them (not necessarily distinct).
• If $$$\mathrm{deg}(u) = 3$$$, Alice wins iff at least two children have a grandchild attached to them (not necessarily distinct).
• Finally, if $$$\mathrm{deg}(u) \geq 4$$$, Alice always wins.

The interesting cases are when the degree is $$$2$$$ or $$$3$$$. But really, proving them is just some not-too-tedious casework on Bob's moves.

The solution is $$$O(n+m)$$$ since each of the above conditions can be checked in $$$O(1)$$$.

Linearity of expectation. This is the easy part.

Exponential generating functions.

By linearity of expectation, we just need to sum the probability that each individual node is toxic.

Note that the probability that some individual node is toxic depends only on the degree of that node. For a node whose degree is $$$d$$$, suppose its ranking is $$$k$$$. Then, all its $$$d$$$ neighbors must have rankings from $$$1$$$ to $$$k$$$ only (and the other nodes can be whatever ranking). So, we need to compute

for all $$$d$$$ from $$$0$$$ to $$$n-1$$$.

Ignore the fraction. The interesting part is computing all the sums of powers in subquadratic time. You can do this using the "snake oil method" from Ch 4 of generatingfunctionology (but imho this isn't too hard to figure out on your own). A more in-depth solution was written by the author and is linked here.

I personally learned how to compute the reciprocal of a power series from the editorial to 438E - The Child and Binary Tree. I think many people did!

No advanced math is needed. Everything follows from the definitions.

Expanding out the summation, what we want to compute is

Note that $$$t$$$ and $$$k$$$ each range from $$$1$$$ to $$$n$$$, so all entries of $$$A$$$ appear exactly once in this sum, and similarly for $$$B$$$.

So actually, in the first place, there are only at most $$$\min(k_a, k_b)$$$ nonzero terms in the sum (since a nonzero term in the sum only comes when both the $$$a$$$ factor and the $$$b$$$ factor are both nonzero). You can manually enumerate over all of them.

To elaborate, for each $$$b_{i, j}$$$ given in the input...

• If $$$a_{j, i}$$$ is also mentioned in the input, then they contribute $$$a_{j, i} b_{i, j}$$$ to the answer.
• If $$$a_{j, i}$$$ is not mentioned in the input, then it is $$$0$$$. This term contributes nothing.

There is an easy $$$O(\mathrm{poly}(2^c))$$$ solution. Can you see it?

There is a less-easy-but-still-pretty-standard $$$O(\mathrm{poly}(2^r))$$$ solution. Can you see it?

Here are the two exponential time solutions.

To solve the problem in $$$O(\mathrm{poly}(2^c))$$$, enumerate over all $$$2^c$$$ subsets of shops. Suppose Gagamboy commits to only buying chemicals from shops within some given subset. Then, for each chemical, he greedily buys it for the lowest price among these shops.

To solve the problem in $$$O(\mathrm{poly}(2^r))$$$, you can do DP with bitmasking. Proceed through each item in each shop, considering whether to buy it or not, and let your DP state track which chemicals you've already bought. There are some details to iron out, but that's the main idea.

To solve the problem overall... check which of $$$r$$$ and $$$c$$$ is smaller, and use that one's exponential-time solution!

If $$$rc \leq 250$$$, then $$$min(r, c) \leq \lfloor \sqrt{250} \rfloor = 15$$$, so a solution that is exponential in the smaller dimension will pass!