First, let's formalize the statement.

Suppose $$$a_i$$$ is the amount you bet on the $$$i$$$-th outcome. let $$$S = \sum a_i$$$.

You are asked whether there exists an array $$$a$$$ such that $$$a_i \ge 0$$$ and $$$(a_i \cdot k_i) - S > 0$$$ for all $$$i$$$.

Assuming the solution is possible, we want $$$a_i \cdot k_i > S$$$ to hold.

Forget about $$$a_i$$$ needing to be integer and let's fix $$$min(a_i \cdot k_i) = c$$$, and we want to minimize $$$S$$$.

Naturally, the optimal choice is to have each

$$$S$$$ can be computed as $$$\sum \frac{c}{k_i}$$$. This solution works when $$$S < c$$$, i.e. $$$\sum \frac{1}{k_i} < 1$$$. It is not too hard to see that when $$$\sum \frac{1}{k_i} \ge 1$$$, the solution is impossible. A final detail is we can choose $$$c = LCM(k_i)$$$ and this guarantees that all $$$a_i$$$ is integer as required by the problem

For completeness, here is a simple proof of the impossibility :

Rewritten Condition is

Additing the equations up over all $$$i$$$,

giving us our desired result

• Take a small amount of time to formalize the conditions. What is the problem exactly asking for?
• Don't be afraid of a little bit of algebra.
• Rephrasing the problem slightly might lead you to an obvious solution, for example just fixing $$$min(a_i \cdot k_i)$$$ as above, and then asking for minimum $$$S$$$.
• How do we motivate ourselves to fix $$$min(a_i \cdot k_i)$$$ though? Well, look at the equation. It is $$$(a_i \cdot k_i) > S$$$, This implies $$$min(a_i \cdot k_i) > S$$$. We can fix either $$$S$$$ or $$$min(a_i \cdot k_i)$$$ and then maximize or minimize the other quantity respectively, to have the largest chance of satisfying the given inequality.

In a lot of asymmetric game questions, it is useful to consider Alice and Bob's strategies separately.

For example, here Alice's strategy is pretty trivial. Once you have identified a simple strategy, it also becomes easier to analyze the opponent's strategy.

At each step, Alice simply takes the element with smallest value of $$$a_i$$$ which doesn't break her sorted condition.

This is pretty obvious as it doesn't worsen any of her future choices. You can formally prove it with Exchange Argument. Note that while I pass it off as something trivial, if you do not understand Exchange Argument, OR do not immediately see how to prove this with Exchange Arguments, I highly recommend you to check up on it. It will help you understand what greedy algorithms are logical and what are baseless.

Let's now analyze Bob's moves. Bob will want to take all occurrences of some element $$$x$$$ himself before Alice reaches there so as to deny Alice that element $$$x$$$.

Here is a very important pitfall. You might think can't Alice play against Bob's strategy specifically? No, as we discussed before, Alice's strategy is fixed.

For the unconvinced, here is a reasoning you can use : If she tried to take $$$x$$$ herself when she sees Bob taking them, she is unable to take some integer $$$y < x$$$. However, you should be convinced of the claim without needing such reasoning, Alice's optimal move at each step should only be dependent on the current setup and not Bob's previous moves.

Let's remove all elements with $$$freq_i = 0$$$ for convenience, and renumber the remaining elements into $$$1...k$$$. Now, consider the case when Bob wants to deny the sequence $$$x_1, x_2, ..., x_m$$$ from Alice. What is Bob's strategy and when is it possible? Both are very important questions.

Reminder that we have fixed the sequence $$$x_1, x_2, ..., x_m$$$ Bob wants to remove, and we will be discussing optimal strategy wrt that.

Claim 1 : Bob will remove the elements in sorted order, i.e. $$$x_i < x_{i + 1}$$$.

This is not hard to see since Alice will approach $$$x_1$$$ first, then $$$x_2$$$, and so on. Thus, if Bob wants to be able to delete these elements, his best chance is removing them in the same order.

Now, we know Bob's strategy too. Let's look at when he can successfully deny Alice all those elements.

For the first element, $$$freq_{x_1} < x_1$$$ must hold, otherwise Alice reaches $$$x_1$$$ too early (reminder : we have renumbered the elements present in the array to always be $$$1...k$$$ to make these formulae easier)

Similarly, for the second element $$$freq_{x_2} + freq_{x_1} < x_2 - 1$$$ must hold, and in general $$$freq_{x_1} + freq_{x_2} + ... + freq_{x_i} < (x_i - i + 1)$$$ must hold. This is pretty obvious once we know Alice and Bob's strategy.

Ok, so we know what sequences are removable. Now, the dynamic programming becomes sort of obvious.

Let's look at what information we need to store. Consider the subproblem till $$$i - 1$$$ and we want to check if we can add $$$i$$$ to Bob's sequence $$$x$$$ or not. We need $$$2$$$ pieces of information :

• $$$\sum freq_{x}$$$ till now
• $$$|x|$$$ till now

Naively, this is still $$$O(N^3)$$$ states but we can incorporate either of the 2 additional parameters into the $$$dp$$$ state. For example, $$$dp_{(i, j)} = $$$ the minimum value of $$$\sum freq_{x}$$$ considering the first $$$i$$$ elements and $$$|x| = j$$$. (You can do it the other way too, for example $$$dp_{(i, j)} =$$$ the maximum value of $$$|x|$$$ under the constraint that $$$\sum freq_{x}$$$ is $$$j$$$).

If you understood the question, transitions are pretty simple to come up with and are left as an exercise.

• The general idea of separately considering Alice and Bob's strategy is pretty useful.
• When we are asked to find a optimal "possible" sequence, it helps to change the problem into a decision problem first. Writing a dp afterwards, becomes much easier.
• Break the problem into several small parts : for example, here i did $$$4$$$ main things : Alice's strategy, Bob's strategy, decision problem of a sequence $$$x$$$, finally the dynamic programming. If you guess one of the steps, be careful as the entire solution from the start might become wrong due to an error in one step. It helps to carefully analyze each step instead. Making small motivated steps like these helps immensely.
• In dynamic programming problems, the method I use isn't to just randomly guess the correct states, but rather looking at what information we need to store which is sufficient to calculate the answer.
• Considering suboptimal solutions and then speeding them up is very important. Here, specifically i used a dp-specific trick where i went from $$$dp_{(i, j, k)} = $$$ is state $$$(i, j, k)$$$ possible? to $$$dp_{(i, j)} = $$$ min/max $$$k$$$ for a possible state.

All these problems authored by me

• 1943A - MEX Game 1

• https://www.codechef.com/problems/ARRAYGAME (quite similiar statements, completely different solutions)

• 1943E1 - MEX Game 2 (Easy Version) and 1943E2 - MEX Game 2 (Hard Version) (much harder problems but utilizes very similar concepts to the ones used here)

We want to find the length of the longest special subsequence of $$$a$$$. A very natural thought is to first check if it is $$$n$$$ which is the whole array itself.

Let's sort the array. Now, we can easily verify the only case when the answer is not $$$n$$$ is when $$$a_i | a_n$$$ ($$$a_i$$$ divides $$$a_n$$$) for all $$$i$$$. Otherwise, the lcm exceeds $$$a_n$$$ and hence doesn't belong to the array.

This powerful idea highly restricts the nature of "interesting" testcases.

So, assume the answer is not $$$n$$$ now.

Let's look at the divisors of $$$a_n$$$. LCM of any subsequence of $$$a$$$ must be a divisor of $$$a_n$$$ naturally. We know that the number of divisors isn't too large even for a number of the order $$$10^9$$$ (we can prove it is definitely $$$\le 2 \cdot \sqrt{10^9}$$$ but in practise it is much lower, somewhere around $$$2000$$$ probably). Since the number of divisors isn't large, we can try them all.

Let's try to fix the LCM of the subsequence to be $$$x$$$ and then calculate longest sequence. Only try $$$x$$$ such that $$$x$$$ doesn't belong to $$$a$$$ as given in the problem. So, we want to find the longest subsequence $$$b$$$ of $$$a$$$ such that and $$$LCM(b_i) = x$$$.

