There are two types of subarrays.

If there exists $$$a_i \geq a_{i+1}$$$, how many times can the subarray appear?

• If there exists an $$$i$$$ such that $$$a_i \geq a_{i+1}$$$, we have $$$a_i = k$$$ for some $$$k$$$, $$$a_{i+1} = 1$$$. The subarray $$$[k, 1]$$$ appears only once on the blackboard (when James writes $$$1, \ldots, k$$$ and then $$$1, \ldots, k+1$$$). Since $$$a_1, a_2, \ldots, a_m$$$ contains $$$[k, 1]$$$, it must appear at most once as well, but the statement guarantees that it appears at least once, so the answer is $$$1$$$.
• Otherwise, the array $$$a_1, a_2, \ldots, a_m$$$ can be rewritten as $$$l, l+1, \ldots, r$$$, and it appears when James writes $$$1, \ldots, r$$$, then when James writes $$$1, \ldots, r+1$$$, ..., then when James writes $$$1, \ldots, n$$$ (so $$$n-r+1$$$ times in total).

Complexity: $$$O(n)$$$

340224512

Suppose you have already calculated where person $$$i-1$$$ goes. Can you calculate fast where person $$$i$$$ goes?

The first $$$i-2$$$ cells visited by people $$$i-1$$$ and $$$i$$$ coincide.

Person $$$i$$$ performs the same commands as person $$$i-1$$$, with the addition of the $$$i$$$-th command.

Now we wonder whether performing the same $$$i-1$$$ commands means that the first $$$i-1$$$ cells visited are the same. This is actually false in general, because after person $$$i-1$$$ performs his commands, he colors a new cell black, and this can change the outcome of the $$$(i-1)$$$-th operation. However, the outcome of the first $$$i-2$$$ commands remains the same, because the new black cell is too far from the positions visited in the first $$$i-2$$$ commands.

So the position visited by person $$$i$$$ after $$$i-2$$$ commands is the same position visited by person $$$i-1$$$ after $$$i-2$$$ commands, and it's enough to simulate the last two commands naively.

Complexity: $$$O(n \log n)$$$ or $$$O(n)$$$

340224365

For a fixed $$$k$$$, find a greedy strategy.

You can calculate the answer with prefix sums.

Consider the following strategy:

• Iterate over events in increasing order.
• In the first $$$k$$$ events, people enter the museum. In the last $$$k$$$ events, people exit. For the other events, if the current number of people is $$$k$$$ a person exits, otherwise a person enters.

This strategy is optimal, because it maximizes the number of people present at any time in the museum.

• After the $$$i$$$-th event with $$$i \leq k$$$, at most $$$i$$$ people can be inside the museum, and in fact we have exactly $$$i$$$.
• A similar argument works for the last $$$k$$$ events (you have to use that at the end the museum is empty).
• For the other events, after the $$$i$$$-th event we know that the parity of the number of people is equal to the parity of $$$i$$$. In fact, the number of people is either $$$k$$$ or $$$k-1$$$, which is the maximum possible number of people $$$\leq k$$$ with the correct parity.

Now we have to calculate the following terms:

• $$$1 \cdot a_1 + 2 \cdot a_2 + \ldots + k \cdot a_k$$$: can be done with prefix sums of $$$i \cdot a_i$$$.
• $$$k \cdot a_{2n-k+1} + (k-1) \cdot a_{2n-k+2} + \ldots + 1 \cdot a_{2n}$$$: can be done with prefix sums of $$$(2n-i+1) \cdot a_i$$$:
• $$$k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k})$$$, $$$k \cdot (a_{k+2} + a_{k+4} + \ldots + a_{2n-k-1})$$$ and similar: can be done with prefix sums of $$$a_{2i}$$$, and prefix sums of $$$a_{2i+1}$$$.

Alternatively, we can calculate the answer for some $$$k$$$ fast using the answer for $$$k-2$$$ and changing a few terms.

Complexity: $$$O(n)$$$

340224635

Let's ignore the first condition for now.

Some cells are necessarily black.

Then, some cells are necessarily white.

Now what happens with $$$k = 2$$$? You can conclude that some cells in column $$$2$$$ are necessarily white.

Repeat with $$$k = 3$$$, etc.

Once you find all the grids which satisfy the second and the third conditions, iterate over rows in decreasing order.

