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.