Obviously, we can simply take all those $$$a_i$$$ which are divisors of $$$x$$$. This guarantees that LCM will be a divisor of $$$x$$$, and this is the longest subsequence since we cannot take non-divisors of $$$x$$$. If even this subsequence fails to have LCM $$$x$$$, it is impossible to obtain it for any subsequence.

Bruteforcing on the LCM solves the problem in $$$O(n \cdot d(A))$$$ where $$$d(A)$$$ denotes the maximum number of divisors of any number $$$\le A (= 10^9)$$$

• Eliminate obvious cases (for example when the answer is $$$n$$$ above). These might even simplify the problem by constraining how the non-obvious tests look like.
• Fixing a parameter and then calculating the answer for that value of the parameter is a useful technique.

Define $$$B_i$$$ as the sum of $$$a_j$$$ where $$$j$$$ belongs to the same component as $$$i$$$.

The given equation is $$$(B_i + B_j) \ge (i \cdot j \cdot c)$$$

Considering all edges seems hard. So, we should try to first consider some special edges. What edges should we try first? Well naturally, an idea is to try those edges with a small value of $$$i \cdot j \cdot c$$$.

Here, you will need to make a claim that you only need edges of the form $$$(1, i)$$$. More specifically, if it is possible to make an edge between $$$(i, j)$$$, it is also possible to make an edge between either $$$(1, i)$$$ or $$$(1, j)$$$. The intuition is there in the previous step that we want to consider edges with the least value of $$$i \cdot j \cdot c$$$, and you must be able to make this small jump.

Proving it is quite simple :

If $$$B_i \ge (i \cdot c)$$$, or $$$B_j \ge (j \cdot c)$$$, we are done.

Otherwise,

for all $$$i, j > 1$$$

Hence, it would be impossible to make an edge $$$(i, j)$$$ if you cannot make edges $$$(1, i)$$$ and $$$(1, j)$$$.

Since, we are only considering edges $$$(1, i)$$$, we want to essentially find an ordering of the $$$n - 1$$$ edges $$$(1, i)$$$ for all $$$i \ge 2$$$ where we are able to add edges in that order.

The condition becomes

at the time of adding edge $$$(1, i)$$$, i.e.

Let's define a new quantity $$$d_i = (i \cdot c) - a_i$$$. Then, if $$$(1, i)$$$ edge is possible right now, and $$$d_j < d_i$$$, then $$$(1, j)$$$ edge is also possible.

This gives us the insight to add edges in increasing order of $$$d_i$$$ since $$$B_1$$$ is an only increasing quantity. Thus, sort the edges $$$(1, i)$$$ according to $$$d_i$$$ and maintain $$$B_1$$$ and check whether each edge is possible or not.

• The most important thing is the motivation behind making claims like we only need edges $$$(1, i)$$$. It might seem like a big jump in logic, but I do not believe it so. It feels very natural to me that we want some equation to hold, we should try to minimize one of the quantities independently of the other. Since we have to make at least one edge $$$(x, i)$$$ for all $$$i$$$, we should consider the case when $$$(x \cdot i \cdot c)$$$ is minimized i.e. $$$x = 1$$$. Proving it is quite easy after we make the claim
• Try to use arguments about the Nature of the Optimal Solution. For example, we used it twice here. First to see that we only need edges $$$(1, i)$$$. Then, to see that we should consider edges in increasing order of $$$d_i = (i \cdot c) - a_i$$$. $$$d_i$$$ is not a randomly plucked quantity, we manipulated some equations and found out $$$B_i \ge d_i$$$ is the condition for adding edge $$$(1, i)$$$. (This is called Separation of Variables fyi, where you split the equation into $$$2$$$ parts, the $$$2$$$ being independent of each other, so that only either the LHS or RHS is dependent on $$$i$$$ while the other part is independent of it)
• Again, formalize(here, simplify) the statement and don't be afraid to do a little algebra. Those are essential skills.

First, let us understand when a permutation is a valid DFS order.

The permutation must begin with $$$1$$$ obviously. After that, the next element must be $$$2$$$ or $$$3$$$. Assuming it is $$$2$$$, we will go on to visit the subtree of $$$2$$$ before coming back up and then going to visit subtree of $$$3$$$.

In general, after visiting a non-leaf node $$$x$$$, we will visit the entire subtree of one of the children of $$$x$$$, and after visiting the entire subtree of its child, we will go on to visit the other child of $$$x$$$.

This gives us the following conditon :

• Condition $$$x$$$ : Let $$$p_1$$$ be the position of $$$x$$$ a non-leaf node, and $$$p_2$$$, $$$p_3$$$ be the positions of the children of $$$x$$$ with $$$p_2 < p_3$$$. Let $$$s$$$ be the subtree size of the child of $$$x$$$. Then, $$$p_2 = p_1 + 1$$$ and $$$p_3 = p_2 + s$$$ must hold.

It is not too hard to see that if the above condition holds for all $$$x$$$, the permutation is a valid DFS order.

We can now solve the problem in $$$O(N \cdot Q)$$$ but we need something faster.

The important note is that our permutation doesn't change significantly throughout operations. Only $$$2$$$ elements gets swapped, so not too many things should be affected.

Let's define $$$bad_x = 1$$$ if Condition $$$x$$$ is false, and $$$bad_x = 0$$$ otherwise. Then, the answer is Yes iff $$$\sum bad_x = 0$$$.

When we swap $$$p_x = b$$$ and $$$p_y = c$$$, we can note that only $$$bad_{b}$$$, $$$bad_{c}$$$, $$$bad_{a_b}$$$, $$$bad_{a_c}$$$ gets affected, as $$$bad_x$$$ only depends on the relative positions of $$$x$$$ and it's children ($$$a_i$$$ is the parent of $$$i$$$).

Thus, we only need to recalculate these values, and this can be easily done in $$$O(1)$$$ time.

This solution generalizes to D2, albeit with much more implementation details.

Also, be careful while implementing this solution. I made a small bug during the contest due to which I skipped to just implementing D2 instead of wasting more time since I had it mindsolved while implementing D1.

The bug is you need to specifically consider only distinct elements in $$$(b, c, a_b, a_c)$$$. Otherwise, it might happen that you add/subtract $$$bad_x$$$ twice and thus get an incorrect result.

278604103

• Try to solve the problem in simpler settings, for example allowing yourself $$$O(N)$$$ time to check the permutation each time. All solutions to this do not generalize however, you can understand what solutions to this easier problem can be adapted to solve the full problem only through experience.
• One tip about extending solutions to simpler versions to queries is that : consider mathematical conditions instead of "processes". For example, i considered conditions on the positions of $$$x$$$ and it's $$$2$$$ children instead of say using DFS itself to check the permutation. Those solutions are usually not generalizable.
• Once we have the condition, it becomes much easier to solve the queries. Usually, it is a matter of being "Chinese" enough, and knowing sufficient tricks.
• The concept of a update not changing much (for example, here only $$$O(1)$$$ items) is very prevalent in a lot of query problems.

We first convert the problem to it's decision variant.

Given $$$n$$$ and $$$k$$$ and a subsequence $$$s$$$ of $$$[1, 2, ... n]$$$, we need to tell if it's achievable.

In each operation, we choose an element $$$x$$$ in $$$s$$$ (call it the 'pivot'), and then $$$k$$$ elements smaller than $$$x$$$ and $$$k$$$ elements larger than $$$x$$$ and delete the $$$2 \cdot k$$$ elements.

I made a mistake in contest because I forgot that elements not part of the final sequence may have acted as pivots too.

Lets write down few necessary conditions :

• $$$n - |S|$$$ must be divisible by $$$2 \cdot k$$$, since we delete $$$2 \cdot k$$$ elements each time