• $$$(1, 1)$$$ is black, because of the second condition with $$$k = 1$$$.
• Then, $$$(i, 1)$$$ is white for $$$i \geq 2$$$, because of the third condition with $$$k = n$$$.
• Then, either $$$(1, 2)$$$ or $$$(2, 2)$$$ is black, because of the second condition with $$$k = 2$$$.
• Then, $$$(i, 2)$$$ is white for $$$i \geq 3$$$, because of the third condition with $$$k = n-1$$$.
• $$$\ldots$$$

In general, only $$$(i, j)$$$ with $$$i \leq j$$$ can be black. If you repeat the same process starting from $$$(1, n)$$$, you can conclude that only $$$(i, j)$$$ with $$$i \leq n-j+1$$$ can be black.

So, for each column $$$j$$$, there is exactly one black cell $$$(i, j)$$$, with $$$i \leq \min(j, n-j+1)$$$.

Now you can iterate over rows in decreasing order. For each row, you have some number $$$c_i$$$ of available columns, and $$$a_i$$$ columns you must fill, and this can be done in $$$\binom{c_i}{a_i}$$$ ways. You can calculate $$$c_i$$$ from $$$c_{i+1}$$$ by calculating the number of new available columns, and subtracting the $$$a_{i+1}$$$ columns you must fill.

Complexity: $$$O(n \log n)$$$ or $$$O(n)$$$

340224711

Try to come up with a condition for when Alice can choose some subset of items.

Write a dynamic programming $$$O(n^2)$$$ solution based on the condition.

Optimize the solution with data structures like segment trees.

We can assume $$$a_i = i$$$ for all $$$i$$$. Now, if Alice wants to take some subset $$$S$$$, we have the following condition:

• For all $$$x \notin S$$$, $$$y \in S$$$, if $$$x \lt y$$$, then $$$pos_x \lt pos_y$$$, where $$$pos = b^{-1}$$$

Proof: If $$$pos_x \gt pos_y$$$, the item $$$y$$$ cannot be taken before $$$x$$$ because $$$x$$$ comes first in Alice's priority order. And item $$$x$$$ cannot be taken before $$$y$$$ because $$$y$$$ comes first in Bob's priority order.

Now, if the condition is satisfied, infact all subsets are valid. A simple algorithm works, just make Alice take all items in $$$S$$$ in increasing order, and when Alice wants to take some item but it is not the first remaining item according to her priority order, Bob takes items till it becomes first in her priority order.

Now, we can write our dynamic programming solution: $$$dp_{(i, j)} =$$$ maximum sum of items taken by Alice within the first $$$i$$$ items such that $$$max(pos_x)$$$ among Bob's items is $$$j$$$.

Transitions are:

• We are allowed to let Alice take item $$$i + 1$$$ if and only if $$$pos_i \gt j$$$.
• Bob can take item $$$i + 1$$$ without restrictions, and $$$j$$$ gets updated to $$$\max(j, pos_{i + 1})$$$

We then optimize this with storing a segment tree over the states $$$j$$$. The first type of transition is a range add query, the second type of transition can be split into $$$j \lt pos_{i + 1}$$$ and $$$j \gt pos_{i + 1}$$$, in the first case we do nothing, and in the second case we need a range max query.

All of the above operations can be handled with a lazy segment tree. The time complexity is $$$O(n \cdot log(n))$$$.

340224797

Find a characterization for when a position array $$$p$$$ is possible. It helps to think in terms of $$$f_x =$$$ the number of people at coordinate $$$x$$$ instead.

Essentially, an attraction at $$$x$$$ combines the people standing at $$$x - 1, x$$$ and $$$x + 1$$$. Each update unites $$$3$$$ components into one, except for updates at the edge.

Read the hints. We are trying to find a characterization for valid sequences $$$p$$$.

We can prove the following necessary conditions easily by considering what happens when an attraction is placed in different positions,

• There exists $$$1 \le L \le R \le n$$$ such that $$$f_i \ge 1$$$ if and only if $$$L \le i \le R$$$.
• $$$f_i$$$ is odd for all $$$L \lt i \lt R$$$.

Further, these conditions are sufficient, and a simple construction is to do $$$\frac{f_i}{2}$$$ attractions at the position of the centre of the group of people finally at $$$i$$$ (The edges are handled easily). Also, you may have to do some translations at the end, which can be done by attracting at $$$1$$$ or $$$n$$$.

Try to fix $$$L$$$ and $$$R - L + 1$$$, and then calculate the sum under these restrictions.

The middle $$$R - L - 1$$$ variables have to be odd, and the outer $$$2$$$ variables can have any parity. Fix the parity of the outer elements.

Use expected value symmetry arguments to calculate the sum fast.

