When is it best for the permutation to remain unchanged?

What elements are obviously optimal and should remain as they are?

Find the first non-optimal element. What's the best way to fix it?

Let $$$p_i$$$ be the first element such that $$$p_i \neq i$$$. For the prefix of elements $$$p_1=1,p_2=2, \dots ,p_{i-1}=i-1$$$ we do not need to change anything because it is already the minimum lexicographic, but we would like to have $$$i$$$ instead of $$$p_i$$$ on that position. The solution is to reverse segment $$$[i,j]$$$, where $$$p_j=i$$$.

Notice that $$$i<j$$$ since $$$p_k=k$$$ for every $$$k<i$$$, so $$$p_k<p_j=i$$$ for every $$$k<i$$$.

Time complexity: $$$O(n)$$$.

• Didn't solve
• Good problem
• Average problem
• Bad problem

Replace the condition "$$$a_i+a_{i+1}$$$ is odd" with something easier to work with.

The condition means that we only swap elements of different parity. Now, make some observations.

What happens if there are some elements $$$a_i$$$ and $$$a_j$$$ ($$$i<j$$$) of the same parity, such that $$$a_i>a_j$$$?

If such pair exists, the answer is "NO". Now consider the array to be a merge between two increasing arrays (one with odd elements, one with even elements). Try to prove that the answer is always "YES" in this case.

What does the Bubble Sort algorithm do here? Does it ever do an illegal swap?

The condition "$$$a_i + a_{i+1}$$$ is odd" means that we can only swap elements of different parity. If either the order of even elements or the order of odd elements is not non-decreasing, then it is impossible to sort the sequence. Otherwise, let's prove that it is always possible to sort the sequence. We can for example perform Bubble Sort algorithm. Note that this algorithm only swaps elements $$$a_i$$$ and $$$a_{i+1}$$$ if $$$a_i > a_{i+1}$$$, so it will never swap two elements of the same parity (given our assumption on their order).

Time complexity: $$$O(n)$$$.

• Didn't solve
• Good problem
• Average problem
• Bad problem

Is there any observation you can make on the structure of the components? Ignoring values, how do they look?

Components form subsegments of the array. Don't prove this now. Instead, try to construct the solution by gradually increasing the prefix and storing components in a simple data structure.

Use a stack of pairs. For all current components, store the minimum and maximum elements inside. How do these components merge when the prefix increases?

• Didn't solve
• Good problem
• Average problem
• Bad problem

Solve the problem in reverse.

What are the possible final operations?

They are the $$$2\times2$$$ squares painted in a single color. After finding all such squares, how can you "remove" them from the painting?

When removing a square, the cells below could have been painted in any color. So, mark them as special cells. After running out of squares painted in a single color, what are the new possible last operations?

They are all the $$$2\times2$$$ squares whose non-special cells are painted in the same color. How do we keep track of those while removing squares?

Queue.

• Didn't solve
• Good problem
• Average problem
• Bad problem

First, solve the problem for single-element updates.

Don't actually add to all elements of some color in an update. Instead, just set a reminder that you have to do so. When do you have to be careful?

When you change color, remember to do the addition. Also, don't forget about the already set reminder on the new color. This is currently wrong because you are up to date. How do you fix it?

Moving to the range update problem, use a data structure to maintain maximal ranges colored in a single color. How do these color intervals change during a color operation? What's the actual time complexity?

• Didn't solve
• Good problem
• Average problem
• Bad problem

Consider the ranges of panels covered by the two posters. Split the problem into multiple cases according to how these intervals are positioned relative to eachother. Throughout the solution, consider the concept of "bottlenecks". These are panels that stop the area to be any larger.

First case: the ranges are disjoint. How do you solve this?

Now, for the other cases, make some observations when the posters share some common range of pannels. Consider the heights to be fixed and group panels into two different types.

There are panels that could fit both (let them be grey) and panels that could fit only one (let them be yellow). The shared range of pannels is between two consecutive yellow panels. Moreover, it is bounded by yellow panels in an optimal solution.

Now, consider the heights of the two posters to not be fixed anymore. How many possible maximal ranges of shared panels can there be? They seem to be $$$O(n^2)$$$, but maybe there are less.

Let the shortest panel inside a maximal shared range to be its "representative panel". Starting from such a panel, what ranges does it represent?

It can be proven that the only possible range is the one between the closest shorter panels to the left and right. Now you are able to consider all possible shared ranges because there are $$$O(n)$$$. You can split further into two cases and solve them using two-pointers and possibly some precomputations.

• Didn't solve
• Good problem
• Average problem
• Bad problem