• There must exist at least one element part of $$$s$$$ which can act as a "pivot" for at least one operation. This is because of the nature of the operation. We must have a last operation where the pivot is chosen among the elements of the sequence $$$s$$$. Minor exception : $$$s = [1, 2, .. n]$$$ because we do not perform any operations in this case. More formally, there exists $$$x$$$ in $$$s$$$ such that :

  • There are at least $$$k$$$ elements smaller than $$$x$$$ and not in $$$s$$$
  • There are at least $$$k$$$ elements larger than $$$x$$$ and not in $$$s$$$

Consider only sequences that satisfy the above $$$2$$$ conditions. So, let's assume that a possible pivot of the last operation is $$$i$$$ and there are $$$x$$$ larger elements to be deleted (i.e. not part of $$$s$$$), and $$$y$$$ smaller elements. Let $$$X$$$ and $$$Y$$$ denote the respective sets of larger and smaller elements which haven't been deleted yet (but need to be deleted)

Because $$$i$$$ can act as a pivot $$$x, y \ge k$$$. Note that $$$(x + y)$$$ is a multiple of $$$2 \cdot k$$$.

If $$$x + y = 2 \cdot k$$$, we are done, because $$$x = y = k$$$, and we can choose subsequence = pivot $$$i$$$ + all remaining elements to be deleted.

Otherwise, without loss of generality, let's assume $$$x \le y$$$.

Case 1 : $$$x \ge 2 \cdot k$$$ : Choose subsequence = pivot $$$i$$$ + arbitrary $$$k$$$ elements of $$$X$$$ + arbitrary $$$k$$$ elements of $$$Y$$$. This will reduce each of $$$x$$$ and $$$y$$$ by $$$k$$$.

Case 2 : $$$x < 2 \cdot k$$$ : This is my solution and not necessarily the most optimum one.

• Case 2.1 : $$$(x + y) \ge (6 \cdot k)$$$ : This means $$$y > 4 \cdot k$$$. Choose any $$$2 \cdot k + 1$$$ elements of $$$Y$$$ and do operation, thus reducing $$$y$$$ by $$$2 \cdot k$$$.

• Case 2.2 : $$$(x + y) = 4 \cdot k$$$ : Take $$$(x - k)$$$ elements of $$$X$$$, and $$$(y - k + 1)$$$ elements of $$$Y$$$ (which adds to exactly $$$2 \cdot k + 1$$$). Then, both $$$x$$$ and $$$y$$$ become $$$k$$$.

Every pair $$$(x, y)$$$ is reduced to a smaller pair which still satisfies $$$x, y \ge k$$$. Thus, by Induction, this necessary condition becomes sufficient as it is possible to achieve every subsequence which satisfies the $$$2$$$ conditions.

Let $$$T$$$ denote the sequence of elements to be deleted. Note that we will only count sequences $$$T$$$ such that $$$|T| \mod (2 \cdot k) = 0$$$. Let's assume $$$|T| = x$$$.

Counting the number of valid sequences $$$T$$$ directly is hard. So, let's count it's complement — the number of invalid $$$T$$$.

$$$T$$$ is good if there exists at least $$$1$$$ element $$$y$$$ such that :

• $$$y$$$ doesn't belong to $$$T$$$
• There exists $$$\ge k$$$ elements in $$$T$$$ which are $$$< y$$$.
• There exists $$$\ge k$$$ elements in $$$T$$$ which are $$$> y$$$.

$$$T$$$ is bad if there exists no such element $$$y$$$.

What does the bad condition imply? Starting from $$$T_k$$$ till $$$T_{x - k + 1}$$$, the elements must form a continuous subarray, i.e. all elements $$$y$$$ satisfying $$$T_k \le y \le T_{x - k + 1}$$$ belong to $$$T$$$, otherwise they are possible pivots.

let $$$d_i = T_{i + 1} - T_i$$$, then the condition implies $$$d_k = 1, d_{k + 1} = 1 .... d_{x - k} = 1$$$. Define $$$d_0 = T_1 - 1$$$ and $$$d_x = n - T_x$$$. We have the additional conditions that $$$d_i \ge 0, \sum d_i = (n - 1)$$$, and these are all the constraints with respect to the difference array $$$d$$$.

Now, it's a standard Stars and Bars approach to find the number of difference arrays $$$d$$$.

The solution fixes $$$k$$$ and then $$$|T|$$$, but since we only consider $$$|T|$$$ as multiples of $$$2 \cdot k$$$, the solution is $$$O(\sum \frac{n}{2 \cdot i}) = O(n \cdot log(n))$$$

• Again, considering the decision problem first is a very essential step
• Finding necessary conditions and then analyzing the structure of the problem is a very nice skill. Often times, the necessary conditions become sufficient as we see here (or the reverse way, sufficient conditions become necessary)
• Note that I did not assume that the necessary condition would become sufficient. I was analyzing the structure of sequences which satisfy the necessary condition.
• Reducing problems to subproblems is a very useful method. It is very commonly used alongside dynamic programming especially, but here we used it to apply Induction to prove all such sequences would be reachable
• This is a somewhat guessable problem. I don't deny that. However, I think analyzing structures like I did is much more useful for gaining rating.

• Counting the number of bad ways instead of the number of good ways is a very common trick in combinatorics problems. An even stronger version of the trick is Principle of Inclusion-Exclusion or PIE for short.

Consider the subproblem when the union of the set of intervals is $$$[1, n]$$$, i.e. for every $$$i (1 \le i \le n)$$$, there exists exactly one $$$j$$$ such that $$$l_j \le i \le r_j$$$.

That is, the set of intervals satisfy :

• $$$l_1 = 1$$$
• $$$l_i = r_{i - 1} + 1$$$
• $$$r_m = n$$$

First, let's rewrite the condition given in the statement.

Let $$$k = max(a_i)$$$. Then, the permutation is divided into $$$2$$$ parts : $$$p_i \le k$$$ part and $$$p_i > k$$$ part. Let's assign a $$$0$$$ to all elements satisfying $$$p_i \le k$$$ and a $$$1$$$ to all elements satisfying $$$p_i > k$$$.

The condition given in the statement essentially means that every interval $$$(l_i, r_i)$$$, there exists a $$$x_i$$$ such that for all $$$l_i \le j \le x_i$$$, $$$a_j \le k$$$, and for all $$$x_i < j \le r_i, a_j > k$$$.

Suppose we have a binary sequence $$$a$$$ of $$$0$$$s and $$$1$$$s which satisfies the condition. How do we get the maximum inversions in $$$p$$$ corresponding to the sequence $$$a$$$?

Claim 1 : The number of inversions in the optimal $$$p$$$ corresponding to $$$a$$$ is $$$\frac{n \cdot (n - 1)}{2}$$$ — number of $$$(i, j)$$$ such that $$$i < j, a_i = 0, a_j = 1$$$.

Just with the previous observation on the maximum number of inversions corresponding to a binary sequence $$$a$$$, we can write a dynamic programming, as in the editorial, and we are done. However, please continue reading as I find my approach cool and it can solve the problem with higher constraints.

Suppose we fixed the rest of the sequence $$$a$$$, and we must decide the partition point within an interval $$$(l_i, r_i)$$$, i.e. we must decide a $$$x$$$ such that $$$1 \le x < (r_i - l_i + 1)$$$ and make the first $$$x$$$ elements in the interval $$$(l_i, r_i) 0$$$'s and the rest $$$1$$$'s.

Let's figure out the cost function $$$f(x)$$$ which represents the number of pairs of indices which cannot be inversions with respect to the specific choice of $$$0$$$ and $$$1$$$.

Let $$$b$$$ denote the number of $$$0$$$ in the subarray $$$[a_1, a_{l_i - 1}]$$$ and $$$c$$$ denote the number of $$$1$$$ in the subarray $$$[a_{r_i + 1}, a_n]$$$ (Reminder that we have fixed the entire sequence except for the interval $$$(l_i, r_i)$$$). Let $$$d = r_i - l_i + 1$$$.

Then, the cost function

and we need to find minimum value of the function varying $$$x$$$ from $$$1$$$ to $$$d - 1$$$.