Assume $$$L = 1$$$ and $$$R = K$$$ ($$$K \gt 1$$$) for now. We have the equation $$$f_1 + f_2 + f_3 + \ldots + f_k = n$$$, and $$$f_i \ge 1$$$ and $$$f_i$$$ odd for $$$i \ne 1$$$ and $$$i \ne k$$$, where $$$f_i =$$$ the number of people finally at $$$i$$$. We want $$$\sum f_i \cdot a_i$$$ over all ways.

Fix parity of $$$f_1, f_k$$$ say $$$x$$$ and $$$y$$$ (let $$$1 \le x, y \le 2$$$), and then let

• $$$f_i = 2 \cdot g_i + 1$$$ for all $$$i \ne 1, i \ne k$$$
• $$$f_1 = 2 \cdot g_1 + x$$$
• $$$f_k = 2 \cdot g_k + y$$$

Let $$$S = n - x - y - (k - 2)$$$. Now, the equation becomes $$$\sum g_i = \frac{S}{2}$$$, and we want $$$\sum 2 \cdot g_i \cdot a_i$$$ over all ways ($$$+$$$ a few more terms arising from the constants $$$1$$$, $$$x$$$ and $$$y$$$).

If $$$S$$$ is odd, no solution. Assume $$$S$$$ even.

Since all $$$g_i$$$ variables are symmetric, we can just say the expected value of $$$g_i$$$ is $$$\frac{S}{2 \cdot k}$$$, and then calculate $$$\sum ways \cdot EV(g_i) \cdot a_i$$$, where $$$ways$$$ is the number of solutions (simple stars and bars).

To solve the full problem, note that it essentially requires you to optimize finding sum of subarrays of size of length $$$k$$$, and this can be done (cleanly) with prefix sums on prefix sums. Also, you need to handle $$$L = R$$$ separately. The final solution is $$$O(n)$$$.

340224836

Assume all elements appear twice, and look for a contradiction.

Split the array into two.

Determine whether each value appear on the left, on the right, or in both.

Continue recursively.

Write a recursive function solve(tl, tr, vals, waste), which means that

• you are looking for the special value in the interval [tl, tr];
• the vector vals contains the values which only appear in [tl, tr];
• the vector waste contains the value which appear both in [tl, tr] and outside it.

At the beginning, call solve(1, 2n - 1, {1, 2, ..., n}, {}). In every call,

• let tm = (tl + tr) / 2, and split the interval [tl, tr] into two intervals [tl, tm] and [tm+1, tr];
• for each value in waste determine the sub-interval containing it (spending $$$1$$$ query);
• for each value in vals determine the sub-intervals containing it (spending at most $$$2$$$ queries).

Now pretend every element appears twice, and calculate the length of [tl, tm] and [tm+1, tr] according to the values they contain. One of the lengths turns out to be wrong, because the interval contains a single element which was counted twice, so you can recurse there.

You visit at most $$$\lceil \log_2 n \rceil$$$ intervals. The total length of the visited intervals is at most $$$4n + \lceil \log_2 n \rceil$$$ (the starting interval has length $$$2n-1$$$ and is halved every time).

For an interval of length $$$l$$$, you ask at most $$$l+1$$$ queries. So you ask at most $$$4n + \lceil 2 \log_2 n \rceil$$$ queries in total.

340224890

For a single value, if it appears twice, how many queries can you spend on average to detect that?

Combine a randomized solution with the solution to 2150E1 - Hidden Single (Version 1).

After the first layer of recursion in the solution to 2150E1 - Hidden Single (Version 1), you have spent around $$$7n/4$$$ queries, and there are around $$$n/4$$$ candidate values which can be the special value.

Consider the following procedure to approximately halve the number of candidates:

• split the array randomly into two halves (subsets);
• for each candidate, determine whether it appears in both halves.

With probability around $$$1/2$$$, the candidate appears in both halves and you use $$$2$$$ queries to detect it. Otherwise, you spend $$$3/2$$$ queries on average. So the average number of queries is approximately the solution to $$$x = 2/2 + (x+3/2)/2$$$, which is $$$7/2$$$. So you spend around $$$21n/8$$$ queries in total. Because of variance, you might end up asking significantly more queries, but with high probability you ask at most $$$900$$$ queries.

Bonus: you can further reduce the number of queries using some minor optimizations. For example, instead of splitting randomly, you can shuffle the array randomly at the beginning, and binary search every candidate. This is better because:

• there is an upper bound on the number of queries you make for each candidate;
• you ask queries on smaller subsets, so the probability of a candidate appearing twice in the same subset is slightly lower;
• you can break earlier if you find the special value.

The model solution based on this approach takes only $$$863$$$ queries on worst case with $$$10^4$$$ tests of size $$$n = 300$$$.

340224967

Use $$$k = 3$$$ for the first operation. Now, you have edges between all vertices at distance $$$1$$$ and $$$2$$$.

Use $$$\frac{D}{2} + 1$$$ for your second operation, where $$$D$$$ is the diameter.

Assume the graph is a tree, otherwise take an arbitrary spanning tree. First operation is $$$k = 3$$$, because that adds edges between all vertices at distance $$$2$$$, and we already have edges of vertices at distance $$$1$$$.

The second operation needs to be at least $$$\frac{D}{2} + 1$$$, where $$$D$$$ is diameter, because otherwise it is impossible to construct a path between the farthest nodes. And infact, it is possible to construct paths of length exactly $$$\frac{D}{2} + 1$$$ between all pairs of vertices, so we choose second operation as this.

The construction is as follows, suppose we want a path between nodes $$$u$$$ and $$$v$$$ (there are simpler constructions, the editorialist describes his). Let $$$c_x$$$ denote the closest node in the diameter to node $$$x$$$.

• $$$dist(u, v) \ge k$$$ : Just take a direct path between $$$u$$$ and $$$v$$$, and skip appropriate number of vertices.

• $$$c_u \ne c_v$$$ : First construct a path from $$$u$$$ to $$$c_u$$$ and similarly, $$$v$$$ to $$$c_v$$$. Now, we need to waste some operations because $$$dist(u, v) \lt k$$$. Assume the diameter is $$$1, 2, \ldots, D$$$ WLOG. Then, we can do the following operation: $$$(c_u, c_u - 2, c_u - 4, c_u - 3, c_u - 1, c_u + 1)$$$ and we successfully wasted $$$4$$$ steps.

This can be easily generalized to all lengths. Because $$$dist(u, v) \lt k$$$ implies $$$dist(c_u, c_v) \lt k$$$, and thus, $$$dist(1, c_u) + dist(c_v, D) \ge k$$$, so it is always possible to waste sufficient number of steps on the paths $$$1$$$ to $$$c_u$$$ and $$$c_v$$$ to $$$D$$$.

• $$$c_u = c_v$$$ : Root the tree at $$$c_u$$$. Assume that $$$u$$$ is an ancestor of $$$v$$$ (if it is not, make it an ancestor by jumping to parent). Either $$$dist(1, u) \ge k$$$ or $$$dist(D, u) \ge k$$$ [due to property of diameter, $$$k = \frac{D}{2} + 1$$$]. Then we can waste the sufficient number of steps on the path from $$$1$$$ to $$$u$$$, or $$$L$$$ to $$$u$$$ whichever one is larger. ($$$1$$$ and $$$D$$$ are diameter endpoints).

The entire solution runs in $$$O(n^3)$$$.

340225230

Let's first solve the following subproblem: given $$$x, y, k,$$$ how can we find the number of binary strings with Longest Nondecreasing Subsequence $$$\geq k$$$?

The answer is if $$$max(x,y)\geq k$$$, the answer is $$$\binom{x+y}{x}$$$. Otherwise, it is $$$\binom{x+y}{k}$$$. The proof for the first case is obvious. In the second case, we can approach it by bijecting it to paths on a grid. We start at the point $$$(0,0)$$$ and we want to get to the point $$$(x,y)$$$ through going East ($$$+1$$$ on $$$x$$$-coordinate) or North ($$$+1$$$ on $$$y$$$-coordinate). We claim that any path $$$p_0=(0,0), p_1,p_2,\ldots,p_{x+y}=(x,y)$$$, where there exists an index $$$i$$$ such that $$$(p_i).x-(p_i).y=y-k$$$ can be bijected to a good binary string. To prove that this is sufficient, note that by taking every occurrence of North on our path in the future, we have a subsequence of size $$$k$$$. To prove that this is necessary, note that if the longest nondecreasing subsequence in the binary string is $$$a$$$ $$$0$$$'s followed by $$$b$$$ $$$1$$$'s, then we can map the point right after $$$a$$$ $$$0$$$'s to the index $$$i$$$. Now, why is this mapping helpful? We can use the reflection technique to count the number of good paths. Let $$$i$$$ be the first occurrence where $$$(p_i).x-(p_i).y=y-k$$$. Now, reflect the remaining part of the path across the line $$$y-x=y-k$$$. Now we have mapped the number of good paths to the number of paths that arrive to the point $$$(x+y-k, k)$$$. This is similar to the proof of the closed form of Catalan numbers. Let this function be $$$f(x,y,k)$$$.