This is a quadratic function with negative coefficient of $$$x^2$$$. This means that it has a central maxima, and then decreasing on both sides, depending on the distance from the central maxima. With some casework on the position of the central maxima, we can conclude that in the allowed interval $$$1 \le x \le (d - 1)$$$, this function is minimized at one of the $$$2$$$ endpoints, i.e. either $$$1$$$ or $$$(d - 1)$$$.

This means that it is optimal to have either $$$a_{l_i} = 0$$$, and $$$a_j = 1$$$ for all $$$(l_i < j \le r_i)$$$, OR $$$a_{r_i} = 1$$$ and $$$a_j = 0$$$ for all $$$(l_i \le j < r_i)$$$.

Applying this for each interval iteratively, we know that an Optimal Solution satisfies this criteria for all it's intervals

Let's call an interval $$$P$$$-type if it has exactly one $$$1$$$, otherwise $$$S$$$-type.

Claim 2 : There exists a prefix of intervals which will be $$$P$$$-type and then the suffix of intervals will be $$$S$$$-type

With this in hand, we can finally solve the problem. Since $$$O(m^2)$$$ works, you can directly bruteforce the prefix of $$$P$$$ type intervals and calculate value according to that.

Returning to the actual problem, there may exist some elements which belong to no intervals. However, they are easy to handle : assign them values maximising the number of inversions. More precisely, check whether assigning them $$$0$$$ or $$$1$$$ gets you more inversions.

Let $$$S$$$ be the set of elements which belong to no intervals. The above argument works only because in the Optimal Solution for all $$$x < y$$$ where $$$x, y$$$ in $$$S$$$, $$$a_x \ge a_y$$$ will hold and they will be an inversion. Otherwise, this argument might not have been correct as the optimum choices might depend on the choices of the other elements in $$$S$$$ themselves.

The above part felt a bit confusing, so I tried to rewrite what It says exactly :

Thus, we can still solve this version in $$$O(m^2)$$$.

This can be extended to the hard version of the problem. Further, this can probably be optimized to $$$O(m)$$$ by quickly calculating the change in answers from prefix of $$$i$$$ intervals being $$$P$$$-type to $$$(i + 1)$$$ intervals being $$$P$$$-type.

The Quadratic function being minimized at the boundaries is a more general observation and can be applied to E2 except now, the boundaries are no longer $$$1$$$ and $$$d - 1$$$. I will leave you to figure out how to extend the solution. There are $$$2$$$ hints below.

Consider the graph where there exists edge $$$j - k$$$ if intervals $$$I_j$$$ and $$$I_k$$$ have non-empty intersection. Work with the connnected components of this graph.

Reduce the problem to this problem :

• The intervals are disjoint (use the previous hint for this)
• Each interval has $$$2$$$ values associated with it, $$$lb_i$$$ and $$$ub_i$$$ such that the valid range of $$$x_i$$$ (the partition point of $$$(l_i, r_i)$$$) must lie in $$$[lb_i, ub_i]$$$.

• Solving subproblems is very useful. Even this entire problem is essentially a subproblem of the main problem. We can find a solution to this and then generalize/extend to there.
• Reducing the problem into something simpler, for example we went from a permutation to a binary array.
• Finding upper/lower bounds on the answer, and then constructing the bounds, proving they are the answer.
• Analyzing the nature of the Optimal Solution. We did it at least twice here
• Algebra, observing stuff about cost functions.

What is the minimum number of bridges to burn if we want to make exactly $$$i$$$ islands visitable from $$$1$$$?

Atleast $$$i \cdot (n - i)$$$ bridges need to burnt (the bridges connecting the $$$i$$$ reachable islands and the $$$n - i$$$ non-reachable islands).

A simple $$$O(n)$$$ solution is for every $$$i$$$ from $$$1$$$ to $$$n$$$, check if $$$i \cdot (n - i) \le k$$$, in which case print $$$i$$$ and break.

What is the answer when $$$k \ge n - 1$$$.

When $$$k < n - 1$$$, is it possible to make any island non-visitable?

When $$$k \ge n - 1$$$, the answer is $$$1$$$ since we can just destroy all bridges $$$(1, i)$$$ for $$$2 \le i \le n$$$.

Otherwise, suppose we tried to make some set of $$$i$$$ islands non-visitable, and the other $$$n - i$$$ nodes reachable from $$$1$$$. Then we need to burn atleast $$$i \cdot (n - i)$$$ bridges (the bridges connecting the $$$2$$$ sets). It is not hard to see that this function attains the minimum value when $$$i = 1$$$ or $$$i = n - 1$$$ for $$$1 \le i < n$$$. Hence the minimum number of bridges to burn always exceeds $$$n - 1$$$.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n, k; cin >> n >> k;
        for (int i = 1; i <= n; i++){
            if (i * (n - i) <= k){
                cout << i << "\n";
                break;
            }
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n, k; cin >> n >> k;
        if (k >= n - 1) cout << 1 << "\n";
        else cout << n << "\n";
    }
    return 0;
}

Group numbers according to how many times they occur in $$$a[1...n]$$$.

The group of numbers having $$$0$$$ occurrences in $$$a[1...n]$$$ is of the same size as the group of numbers having $$$2$$$ occurences in $$$a[1...n]$$$.

Try to use the $$$0$$$ and $$$2$$$ occurrence numbers first, and then if we still need more, we can use the $$$1$$$ occurence numbers. Remember that we have to form sequences of size $$$2 \cdot k$$$ which is even.

We can append any $$$2$$$ occurrence numbers to our sequence $$$l$$$ and any $$$0$$$ occurrence numbers to our sequence $$$r$$$ without any issue because the xor value will cancel out. We do this while our sequence sizes are less than $$$2 \cdot k$$$. At the end of this process, $$$l$$$ and $$$r$$$ will have the same size due to Hint $$$2$$$.

Now, we use as many $$$1$$$ occurrence numbers appending to both $$$l$$$ and $$$r$$$ as needed. Since we append to both sequences, the xor value of the $$$2$$$ sequences will be the same.