Now, let's solve the above problem again, but we are given a prefix of the binary string. Let $$$Z$$$ be the number of zeroes, $$$L$$$ be the length of the longest nondecreasing subsequence, $$$x$$$ and $$$y$$$ be the number of zeroes and ones to concatenate, and let $$$k$$$ be the target length of longest nondecreasing subsequence. I claim that the number of ways to finish the binary string is $$$\binom{x+y}{x}$$$ if $$$L+y \geq k$$$ or $$$Z+x \geq k$$$, $$$0$$$ if $$$Z+x+y \lt k$$$, and $$$\binom{x+y}{k-Z}$$$ otherwise. The first two cases are relatively simple to show. We can show the last case because the longest nondecreasing subsequence of the entire string must compose entirely of $$$0$$$'s in the prefix (or else $$$L+y\geq k$$$ would be true), so we can simplify this problem to the above problem as we only need a longest nondecreasing subsequence of $$$k-Z$$$ now. Let this function be $$$g(x,y,k,Z)$$$.

Now, to solve the problem, let's enumerate the length of the common prefix of $$$s$$$ and $$$t$$$, and then the index where the first half first has a longest nondecreasing subsequence length of exactly $$$k$$$ (call this index $$$i$$$). If this point is within the prefix, then we can complete the second half of the sequence directly using the formula we obtained above. There are two cases: either $$$t_i=0$$$ or $$$t_i=1$$$. If $$$t_i=0$$$ and $$$i$$$ is the first index where the longest nondecreasing subsequence has length $$$k$$$, then the longest nondecreasing subsequence must compose of only $$$0$$$'s. In this case, the length of the longest nondecreasing subsequence up to index $$$i-1$$$ must be $$$k-1$$$, and the number of zeroes are also fixed — this is also a direct application of the original formula. Otherwise (that is, if $$$t_i=1$$$), let $$$x'$$$ and $$$y'$$$ be the number of zeroes and ones in this half. At index $$$i-1$$$, the length of the longest nondecreasing subsequence should be exactly $$$k-1$$$. We can calculate this by taking the number of binary strings with LNDS length at least $$$k-1$$$, and subtract the number of binary strings with LNDS length at least $$$k$$$. Note that the number of $$$0$$$'s and $$$1$$$'s in the second half is also fixed (call them $$$x"$$$ and $$$y"$$$ respectively), so we can multiply the previous result by the number of binary strings with LNDS at least $$$k$$$. We can write this as getting the sum $$$(g(x',y',k-1,Z)-g(x',y',k,Z))\cdot f(x",y",k)$$$.

This looks like the solution will become $$$O(n^3)$$$ since we have to loop through all possible $$$x'$$$ values. However, let's look at $$$g(x,y,k,Z)$$$ again. It is $$$\binom{x+y}{x}$$$ if $$$y \geq k-C_1$$$ or $$$x \geq k-C_2$$$ (call this case $$$1$$$) for some constants $$$C_1$$$ and $$$C_2$$$, and $$$\binom{x+y}{k-Z}$$$ otherwise (call this case $$$2$$$). Consider $$$g(x',y',k-1,Z)$$$ and $$$g(x',y',k,Z)$$$. When both functions are in case $$$1$$$, we have $$$g(x',y',k-1,Z)-g(x',y',k,Z)=0$$$. When both functions are in case $$$2$$$, the difference is a constant. The only case we have to worry about is when one function is in case $$$1$$$ and the other is in case $$$2$$$. But note the conditions for case $$$1$$$ — it is either if $$$y$$$ is larger than some constant or if $$$x$$$ is larger than some constant. Thus, when $$$g(x',y',k-1,Z)$$$ leaves case $$$1$$$, $$$g(x',y',k-1,Z)$$$ will also leave case $$$1$$$. Similarly, when $$$g(x',y',k,Z)$$$ enters case $$$1$$$ (when $$$y$$$ becomes too large), $$$g(x',y',k-1,Z)$$$ will also enter case $$$1$$$ in the next iteration. So, we only have to calculate these cases for $$$2$$$ values of $$$X$$$. Combining this with some prefix sums of binomial factors (to deal with the $$$f(x",y",k)$$$ portion when $$$g(x',y',k-1,Z)-g(x',y',k,Z)$$$ is constant), we actually avoid running the loop entirely. Thus, we can calculate the answer in $$$O(n^2)$$$.

340578210