If we had to solve for odd sequence sizes, we could take a $$$1$$$ occurrence number at the very start to make it even, and then run the same process, but if there are no $$$1$$$ occurrence numbers at all, we fail with this method.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n, k; 
        cin >> n >> k; 
        k = 2 * k;
        
        vector <int> a(2 * n), occ(n + 1, 0);
        
        for (auto &x : a) cin >> x;
        for (int i = 0; i < n; i++) occ[a[i]]++;
        
        vector <int> g0, g1, g2;
        for (int i = 1; i <= n; i++){
            if (occ[i] == 0) g0.push_back(i);
            else if (occ[i] == 1) g1.push_back(i);
            else g2.push_back(i);
        }
        
        int v = 0;
        for (auto x : g2){
            if (v < k){
                v += 2;
                cout << x << " " << x << " ";
            }
        }
        for (auto x : g1){
            if (v < k){
                v++;
                cout << x << " ";
            }
        }
        cout << "\n";
        
        v = 0;
        for (auto x : g0){
            if (v < k){
                v += 2;
                cout << x << " " << x << " ";
            }
        }
        for (auto x : g1){
            if (v < k){
                v++;
                cout << x << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

Alice can adapt to Bob's strategy. Try to keep that in mind.

Whenever Bob chooses $$$i$$$, and if there are any copies of $$$i$$$ left, Alice can take $$$i$$$ on her next move.

Let $$$f$$$ be the frequency array of $$$a$$$. You can ignore all $$$f(i) \ge 2$$$ due to the previous hint. Now the answer is some simple casework.

For any $$$i$$$ s.t. $$$f_i \ge 2$$$, whenever Bob chooses to remove an occurence of $$$i$$$, on the next move Alice simply chooses $$$i$$$ herself (if she hasn't already taken $$$i$$$ before that). Thus, we only focus on $$$f_i \le 1$$$ now.

The answer is min(first $$$i$$$ s.t. $$$f(i) = 0$$$, second $$$i$$$ s.t. $$$f(i) = 1$$$).

Obviously, Alice can't do better than the mex of array (first $$$i$$$ s.t. $$$f(i) = 0$$$). Further, among $$$f(i) = 1$$$, Alice can save atmost $$$1$$$ $$$i$$$ after which Bob will remove the smallest $$$f(i) = 1$$$ he can find. This is optimal for Bob as well because he cannot do better when Alice removes the (first $$$i$$$ s.t. $$$f(i) = 1$$$) on her first move.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        vector <int> f(n + 1, 0);
        
        for (int i = 0; i < n; i++){
            int x; cin >> x;
            f[x]++;
        }
        
        int c = 0;
        for (int i = 0; i <= n; i++){
            c += (f[i] == 1);
            if ((c == 2) || (f[i] == 0)){
                cout << i << "\n";
                break;
            }
        }
    }
    return 0;
}

When is a string not $$$k$$$-good? (Ignore the trivial edge cases of $$$k = 1$$$ and $$$k = n$$$).

What happens when $$$s[i....j]$$$ and $$$s[i + 1....j + 1]$$$ are both palindromes?

We first try to find the answer for a string

Let $$$k = j - i + 1$$$, $$$s[i....j]$$$ -> I and $$$s[i + 1...j + 1]$$$ -> II are both palindromes.

Then $$$s_i = s_j$$$ (due to I)
$$$s_j = s_{i + 2}$$$ (due to II)
$$$s_{i + 2} = s_{j - 2}$$$ (due to I)
$$$s_{j - 2} = s_{i + 4}$$$ (due to II)
and so on.... you can see that it forces $$$s_i = s_{i + 2} = s_{i + 4} = ....$$$. A similiar reasoning gives you $$$s_{i + 1} = s_{i + 3} = s_{i + 5}$$$.

Further, if $$$k$$$ is even, $$$i$$$ and $$$j$$$ have different parities, but $$$s_i = s_j$$$ implies that all characters must be equal actually.

We mentioned that the edge cases are $$$1$$$ and $$$n$$$, but why exactly? How does the analysis fail for them?(Left as a exercise)

So, the condition for a string to be $$$k$$$-good can be written as follows : $$$k = 1$$$ : never possible
$$$1 < k < n$$$, odd : not an alternating string
$$$1 < k < n$$$, even : not all characters same
$$$k = n$$$ : non-palindromic string

Now onto substring queries. The second and third things are easy to handle, you can store the next position where $$$s_i \ne s_{i + 2}$$$ and $$$s_i \ne s_{i + 1}$$$ respectively. Checking if a substring is a palindrome is standard with various methods such as string hashing or manacher's algorithm.

#include <bits/stdc++.h>
using namespace std;

#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

#define int long long

void Solve() 
{
    int n, q; cin >> n >> q;

    string s; cin >> s;
    auto v = manacher(s);
    for (auto &x : v) x--;

    // we also need to know if all same, and all alternating 
    set <int> s1, s2;
    for (int i = 0; i < n - 1; i++){
        if (s[i] != s[i + 1]) s1.insert(i);
        if (i != n - 1 && s[i] != s[i + 2]) s2.insert(i);
    }

    while (q--){
        int l, r; cin >> l >> r;
        l--;
        r--;

        if (l == r){
            cout << 0 << "\n";
            continue;
        }
        
        int len = r - l + 1;

        int ans;
        auto it = s1.lower_bound(l);
        if (it == s1.end() || (*it) >= r){
            ans = 0;
        } else {
            it = s2.lower_bound(l);
            if (it == s2.end() || (*it) >= r - 1){
                ans = ((len - 1)/ 2) * (((len - 1) / 2) + 1);
            } else {
                ans =  len * (len - 1) / 2 - 1;
            }
        }

        if (v[l + r] < (r - l + 1)) ans += len;

        cout << ans << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Try to solve for line case.

You may have to use more than $$$1$$$ node for certain cases.

Extend the solution for the line to the general tree version (consider the diamater).

For a line, an obvious bound on the answer is $$$\lceil \frac{n}{2} \rceil$$$, as we can colour atmost $$$2$$$ nodes per operation. I claim this is achieveable except for when $$$n$$$ mod $$$4 = 2$$$, where we do $$$1$$$ worse. That is however still provably optimal as you can bicolour the line and operations only colours nodes black which are in the same bicolouring.

Now that we have the solution for the line case, lets divide into $$$2$$$ cases based on parity of diamater (maximum number of nodes on a path) :

diameter mod $$$2 = 1$$$ : Find the centre of the diamater. Then we can simply do operations of the form $$$(centre, i)$$$ (for all $$$0 \le i \le \lfloor \frac{diameter}{2} \rfloor$$$). If this doesn't colour all nodes, then one can easily check that the diamater we found is not the real diamater, as the node which is not coloured is an endpoint of a larger diameter.

diamater mod $$$2 = 0$$$ : Find the $$$2$$$ centres of the diameter. Then the following set of operations satisfy the requirements : $$$(centre1, i)$$$ and $$$(centre2, i)$$$ for all odd $$$i$$$ satisfying $$$1 \le i \le \frac{diameter}{2}$$$. The intuition behind this is to basically split the nodes into $$$2$$$ sets according to a bicolouring, and then $$$1$$$ centre colours all nodes of a certain colour, while the other centre colours all nodes of the other colour.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n;
    cin >> n;
    
    vector<vector<int>> E(n);
    
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        
        u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    
    auto bfs = [&](int s){
      vector<int> d(n, -1);
      d[s] = 0;
      queue<int> Q;
      Q.push(s);
      while (!Q.empty()){
        int v = Q.front();
        Q.pop();
        for (int w : E[v]){
          if (d[w] == -1){
            d[w] = d[v] + 1;
            Q.push(w);
          }
        }
      }
      return d;
    };
    
    vector<int> d1 = bfs(0);
    int a = max_element(d1.begin(), d1.end()) - d1.begin();
    vector<int> d2 = bfs(a);
    int b = max_element(d2.begin(), d2.end()) - d2.begin();
    vector<int> d3 = bfs(b);
    int diam = d3[max_element(d3.begin(), d3.end()) - d3.begin()] + 1;
    //if 3 we want 1, 1 if 4 we want 1 2 
    
    vector <int> ans;
    for (int i = 0; i < n; i++){
        if ((d2[i] + d3[i] == diam - 1) && ((d2[i] == diam/2) || (d3[i] == diam/2))) 
            ans.push_back(i);
    }
    
    if (diam & 1) assert(ans.size() == 1);
    else assert(ans.size() == 2);
    
    vector <pair<int, int>> ok;
    
    if (diam & 1){
        //print everything from 0 to diam/2 
        for (int i = 0; i <= diam/2; i++){
            ok.push_back({ans[0], i});
        }
    } else {
        //2 => 2 ops, 4 => 2 ops , 6 => 4 ops, 8 => 4 ops 
        int ops = ((n - 2)/4) + 1;
        int need = (diam/2) - 1;
        while (need >= 0){
            ok.push_back({ans[0], need});
            ok.push_back({ans[1], need});
            
            need -= 2;
        }
    }
    
    cout << ok.size() << "\n";
    for (auto [u, r] : ok){
        cout << u + 1 << " " << r << "\n";
    }
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
   // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Try to come up with some necessary and sufficient conditions of a good array.

Apply dp once you have a good condition.

All operations which include $$$i$$$ must also either include $$$i - 1$$$ or $$$i + 1$$$. Hence $$$a_i \le a_{i - 1} + a_{i + 1}$$$ must hold. Throughout the editorial treat $$$a_i = 0$$$ for $$$(i \le 0)$$$ or $$$(i > n)$$$.

But, is this sufficient? Infact, it is and we can prove it by strong induction.

Now that we have the condition, we can define a dynamic programming as follows :

$$$dp(i, a, b)$$$ = number of ways to make an array upto the $$$i$$$-th index with $$$a_{i - 1} = a$$$, $$$a_i = b$$$ (since only the last $$$2$$$ elements are relevant).

Let the new element be $$$c$$$, then it is a valid way iff $$$b \le a + c$$$. So we have a $$$\mathcal{O}(n^4)$$$ by iterating over all possibilities.

As a final optimization, we can speed it up to $$$\mathcal{O}(n^3)$$$ by using prefix sums. Note that the valid values of $$$a$$$ for fixed $$$b$$$ and $$$c$$$ satisfy $$$a \ge max(0, b - c)$$$, and hence maintaining prefix sums over $$$a$$$, we can speed it up.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, k, mod; cin >> n >> k >> mod;
    
    vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
    dp[0][0] = 1; // dp[a][b]
    
    for (int i = 1; i <= n + 2; i++){
        vector<vector<int>> ndp(k + 1, vector<int>(k + 1, 0)); // dp[b][c]
        vector<vector<int>> pref(k + 1, vector<int>(k + 1, 0)); // pref[b][a]
        
        for (int b = 0; b <= k; b++){
            pref[b][0] = dp[0][b];
            for (int a = 1; a <= k; a++){
                pref[b][a] = (pref[b][a - 1] + dp[a][b]) % mod;
            }
        }
        
        for (int b = 0; b <= k; b++){
            for (int c = 0; c <= k; c++){
                if (b > c){
                    // a must be atleast b - c 
                    ndp[b][c] = (pref[b][k] - pref[b][b - c - 1] + mod) % mod;
                } else {
                    ndp[b][c] = pref[b][k];
                }
            }
        }
        
        dp = ndp;
    }
    
    cout << dp[0][0] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Try to apply Principle of Inclusion Exclusion (PIE).

You do not need to store both last elements! Only the last is enough.

Since there are $$$n^3$$$ states in our dp, we will have to optimize the number of states somehow.

Let us consider all arrays and not just good arrays. An element is bad if $$$a_i > a_{i - 1} + a_{i + 1}$$$.

Suppose, $$$f(x_1, x_2, ...., x_k)$$$ gave us the number of arrays where each of $$$x_i$$$ are distinct and bad. (Note that other positions may be bad as well). Then, by PIE, the answer is $$$(-1)^k \cdot f(x_1, x_2, ....., x_k)$$$.

For example, for $$$n = 3$$$, we would want to compute $$$f([]) - f([1]) - f([2]) - f([3]) + f([1, 2]) + f([1, 3]) + f([2, 3]) - f([1, 2, 3])$$$. Note that $$$f([])$$$ is simply $$$(k + 1)^n$$$ as there are no restrictions placed on the array.

This has $$$2^n$$$ calculations, so we need to optimize it.

First optimization : obviously, only $$$k$$$ matters and not the exact indices. This means we only have to maintain the count of the number of indices we have made sure are bad.

Second optimization : only parity of $$$k$$$ matters, due to the only dependence of $$$k$$$ being $$$(-1)^k$$$.

We now define $$$dp(i, last, x)$$$ = number of arrays such that $$$a_i = last$$$ and the parity of bad elements (that we know of) till $$$i$$$ is $$$x$$$.

Transitions :

• Without (necessarily) creating a bad element : $$$dp(i, last, x) += dp(i - 1, y, x)$$$ for all $$$0 \le y \le k$$$. We might accidentally create more bad elements, but remember that PIE allows us to not worry about that.

• With creating a bad element : We view it as a transition from index $$$(i - 2)$$$, $$$a_{i - 1} > a_i + a_{i - 2}$$$ for it to bad, so fix $$$a_i = l1$$$, $$$a_{i - 2} = l2$$$, and you get $$$dp(i, l1, x) += dp(i - 2, l2, 1 - x) \cdot (max(0, k - l1 - l2))$$$.
  The $$$max(0, k - l1 - l2)$$$ term comes from the ways to choose $$$a_{i - 1}$$$ such that $$$a_{i - 1} > l1 + l2$$$.

Both the transitions are optimizable with some prefix sums and running totals to get a $$$\mathcal{O}(n^2)$$$ solution.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, k, mod; cin >> n >> k >> mod;
    
    vector<vector<int>> dp(2, vector<int>(k + 1, 0));
    auto prev2 = dp;
    dp[0][0] = 1;
    
    for (int i = 1; i <= n + 1; i++){
        vector<vector<int>> ndp(2, vector<int>(k + 1, 0));
        vector<int> sum(2, 0);
        
        for (int j = 0; j < 2; j++) for (int x = 0; x <= k; x++){
            sum[j] += dp[j][x]; sum[j] %= mod;
        }
        
        for (int j = 0; j < 2; j++){
            int s1 = 0, s2 = 0;
            
            for (int x = k; x >= 0; x--){
                ndp[j][x] += sum[j];  // normal transition
                
                ndp[j][x] += s2; ndp[j][x] %= mod; // with one wrong
                
                s1 += prev2[j ^ 1][k - x]; s1 %= mod;
                s2 += s1; s2 %= mod;
            }
        }
        
        prev2 = dp;
        dp = ndp;
    }
    
    int ans = (dp[0][0] - dp[1][0] + mod) % mod;
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

It might be optimal for Bob to reduce multiple elements at the same time, thus making Alice choose between which element she wants to take.

Suppose you are only checking whether $$$ans \ge i$$$ for now, what would Alice's strategy be?

Try fixing the element that Bob wants to make sure Alice is not able to get. What would be his strategy then?

For now, lets try to see if $$$ans \ge i$$$. This is equivalent to Alice being able to take $$$1$$$ occurence of everything when the game is reduced to numbers $$$[0, i - 1]$$$.

Alice's strategy here is actually easy to find. At every step, Alice will choose the minimum $$$f_j$$$ such that $$$0 \le j < i$$$, and she hasn't chosen $$$i$$$ yet. You can reason this with greedy stays ahead, exchange argument, whatever you want.

This gives us a nice definition of Alice's moves, however we seemingly have to maintain the sorted sequence of $$$f_i$$$ always. But we can actually rewrite Bob's moves such that it does not affect the sorted order of $$$f_i$$$ and always keeps it sorted. Here, by sorted order, we mean some permutation $$$p = [p_1, p_2, ...., p_i]$$$ of $$$[0, i - 1]$$$ such that $$$f_{p_i} \le f_{p_j}$$$ whenever $$$i \le j$$$.

First, instead of subtracting $$$k$$$, we will do $$$k$$$ subtractions of only $$$1$$$. Then, the only case when sorted order can be destroyed is when there exists $$$k1$$$ and $$$k2$$$ such that $$$f_{k1} = f_{k2}$$$ and we do an operation on $$$k1$$$ but $$$k2$$$ occurs before $$$k1$$$ in the sorted order. This issue can simply be fixed by doing the operation on the smallest $$$x$$$ (according to sorted order) such that $$$f_x = f_{k1}$$$.

Now, we have a good way of representing Alice moves. Suppose we fixed the element that Bob "wins" on. Then, Bob's strategy will obviously be to make the frequency of that element as small as possible, but he must make sure to never violate sorted condition. Since Bob will make at most $$$m$$$ moves, you can just simulate his moves.

The main details of the simulation is that you need to figure out upto what index all values will become equal when doing k operations (or nearly equal, off by 1), and then first take all elements to that state. Let $$$w$$$ be the remaining operations from the $$$k$$$ operations after this, and $$$l$$$ the length of the equal sequence. Then you will reduce every frequency by $$$w / l$$$, and finally reduce the first $$$w$$$ mod $$$l$$$ numbers of this sequence. Check the code for more details.

A naive implementation takes $$$O(m)$$$ per move, so $$$O(m^2)$$$ per element we fix => $$$O(m^3)$$$ total to check $$$ans \ge i$$$. With a binary search on the answer, you get $$$O(m^3 logm)$$$. It can be optimized further, but it wasnt needed to pass. Most other polynomial solutions should pass this.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, k; cin >> n >> k;

    vector <int> a(n + 1);
    for (auto &x : a) cin >> x;

    auto check = [&](int x){
        vector <int> b;
        for (int i = 0; i < x; i++){
            b.push_back(a[i] - k);
        }

        sort(b.begin(), b.end());

        for (int fix = 1; fix < x; fix++){
            // this is element where bob wins 

            deque <int> c;
            for (int i = 0; i <= fix; i++){
                c.push_back(b[i]);
            }
            
            assert(c.size() >= 2);

            while (c.size() != 2){
                c.pop_front(); 

                // find suffix which works 
                int sz = c.size();
                int works = 0;
                int sum = 0;
                for (int j = 1; j < sz; j++){
                    // sum(elements of c - current element) 
                    // this shud be >= k 
                    sum += c[sz - j];
                    int loss = sum - c[sz - j - 1] * j;
                    if (loss >= k){
                        works = sz - j;
                        break;
                    }
                }

                int have = k;

                // make everything = c[works]
                for (int j = works + 1; j < sz; j++){
                    have -= c[j] - c[works];
                    c[j] = c[works];
                }

                assert(have >= 0);
                for (int j = works; j < sz; j++){
                    c[j] -= have / (sz - works);
                }
                have %= (sz - works);

                for (int j = works; j < sz; j++){
                    if (have){
                        c[j]--;
                        have--;
                    }
                }

                for (int j = 0; j < sz - 1; j++){
                    assert(c[j] <= c[j + 1]);
                }
            }

            c.pop_front();
            if (c[0] <= 0) return false;
        }

        return true;
    };

    int l = 1, r = n + 1;   
    while (l != r){
        int mid = (l + r + 1) / 2;

        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Instead of doing the check for $$$ans \geq i$$$ in $$$O(m^3)$$$, we will do it in $$$O(m)$$$.

For an array $$$f$$$ of length $$$n$$$. Let $$$s=f_1+f_2+\ldots+f_n$$$ be the sum of the element. $$$f$$$ will be called flat if $$$f_i = \lfloor \frac{s+i-1}{n} \rfloor$$$. That is, it has the form $$$x, \ldots, x, x+1, \ldots x+1$$$. All flat array can be characters by $$$2$$$ integers $$$(n,s)$$$ only.

Imagine simulating Bob's strategy without simulating Alice's moves of removing the first element of the array. For some prefix of the moves, the actual simulation will be a suffix of this simulation. This is because to subtract something from index $$$\leq i$$$, we must have $$$f_{i+1} = f_{i+2} = \ldots = f_n$$$.

As an example, let $$$k=4$$$.

With Alice moves: $$$[1,2,3,5,5] \to [2,3,3,3] \to [1,2,2]$$$

Without Alice moves: $$$[1,2,3,5,5] \to [1,2,3,3,3] \to [1,1,2,2,2]$$$

$$$[1,2,2]$$$ is not a suffix of $$$[1,1,2,2,2]$$$ and is the first time such a thing happens.

Suppose that the first time this happens is after $$$p$$$ moves. Then the resulting array is the flat array $$$(n-p,f_{p+1}+f_{p+2}+\ldots+f_n-pk)$$$. To find the necessary value of $$$p$$$, we can binary search or run $$$2$$$-pointers to check if the suffix of the array can reach $$$f_p$$$ with the amount of subtraction operations till then. (What we basically did is find the suffix of the array that actually gets operated on, since that makes it much more easier to solve)

Then, since the flat array $$$(n,s)$$$ becomes $$$(n-1,s-\lfloor \frac{s}{n} \rfloor - k)$$$, we can figure out whether each flat array evantually becomes a losing or winning state as we can calculate for each $$$n$$$, the minimum $$$s$$$ such that $$$(n,s)$$$ is a winning state.

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
int arr[200005];
int temp[200005];

bool solve(vector<int> v){
    sort(all(v));
    
    rep(x,0,sz(v)) temp[x]=1e18;
    
    int l=1,curr=0;
    rep(x,1,sz(v)){
        curr+=v[x];
        
        while (l<x && (curr-v[l])-(x-l)*v[l] >= l*k){
            curr-=v[l];
            l++;
        }
        
        temp[x-l]=min(temp[x-l],curr-l*k);
    }
    
    rep(x,sz(v),1) temp[x-1]=min(temp[x-1],(temp[x]-temp[x]/(x+1))-k);
    
    return temp[0]>0;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.exceptions(ios::badbit | ios::failbit);
    
    int TC;
    cin>>TC;
    while (TC--){
        cin>>n>>k;
        rep(x,0,n+1) cin>>arr[x];
        
        // solve(vector<int>(arr,arr+n+1));
        // continue;
        
        int lo=0,hi=n+2,mi;
        while (hi-lo>1){
            mi=hi+lo>>1;
            
            if (solve(vector<int>(arr,arr+mi))) lo=mi;
            else hi=mi;
        }
        
        cout<<lo<<endl;
    }
}

Assumption: 0 is the mode of string t. If 1 occurs more times than 0 in t, we will flip all characters of s and t so that 0 is the mode of string t.

Let us say index $$$i$$$ nice if there exists $$$l$$$ and $$$r$$$($$$1 \le l \le i \le r \le n$$$) such that $$$s_i$$$ is the mode of substring $$$t[l,r]$$$.

So we might have some not nice indices $$$i$$$ such that $$$s_i =$$$ $$$\mathtt{1} $$$. We will not have any index $$$i$$$ such that i is not nice and $$$s_i =$$$ $$$\mathtt{0} $$$, as $$$\mathtt{0} $$$ is the mode of $$$t$$$. So, we need to fix the not nice indices.

Now we will start changing some $$$\mathtt{0} $$$ to $$$\mathtt{1} $$$. So it might be possible that in final $$$t$$$, the frequency of $$$\mathtt{1} $$$ is more than that of $$$\mathtt{0} $$$, and $$$\mathtt{0} $$$ is no longer the mode. So should we worry about indices $$$ i $$$ such that $$$ i $$$ was nice in the beginning, and now that we made some flips, $$$ i $$$ may become not nice?

No! It will never be possible.

In case $$$\mathtt{1} $$$ occurs more times than $$$\mathtt{0} $$$ in the updated $$$t$$$, we will have $$$frequency[1] = frequency[0] + 1$$$ and $$$t[1] = t[n] =$$$ $$$\mathtt{1} $$$(we will have such cases for pairs like ($$$s =$$$ $$$\mathtt{011} $$$, $$$t =$$$ $$$\mathtt{100} $$$; for this pair final $$$t$$$ should be $$$t =$$$ $$$\mathtt{101} $$$). So the substrings $$$t[1, n - 1]$$$ and $$$t[2, n]$$$ will have equal numbers of $$$\mathtt{0} $$$ and $$$\mathtt{1} $$$, and thus all indices should be nice. So our claim is that we should change some $$$\mathtt{0} $$$ to $$$\mathtt{1} $$$, without caring about indices $$$i$$$(which were nice initially) becoming not nice such that $$$s_i =$$$ $$$\mathtt{0} $$$.

We can use dynamic programming here.
So let us have $$$dp$$$, such that $$$dp[i][j]$$$ gives the minimum number of flips required to make $$$t[1, i]$$$ friend of $$$s[1, i]$$$ and the maximum suffix sum is $$$j$$$.
String $$$x$$$ is called to be friend of string $$$y(|x| = |y|)$$$, if for every $$$i$$$($$$1 \le i \le |x|$$$), there exists indices $$$l$$$ and $$$r$$$ such that:
1. $$$1 \le l \le i \le r \le |x|$$$
2. $$$x_i$$$ is a mode of the string $$$y[l,r]$$$

Please read hints $$$1$$$ and $$$2$$$ if you haven't as they contain some claims and definitions.

Note that when we find some sum, we add $$$1$$$ when we get $$$\mathtt{1} $$$ and subtract $$$-1$$$ when we get $$$\mathtt{0} $$$.

Suppose we have found $$$dp$$$ values for the first $$$i - 1$$$ indices, and we want to find $$$dp[i][j]$$$ for $$$0 \le j \le n$$$. Now, we need to perform the transitions.

Let us try to have a $$$O(n^3)$$$ solution first, which we can optimise after making some observations.

Take some $$$l$$$($$$0 \leq l \leq i - 1$$$). We will iterate over $$$suff$$$_$$$sum = 0$$$ to $$$n$$$, here $$$suff$$$_$$$sum$$$ is the maximum suffix sum of substring $$$t[1, l]$$$, and use $$$dp[l][suff$$$_$$$sum]$$$ to find optimal values for $$$dp[i][x]$$$ for some $$$x$$$.

So we need to do some flips to substring $$$t[l + 1, i]$$$, as $$$s[1, l]$$$ and $$$t[1, l]$$$ are already friends. So we only care to make all indices $$$j$$$ ($$$l + 1 \le j \le i$$$) nice. So there are two possibilities(either $$$\mathtt{1} $$$ occurs in substring $$$s[l + 1, i]$$$ or not):

1. If $$$\mathtt{1} $$$ does not occur, we can perform the transition without making any flips.

2. Assume $$$\mathtt{1} $$$ occurs in substring $$$s[l + 1, i]$$$. So firstly, find the sum(say $$$cur$$$_$$$sum$$$) of substring $$$t[l + 1, i]$$$. Now, if we do some flips to substring $$$t[l + 1, i]$$$, $$$cur$$$_$$$sum$$$ will change accordingly. We will do a minimum number of flips such that $$$suff$$$_$$$sum + cur$$$_$$$sum \ge 0$$$. Note that we are talking here about updated $$$cur$$$_$$$sum$$$. So we can find the minimum number(say $$$cost$$$) of flips, which will be $$$\lfloor \frac{\max(0, 1 -d )}{2} \rfloor$$$, where $$$d=suff$$$_$$$sum + initial$$$_$$$cur$$$_$$$sum$$$. So we know how many flips to make.

But which ones to flip? Here is one more claim. We should only flip the last $$$cost$$$ $$$\mathtt{0} $$$ of substring $$$t[l + 1, i]$$$.

So this is a sufficient condition, as we can certainly say that $$$t[1, i]$$$ will be friend of $$$s[1, i]$$$ now. So we know the required number of flips, which is $$$dp[l][suff$$$_$$$sum] + cost$$$. We need to find one more thing — what would be the maximum suffix sum if we flip the last $$$cost$$$ characters of $$$t[l + 1, i]$$$? We can precompute.

But we have an issue now. We know that what we performed is sufficient. But is it necessary? What if we did not need to flip cost characters of $$$t[l + 1, i]$$$?

It might be possible that we could have done less number of flips and still made all indices $$$l + 1 \le j \le i$$$ nice. The reasoning behind this is we made sure that $$$suff$$$_$$$sum + cur$$$_$$$sum \ge 0$$$, but what if it was not needed?

Like it is possible that total sum is negative, but all indices $$$j$$$($$$l + 1 \le j \le i$$$) such that $$$s_j =$$$ $$$\mathtt{1} $$$ are satisfied. So here, we can use exchange arguments and conclude that all cases will be covered if we check for all pairs of ($$$l, suff$$$_$$$sum$$$) $$$0 \le l, suff$$$_$$$sum \le i - 1$$$.

Now we need to optimise this to $$$O(n^2)$$$.

Notice that when we do the flips, there will be a suffix(possibly empty when $$$cost=0$$$) of $$$t[l + 1, i]$$$ containing only $$$\mathtt{1} $$$ s. Suppose we are at index $$$i$$$ and need to find $$$dp[i][j]$$$ for $$$0 \le j \le i$$$. We can iterate over all $$$j$$$($$$1 \le j \le i$$$), assume that all the characters in substring $$$t[j,i]$$$ are $$$\mathtt{1} $$$ s, and find the $$$dp$$$ values. Maximum suffix sum will be $$$i-j+1+max$$$_$$$suffix$$$_$$$sum[j-1]$$$. So we can find the smallest index $$$p$$$ such that the sum of the elements in substring $$$t[p,l]$$$ is greater than or equal to $$$0$$$ if we make all the characters in substring $$$t[j,i]$$$ $$$\mathtt{1} $$$.

Notice that we already have the new suffix maximum, and we know the $$$cost$$$ too, which is equal to the number of $$$\mathtt{0} $$$ s in the original substring $$$t[j,i]$$$. So our transition will be $$$dp[i][new$$$_$$$suffix$$$_$$$max]=\max(dp[i][new$$$_$$$suffix$$$_$$$max], \min\limits_{k = p-1}^{i} best[k] + cost)$$$, where $$$best[i]= \min\limits_{k = 0}^{i} dp[i][k]$$$.

So, our final complexity will be $$$O(n^2)$$$, as we can perform the transition in $$$O(1)$$$ if we precompute the needed things.

#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll int
#define pb push_back                  
#define mp make_pair          
#define nline "\n"                            
#define f first                                            
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
const ll MOD=998244353;
const ll MAX=10005;  
ll dp[MAX][MAX];
ll suffix_min[MAX];
ll suffix_max[MAX];
ll can_go_till[MAX][MAX+5];
void solve(){     
    ll n; cin>>n; 
    ll shift=n;
    for(ll i=-n;i<=0;i++){
        can_go_till[0][shift+i]=0;
    }
    string s,t; cin>>s>>t;
    s=" "+s,t=" "+t;
    ll sum=0;
    for(ll i=1;i<=n;i++){
        sum+=2*(t[i]-'0')-1;
    }
    suffix_max[0]=0;
    if(sum>=0){   
        for(ll i=1;i<=n;i++){
            s[i]='0'+'1'-s[i];  
            t[i]='0'+'1'-t[i];
        }    
    }
    ll max_sum=0;
    for(ll i=1;i<=n;i++){
        max_sum+=2*(t[i]-'0')-1;
        max_sum=max(0,max_sum);
        suffix_max[i]=max_sum;
    }  
    for(ll i=1;i<=n;i++){
        sum=0;
        for(ll j=-n;j<=0;j++){
            can_go_till[i][shift+j]=i+1;
        }
        for(ll j=i;j>=1;j--){
            sum+=2*(t[j]-'0')-1;
            ll use=min(sum,0);
            can_go_till[i][shift+use]=j;
        }
        for(ll j=n-1;j>=0;j--){
            can_go_till[i][j]=min(can_go_till[i][j],can_go_till[i][j+1]);
        }
    }
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            dp[i][j]=MOD;
        }
    }
    dp[0][0]=0;
    vector<ll> best(n+5,MOD);
    best[0]=0;
    for(ll i=1;i<=n;i++){
        for(ll l=0;l<=i-1;l++){ 
            dp[i][l+1]=dp[i-1][l]+(t[i]=='0');
        }
        for(ll l=0;l<=i;l++){
            ll new_sum=l+2*(t[i]-'0')-1;  
            if(s[i]=='1' and new_sum<=-1){
                continue; 
            }    
            new_sum=max(0,new_sum); 
            dp[i][new_sum]=min(dp[i][new_sum],dp[i-1][l]);
        }
        suffix_min[i]=MOD;
        for(ll j=i-1;j>=0;j--){
            suffix_min[j]=min(suffix_min[j+1],best[j]);
        }
        ll cnt=0;
        for(ll j=i;j>=1;j--){
            cnt+=(t[j]=='0');
            ll now=i-j+1;
            ll cur_suff_max=now+suffix_max[j-1];
            ll pos=max(0,can_go_till[j-1][shift-now]-1);
            dp[i][cur_suff_max]=min(dp[i][cur_suff_max],suffix_min[pos]+cnt);
        }
        for(ll j=0;j<=n;j++){
            best[i]=min(best[i],dp[i][j]); 
        }
    } 
    ll ans=MOD; 
    s[0]='1';
    for(ll i=n;i>=0;i--){  
        ans=min(ans,best[i]);    
        if(s[i]=='1'){
            cout<<ans<<nline;
            return;  
        }
    }
    return;          
}                                          
int main()                                                                               
{     
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                               
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);      
    freopen("error.txt", "w", stderr);                        
    #endif     
    ll test_cases=1;                 
    cin>>test_cases;
    while(test_cases--){
        solve();
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}