It took days for me to just to barely understand the editorials and from my own opinion, it was so obscure and omitted lot of thing to barely make sense so I had an idea to share my own analysis here for everyone to discuss. Please note this is a wall of text since I want to elaborate on every ambiguous part of editorial and explain my flow of logic as much as possible and for anyone patient enough to read through the end, please share some advice and opinion to optimize and speed up my logic arguments, maybe fixing some typo or request some clarification of my explanation if possible. Thank you for reading.

First about the problem statement, it can be divide into 3 parts :

• Input :

  • A table with size $$$N\times M$$$
  • Each cell is either empty or has a piece on it

• Algorithm 1 : Take a table with pieces on it as input

  • Define the way to move a piece in the table
    • The moving piece can move to the adjacent cell in 4 direction
    • The destination must not already have a piece
  • Choose the sequence of applying the above move to the table so that each row have even pieces and have the least moves
  • If it's impossible, return 0, else return the minimum number of moves

• Algorithm 2 : Take original table $$$N\times M$$$ as input

  • Generate all pair of number $$$0 \lt = L \lt = R \lt = N - 1$$$
  • Each pair of number $$$L, R$$$, generate a table $$$(R - L + 1) \times M$$$ :
    • That's a table created by removing the first $$$L$$$ rows and last $$$N - 1 - R$$$ rows of original table
  • Sum up all the value as the result of applying Algorithm 1 to every generated tables, return that value

The problem asked what is the value of Algorithm 2

First we will try to study Algorithm 1, we will want to keep track of the path of each piece moving through to table. Define the track of piece $$$a$$$ on the table as : The ordered list of cells such that number of elements of the list is number of moves performed on piece $$$a$$$ plus 1, and the $$$i^{th}$$$ cell on the list is the location of $$$a$$$ after applying the $$$i^{th}$$$ move on it.

The number of moves is the total size of all the list (minus one on each list). Next because we only care about parity, each track will change the parity of the row of the first and last cell, so I will try to reduce the complexity by trying this algo : (algo 3)

• Find a row with at least 2 track that end or begin on it, (if there are none, terminate)
• Unite those 2 into one track :
  • Supposed we have track $$$a$$$ and $$$b$$$
  • If track $$$a$$$ begins on the row while $$$b$$$ ends on it, remove the first element of $$$a$$$ and append it to the end of $$$b$$$.
  • If both track begin on it, reverse track $$$b$$$, remove last element of track $$$b$$$ and append $$$a$$$ to the end of $$$b$$$
  • Other case deal similarly

After this reduction, each row has at most one track start or end on it, and number of moves in the pieces moving process still equal to total size of every track minus 1 for each track. Since the table ends up with every row has even pieces, only odd rows has a track begin or end on it. From this we can make a new definition :

• A row numbered $$$a$$$ is matched with row numbered $$$b$$$ if there is a track connect a cell on row $$$a$$$ and $$$b$$$ (4)

So we have a relation :

A way to moves pieces to make all rows even $$$= \gt $$$

• A match between odd rows that :
  • There exist a track of cells between each matched pair
  • Adjacent cells on the track is either adjacent cell or share a same rows
  • Sum of size of all track minus 1 for each track equals number of moves to move pieces

(*0) A track of the matched rows $$$a$$$,$$$b$$$ clearly has size at least $$$\lvert a-b \rvert$$$ + 1 (fact 1) , so the number of moves has a lower bound $$$\sum_{condition \,A}(\lvert a-b \rvert)$$$ $$$ \gt =$$$ $$$\sum_{condition \,B}(\lvert a-b \rvert)$$$ with the conditions is :

• $$$A$$$ : $$$a,b$$$ is matched by algo (3) and condition (4)
• $$$B$$$ : $$$a,b$$$ is matched to minimized the above sum

It's easy to see that Condition $$$B$$$ is equivalent to : Rows $$$a,b$$$ is matched so that there are no odd rows between $$$a,b$$$ and there are even number of other odd rows to the left and right of $$$a,b$$$. But can this lower bound achievable ? Not always, and this is a dead end if we want to expand our approach from this point on, so we will track back the logic route from here.

The above lower bound come from the other lower bound lower bound by condition $$$A$$$, which is induced from the lower bound (fact 1) and we will try to study this lower bound.

A track of the matched rows $$$a$$$,$$$b$$$ has size at least $$$\lvert a-b \rvert$$$ + 1, PLUS the number of cells that is outside of row $$$a,b$$$, PLUS the number of adjacent pair of cells in the track that lies on the same row between $$$a, b$$$.

So we study the track that connect row $$$a$$$,$$$b$$$. We will assume that we won't move outside of the rows between $$$a$$$,$$$b$$$ in the track of the optimal pieces moving strategy ( NOTE 1 ). From algo 3 that track come from the union of some number of pieces moving track and since the union track won't go outside the rows between $$$a$$$,$$$b$$$, so does the pieces moving track. So we have a set of pieces moving tracks and their contribution to the total moves counting is the sum of their size minus 1 for each track, representing the moves performing on each piece. The sum should be at least $$$\lvert a-b \rvert$$$ since the union of the track by algo 3 is a track connecting row $$$a, b$$$ and must pass through all the track between them. We will study when does the sum achieved $$$\lvert a-b \rvert$$$. That would be when the moving piece track never move horizontally and any two moving piece track does not have 2 cells lies in same a row unless those 2 cells is the beginning, ending of those track. (*1)

From the observation above we naturally can built a strategy to move a piece on a column from a row that has it to another row that doesn't have it : Supposed at column $$$i$$$, row $$$a$$$ has a piece while row $$$b$$$ doesn't, do the algo $$$move(i, a, b)$$$ :

• Mark the empty cell of row $$$b$$$ at column $$$i$$$
• Until row $$$a$$$ has no piece on column $$$i$$$
  • There is currently a marked empty cell at column $$$i$$$ from a row between $$$a,b$$$
  • Look through the direction from row $$$b$$$ to $$$a$$$ from the marked cell, there would be at least a cell with piece since row $$$a$$$ still has a piece on it
  • Choose a cell with a piece closest to marked empty cell observed, move piece from that cell to marked empty cell and the cell has its piece moved became empty and we choose it as a new marked empty cell.

Easily see $$$move(i, a, b)$$$ only change the piece placements of row $$$a,b$$$, and if row $$$a,b$$$ differ in at least one column $$$i$$$. And apply this strategy repeatedly optimally can generate the set of track that follow structure (*1) so there are a high chance we only need to study this algo to study the condition to have structure (*1) feasible and $$$\lvert a-b \rvert$$$ lower bound.

First we immediately see if row $$$a,b$$$ differ at column $$$i$$$, we apply $$$move(i, a, b)$$$ or $$$move(i, b, a)$$$ immediately and reach the lower bound. So supposed row $$$a, b$$$ has the same piece placement.

The structure (*1) can be reached by performing some $$$move(...)$$$ algo and since no 2 track overlapped beside their endpoint, the $$$move(...)$$$ algorithm only perform on the set of pairs of rows such that no two pairs made overlapped their row interval made by rows between them beside their endpoints.

From that we can study the structure of set of pair of rows to perform $$$move(...)$$$ and deduce that there is a strategy we can perform the first $$$move$$$ algo is between row $$$a$$$ and some row $$$c$$$ between $$$a,b$$$. If after this $$$move$$$ cost $$$\lvert a-c \rvert$$$, row $$$a$$$ become even, row $$$c$$$ become odd. If row $$$c$$$ piece placement is different than row $$$b$$$ (which is also row $$$a$$$ original) placement then just perform $$$move$$$ on $$$c,b$$$ and the lower bound $$$\lvert a-b \rvert$$$ reached. Else row $$$c$$$ initially just differ from row $$$a$$$ one position and now row $$$c, b$$$ has the same piece placement, apply the same process with them and continue on. We see that eventually we have to find a row $$$p$$$ that differ from $$$a$$$ and $$$b$$$ at least 2 slots $$$i, j$$$ column, and if it exists, we can just perform $$$move(i, a, p)$$$ and $$$move(j, p, b)$$$ to reach to lower bound $$$\lvert a-b \rvert$$$.

So the condition for the match between row $$$a, b$$$ does not reach lower bound $$$\lvert a-b \rvert$$$ is : (5)

• Row $$$a, b$$$ has same pieces placement
• Every row between them differ from them exactly 1 piece placement in one column

For each matched row $$$a, b$$$ like that, we need an additional horizontal move to break the condition so we will need $$$\lvert a-b \rvert + 1$$$ moves ( NOTE 2 ). So the (*0) lower bound can be fixed as : the number of moves has a lower bound $$$\sum_{condition \,A}(\lvert a-b \rvert + ck(a,b))$$$ $$$ \gt =$$$ $$$\sum_{condition \,B}(\lvert a-b \rvert + ck(a,b))$$$ with the conditions is :

• $$$A$$$ : $$$a,b$$$ is matched by algo (3) and condition (4)
• $$$B$$$ : $$$a,b$$$ is matched to minimized the above sum
• $$$ck(a,b)$$$ check if row $$$a,b$$$ sastified condition (5) or not

To study condition $$$B$$$, we will try to exchange process between 2 matched pair. Supposed pair $$$(a,b)$$$ and $$$(c,d)$$$ is matched, their contributed sum is $$$\lvert a-b \rvert + ck(a,b) + \lvert c-d \rvert + ck(c,d)$$$. One can easily see that if the interval $$$[a,b]$$$ and $$$[c,d]$$$ overlapped at a point beside their endpoints, like assuming $$$a \lt c \lt b \lt d$$$, we have $$$\lvert a-b \rvert + \lvert c-d \rvert$$$ $$$=$$$ $$$\lvert a-c \rvert + \lvert b-d \rvert + 2\lvert b-c \rvert $$$ $$$ \gt =$$$ $$$\lvert a-c \rvert + \lvert b-d \rvert + 2$$$ so $$$\lvert a-b \rvert + ck(a,b) + \lvert c-d \rvert + ck(c,d)$$$ $$$ \gt =$$$ $$$\lvert a-b \rvert + \lvert c-d \rvert$$$ $$$ \gt =$$$ $$$\lvert a-c \rvert + \lvert b-d \rvert + 2$$$ $$$ \gt =$$$ $$$\lvert a-c \rvert + \lvert b-d \rvert + ck(a,c) + ck(b,d)$$$. So matched $$$a, c$$$ and $$$b, d$$$ yield a not worse result. From that logic there is a optimal match that minimize the sum so that between each matched pair there are no other odd row.

So we found the optimized form of match and the result of Algorithm 1 can be deduced as follow (algo 5)

• If there are odd odd rows, return 0
• Else supposed the first 2 odd row is $$$a,b$$$, add $$$\lvert a-b \rvert$$$ to answer and add 1 if $$$a, b$$$ sastified condition (5), remove that 2 rows and repeating until no rows left.
• Return the answer

Is it done ? There are two grave mistake I made got noted that will invalidate my logic. But first let me introduce some logic framework I used when approaching this kind of problems. The general problem of Algorithm will use a set of object $$$X$$$ as an input, an grader algorithm $$$f$$$ and ask me : If for each element in $$$X$$$, grade them with $$$f$$$, what is the optimal result ?

Applied for Algorithm 1, $$$X$$$ is set of sequence of legit moves in the problem statement that end with every row in the table having even pieces, and $$$f$$$ count number of moves in such sequence. I will have some approach :

• Study the optimality of $$$f$$$ interacted with each element of $$$X$$$, build some optimization algorithm that expected to failed when performing on an optimal element of $$$X$$$ regarding $$$f$$$, use the conditions to filtered out non-optimal elements of $$$X$$$, the set $$$X$$$ will then got filtered out into subset $$$X'$$$ with additional condition and changed structure I can work on (Apr 1)
• Or if $$$f$$$ is a complex grader required to change the elements it interacted on through multiple state (like counting number of moves in the sequence, is actually an algorithm that applied the sequence moves to change the table through multiple state, each state check if the move is valid and in the end check if all the row is even). I can first build some conditions to filter out $$$X$$$ into some simpler structure set $$$X'$$$ then build a simpler grader $$$f'$$$ that can be applied more versatile that would return the same result as grader $$$f$$$ on each element of $$$X'$$$ and not worse result on each element of $$$X$$$. To prove $$$f'$$$ produce not worse result on each element of $$$X$$$, prove that on each state after $$$f$$$ change a element of $$$X$$$ the more versatile $$$f'$$$ return the worse result than before. For example $$$f'$$$ I deduced of this problem would be algo 5. (Apr 2)

The first mistake I made is NOTE 1, I assume there always is an optimal solution where we only move between matched row but there isn't. I just assumed that without proving since I'm approaching that part as Apr 2, so in a sense it was not that much of a mistake. The true mistake is the NOTE 2 where I assume one horizontal move can fix the difficult scenario. If $$$M$$$ is odd and both row $$$a, b$$$ is a full row pieces then there are no room to move pieces horizontally, and even the row between them with $$$M - 1$$$ pieces, move one piece horizontally they still differ from $$$a, b$$$ one piece. One simpler mistake like that break my logic apart, but in the case $$$M$$$ is even that mistake won't applied, my logic is still valid and the argument above deals with Algorithm 1 efficiently to prepare optimization for Algorithm 2. So I will divide the problem in 2 case of $$$M$$$ even and odd which is what the editorial has done in the first place

The editorial introduced the definition of balls and holes which I didn't understand for sometime. From what I understand, every odd rows single out a piece and for every row counting maximum number of pair of pieces that can occupied empty slot on it (the singled pieces counted as a part of occupied-empty-slot pair of pieces). And then on the editorial treat the optimal solution as simply sending pair of pieces, each from a row of a pair matched odd row, to an avaiable double slot on the same row. But in situation like row 1 and 3 both have 1 pieces and row 2 has 4 pieces, we clearly would send 2 pieces from row 2 to row 1 and 3 each and row 1 and 3 would be matched with each other. So how do we define holes of matched pair (1,3) in that case ? Should we assume there would always be an optimal solution that send a piece from each row of a matched pair of row to a same row (aka hole) and use approach Apr 2 ? But the example I mentioned earlier doesn't have any way to send piece from row 1 and 3 to row 2 if row 1, 2, 3 all have a piece in column 0.

After some though I find a way to build a argument process that would validate the ball-hole matching process. We will build a biparte graph with ball and hole. For each odd row, we will associate it with a unique ball node with recorded number of row it got created from the table the in the bipartite graph, other even rows will associate no balls. Each row r will also calculate a function $$$count(r) = (M - 1 - c') / 2$$$ with $$$c'$$$ is the maximum even number not larger than number of pieces currently on row $$$r$$$ and associate it with $$$count(r)$$$ holes, each holes recorded number of row associated with it in the bipartite graph. Each time we move a piece vertically from row $$$a$$$ to $$$b$$$, do the following :

• If row $$$a$$$ is currently odd and currently associated with ball $$$t$$$

  • If row $$$b$$$ is currently even, row $$$a$$$ will become even and $$$b$$$ become odd, reassociate $$$b$$$ with $$$t$$$ and unassociate $$$a$$$ $$$t$$$.
  • If row $$$b$$$ is currently odd and associated with ball $$$q$$$, row $$$b$$$ must be currently associated with at least one hole ($$$count(b)$$$ $$$ \gt =$$$ 1) for a piece in $$$a$$$ to move over. Choose one hole $$$h$$$, create two red edges from balls $$$t, q$$$ to hole $$$h$$$. After this $$$count(b)$$$ will be reduced by 1, unassociated $$$h$$$ with row $$$b$$$, both row $$$a,b$$$ become even so remove their association with their balls.

• If row $$$a$$$ is currently even, create 2 new additional balls $$$x$$$, $$$y$$$ that memorized their row of creation and the other balls they got created with, also add a new hole $$$d$$$ and add two white edges from $$$x, y$$$ to $$$d$$$ in bipartite graph. Choose one of the balls $$$x, y$$$ to move to $$$b$$$ and deal similarly as above.

After all the moves that even out all the rows and unassociated it with all the balls, we have one bipartite graph that :

• An original ball has exactly 1 red edge
• An additional ball has exactly 1 red and white edges
• An original hole has 0 or 2 red edges, while an additional hole has 2 white edges and possibly 2 red edges

Now if there are an additional hole has 2 white edges, that means we created an additional hole but doesn't move any ball pair into it so it's useless. Erase that hole and its white edge to its additional balls. Now for additional hole with 2 white edges and 2 red edges, unite 1 white edge to 1 red edge in pair to form a path. With each additional ball with 2 edges, we also unite them. After finishing this process the graph will become set of path and cycles formed by united pairing of edges. Consider each ball that has exactly 1 edge, it must be the beginning of some path that end at an original hole since reaching an additional hole through red edge, we always go out of it by an white edge to an additional ball and in turn go out of that ball through a red edge to other hole.

So each path $$$x$$$ start with a ball with 1 red edge, ends at an original hole $$$c$$$ and each original hole $$$c$$$ is in 2 paths, since it has 2 red edges, that start at balls $$$x, y$$$ with 1 red edge. That make up a collection of tuple $$$(ball\, x,\, hole \, c,\, ball\, y)$$$, corresponding to the process of matching in pair the odd rows and match each pair of matched rows to a hole. In the scenario where an original ball $$$x$$$ got paired with an additional ball $$$z$$$, there would be an additional ball $$$z'$$$ that got created at the same time with $$$z$$$ and match to a ball $$$y$$$ so we can combine 2 tuple $$$(x, c, z)$$$ and $$$(z', c', y)$$$ into $$$(x, c, y)$$$ and remove $$$z, z'$$$ out of the match. (alg 4)

So in conclusion a way to move pieces to make all row even can generate a process of matching in pair the odd rows and match each pair of matched rows to a hole in the table which consistent with the editorial. We can easily see that from the structure of generated tuples, number of moves has a lower bound of summing over all tuples $$$(x, c, y)$$$, how many move to move from row $$$x$$$ to row $$$c$$$ and row $$$y$$$ to row $$$c$$$, which is at least $$$\lvert c-x \rvert + \lvert c-y \rvert$$$, and the appearance of row $$$c$$$ across all the tuple matching is at most $$$count(c)$$$

Now I can confidently use Apr 2. First I put some conditions on the set of candidate pieces moving strategy : That's all the strategy with their tuples generated by aglo 4 follow conditions (6)

• A tuple $$$(x, c, y)$$$, if $$$c$$$ is outside of range $$$x, y$$$ then there is exactly $$$\lvert c-x \rvert + \lvert c-y \rvert$$$ moves involving $$$(x, c, y)$$$ pieces moving operation
• A tuple $$$(x, c, y)$$$, with $$$(x, y)$$$ satisfied condition (5) and there is at least 1 hole inside them and no other pair of rows got match to a hole in a row inside range $$$x, y$$$, then there is an additionally 1 extra move.

First condition actually the pair of row still have to pay 1 extra horizontal move when their pieces move to a hole outside their range while condition 5 for every rows involved the movement still applied. But those pair of rows will prefer moving to a hole inside their range and there is unlikely that condition 5 will apply even if they got forced outside, so we will ignore it for now (Inserting Freeza meme). Second condition come from the fact that the sub-table of rows that sastified condition (5) cannot be resolved on their own without outside intervention or 1 extra horizontal move. Actually the piece movement from outside if doesn't got condition (5) applied to all the rows involved then it doesn't have to pay an extra 1 move, but the scenario where row $$$x, y$$$ have a hole between them unmatched but that pair go match outside is suboptimal, and if they has no hole between them meaning both $$$x, y$$$ is full row and all row between them has exactly $$$M - 1$$$ piece, and the rows they try to send a pair of pieces to will have at least 3 empty slot avaiable which unvalidate condition 5. So the inconsistent scenatio won't happen and we will just assume the condition to compute extra moves more easily later.

Now I will study the structure of tuple $$$(x, c, y)$$$ matching. The final total cost of the matching only cares about the distance travel from $$$x, y$$$ to $$$c$$$ and penalty cost from evaluating which row has a hole matched and which pair of matched rows has some holes inside their range matched. By some simple observation we see that if there is a tuple $$$(x, c, y)$$$ and $$$(x', c', y')$$$ with $$$c \gt = c'$$$ then we can exchange the match such that $$$min(x, y) \gt = max(x', y)$$$ so that the distance travel doesn't get worse, and $$$c, c'$$$ still has a hole match and there are at most 2 pair of rows got affected when assessing there is a hole inside their range matched, so the penalty cost increase at most 2, but we can also prove that in those circumstance where penalty cost increase 2 the distance cost decrease least 2 by calculating edge-case so the total cost won't increase. So we can add one condition to (6)

• If there are tuples $$$(x, c, y)$$$ and $$$(x', c', y')$$$ with $$$c \gt = c'$$$ then $$$min(x, y) \gt = max(x', y)$$$ (7)

From (7) we easily see that if there is a tuple $$$(x, c, y)$$$ then there are no odd rows between $$$x, y$$$ because it will be matched to a hole in row $$$c'$$$ which is either to left or right of $$$c$$$, making that odd row lie outside of the range. So we have new condition :

• If there are tuples $$$(x, c, y)$$$, the are no odd rows between $$$x, y$$$ and even numbers of other odd rows on both of their left and right side (8)

So how the pair row aka balls got matched is determined, we will study how to match them with hole. Note that the row matched is already determined so the penalty cost will be decided solely on which holes is matched (Obv 1). A ball is pair of row $$$(x, x)$$$ need to travel to row $$$c$$$ can be represent as $$$\lvert y-x \rvert + 2 \times min(\lvert c-x \rvert, \lvert c-y \rvert)$$$ if $$$c$$$ is outside of range $$$[x, y]$$$ or just $$$\lvert y-x \rvert$$$ if it's inside. (Algo 6)

So after sum out all the determined $$$\lvert y-x \rvert$$$, we need to find the matching that minimize sum of penalty cost and the distance cost to pair calculate by : If hole in row $$$c$$$ is outside pair of matched row $$$(x, y)$$$ then distance is $$$2 \times min(\lvert c-x \rvert, \lvert c-y \rvert)$$$, else it's $$$0$$$.

So we will try to match a set of balls present as pair of row $$$(x, y)$$$ to the hole present as a row $$$c$$$ it's on. At this stage the editorial decided to transform the pair of row $$$(x, y)$$$ with holes $$$x \lt = h_1 \lt = h_2 \lt = ... \lt = h_m \lt = y$$$ inside it to set of 2 balls $$$(x, x), (y, y)$$$ and some holes $$$(x, h_1), (h_1, h_2), ..., (h_m, y)$$$, also treat another hole row $$$c$$$ as hole $$$(c, c)$$$. I don't know what is the intuition behind such drastic change, just transform it to matching on the line is too weak reason for me since this transformation is too complex to come up in the first place so it will be great help if someone can explain the logic behind this, but for now I can at least explain why this alternatives graph minumum cost matching correspond to the straight-forward matching pair of rows balls and one row hole graph.

Study how to match a ball $$$(x, y)$$$ such that there are holes $$$h_L, ..., h_R$$$ inside it.

Supposed ball $$$(x, y)$$$ is matched with hole $$$h$$$ inside it and by condition (7) holes $$$a_1, a_2, ..., a_l$$$ and $$$b_1, b_2, ..., b_l$$$ inside of $$$(x, y)$$$ to the left and right resp to hole $$$h$$$, got matched so that holes $$$a_i$$$ matched to ball $$$(x_L, y_L)$$$ to the left of $$$(x, y)$$$ and $$$b_i$$$ to ball $$$(x_R, y_R)$$$ to the right of $$$(x, y)$$$. In the transformed graph it will be treated as ball $$$(x, x), (y, y)$$$ matched to holes $$$(x, h_L), (y, h_R)$$$, holes $$$(a_i, nxt(a_i))$$$ matched to ball $$$(x_L, y_L)$$$ or $$$(y_L, y_L)$$$ depending $$$(x_L, y_L)$$$ got transformed or not, same with hole $$$b_i$$$ (fucntion $$$nxt(a_i)$$$ return the nearest hole to the right of $$$a_i$$$ in the holes sequence $$$h_L, ..., h_R$$$ which is to the left or equal to $$$h$$$ in the sequence by condition (7)).

Supposed ball $$$(x, y)$$$ is matched with hole $$$h$$$ to the right, in the transformed graph ball $$$(x, x)$$$ matched to $$$(x, h_L)$$$, $$$(y, y)$$$ to $$$(h, h)$$$, and $$$(a_i, nxt(a_i))$$$ matched to ball $$$(x_L, y_L)$$$ or $$$(y_L, y_L)$$$ as above.

By observing the optimal matching in transformed graph also follow condition (7), we can deduce an optimal matching from original graph via an optimal matching in transformed graph. Note an additional condition for transformed graph that at least one of ball $$$(x, x), (y, y)$$$ is matched with their corresponding hole $$$(x, h_L), (y, h_R)$$$. Since if it's not, supposed ball $$$(x, x)$$$ matched with a hole $$$L$$$ to its left and hole $$$(x, h_L)$$$ matched with ball $$$B_r$$$ to the right of $$$(x, y)$$$ by condition (7), since this is the only scenario where switching hole to match $$$(x, x)$$$ with $$$(x, h_L)$$$ will increase cost. Similarly ball $$$B_l$$$ to the left matched with $$$(y, h_R)$$$, we will switch the holes of balls $$$B_l, B_r$$$ to yield better result, so it's a contradiction.

The transformed graph deal with disjointed set of intervals and we checked that transformation is legit, we can also easily check conditions (6), (7), (8) and (Obv 1) still can apply to find an optimal solution. Now we represent a ball interval as sign $$$-$$$, hole interval as sign $$$+$$$, we need to match all the $$$-$$$ with $$$+$$$. Now we free the set of optimal solution in transformed graph from condtion (7) and sort all the non crossing intervals naturally with tie-breakers that two elements with having intervals representation will have a $$$+$$$ ones stand to the left of the $$$-$$$ (this will be important later) to apply a conviennent observation :

• There exist a optimal solution that if a + interval $$$a$$$ matched with a — interval $$$b$$$, there is equal number of + and — between those 2 intervals.

If there is more — than + , a $$$-$$$ inside $$$[a, b]$$$ range must match to a $$$+$$$ outside, then we exchange those two match to yield a not worse solution. If there are more + than -, if a $$$+$$$ match outside we deal similarly as above, or a $$$+$$$ is unmatched then we just match $$$b$$$ to that $$$+$$$ and make $$$a$$$ unmatched. We can easily prove this optimization algorithm will eventually end. So we can add another condition (9) :

• If a + interval $$$a$$$ matched with a — interval $$$b$$$, there is equal number of + and — between those 2 intervals.

Now we consider between a matched $$$+$$$ and $$$-$$$ there is equal number of $$$+, -$$$. We first build a stack-like algo that processing elements from left to right to classify all the pair of $$$+, -$$$ that related by the condition there is equal number of $$$+, -$$$ between them (the editorial called this cumulative sum which I don't understand since this clearly is not) : (algo $$$stk$$$)

• Prepare a stack and choose an initial height $$$H$$$
• Process +, — intervals from left to right. When process an interval
  • If the stack is empty, height of that element is $$$H$$$, put it in the stack
  • If the last element of stack is the same sign as the processing interval, height of the processing element is height of the last element in stack + 1 if the sign is $$$+$$$ or -1 if not, put it in the stack
  • If the last element of stack is the same sign as the processing interval, height of the processing element is height of the last element in stack, remove the last element in stack.

By restricting the optimal solution using (6), (8), (9) we see that only element of the same height can be matched to each other, the +, — intervals of a same height also have no adjacent element with same sign, basically it's in the form $$$...+-+-+-...$$$. Also assuming the last element has height $$$E$$$, the first element is height $$$H$$$ as above, then $$$E \gt = H$$$ and every height between $$$E, H$$$ has 1 more $$$+$$$ than $$$-$$$, except height $$$E$$$ and $$$H$$$ when first and last element resp is a $$$-$$$ interval. Every other height has the same number of $$$+, -$$$

Study how to match interval at same height with equal number of $$$+, -$$$, first we can see that first $$$+$$$ interval should be match with first $$$-$$$ by some exchange matching argument that perseve the set of $$$+$$$ interval match so the penalty is unchanged. Remove those intervals and continue on, the match can be describe as an simple algo 7 :

• Sort all the $$$+$$$ and $$$-$$$ intervals, match $$$i^{th}$$$ $$$+$$$ with $$$i^{th}$$$ $$$-$$$ interval

So the matching is unique if number of $$$+$$$ is equal to $$$-$$$. If there is 1 more $$$+$$$ than $$$-$$$, the interval sign sequence will look like $$$+-+-+...-+-+$$$ with element changing from $$$+$$$ to $$$-$$$ that start and end with $$$+$$$. We will choose exactly one $$$+$$$ to ignore and match all the rest, we can see that when choosing 1 $$$+$$$ to remove and perform algo 7, all the $$$+$$$ to left of that removed $$$+$$$ will match with the $$$-$$$ immediately to the right of them and similar to the $$$+$$$ to the right. So how do we find out what is the best $$$+$$$ to remove. We can see that when choose to remove $$$+$$$ intervals $$$a$$$ and $$$b$$$ assume $$$a \lt b$$$, the difference is that the $$$+$$$ intervals between them match to the immediate $$$-$$$ interval to the left if $$$a$$$ removed, and right if $$$b$$$ removed, $$$b$$$ also matched to the left $$$-$$$ when $$$a$$$ removed and similar to $$$a$$$. So the algo to calculate the change in cost when we unremove $$$a$$$ and remove $$$b$$$ instead :

• Add the cost to match $$$a$$$ to its immediately right $$$-$$$
• For each $$$+$$$ between $$$a$$$ and $$$b$$$ : Add cost to match it to its immediately right $$$-$$$, subtract cost to match it to its immediately left $$$-$$$
• Subtract cost to match $$$b$$$ to its immediately left $$$-$$$

We can see that when considering intervals at height $$$W$$$, remove $$$-$$$ interval at begin and last of the height $$$W$$$ if exist and for each $$$+$$$ interval $$$a$$$ calculate the cost $$$calc(a)$$$ to match remaining $$$+$$$ and $$$-$$$ interval if removing $$$a$$$. We see that the above algorithm is exactly $$$calc(b) - calc(a)$$$ so it's still true if we just apply that on a sub array interval of height $$$W$$$ that contain $$$a, b$$$, which will be helpful when dealing with Algorithm 2

Now we will study how to calculate the penalty involving the ball $$$(x, y)$$$ satisfied condition (5) and no hole in the interval got matched and that ball got matched with a hole inside them. That interval got transformed into 2 balls $$$(x, x), (y, y)$$$ and list of holes $$$(x, h_1), (h_1, h_2), ..., (h_m, y)$$$, which is a continous $$$+$$$ interval so their height from left to right will be like $$$w, w + 1, ...., W$$$. If any of those $$$+$$$ interval can't be removed in the optimal matching of their height, then the ball $$$(x, y)$$$ won't be penalized no matter what. So we will consider only the ball $$$(x, y)$$$ satisfied condition (5), and all the hole inside them removable. We call it a bad match.

We can try greedy at each height, each time choose 1 hole to remove if must to so that we unpenalize as much balls as possible. An observation will simplified the situation that the editorial also mentioned is that if a hole $$$p$$$ is removable at height $$$W$$$ and another hole $$$q$$$ that is removable at height $$$T \gt W$$$ such that no height between $$$W, T$$$ have removable element, then $$$p$$$ is to the left of $$$q$$$.

Supposed $$$p$$$ is to the right of $$$q$$$, observe algo $$$stk$$$ we see that there is exactly one $$$+, -$$$ adjacent elements $$$u, v$$$ resp at height $$$W$$$ that $$$q$$$ is between them, and $$$p$$$ is to the right of both $$$u, v$$$. More all the elements of height $$$T$$$ between $$$u, v$$$ will make an array with adjacent elements changing from $$$+$$$ to $$$-$$$, that started with a $$$+$$$ and end with a $$$-$$$ element $$$e$$$. Now if we remove $$$p$$$ and apply algo 7 to height $$$W$$$, $$$u, v$$$ will be matched. Then remove $$$q$$$ and apply algo 7 to height $$$T$$$, $$$e$$$ will be matched with an $$$+$$$ element $$$f$$$ that is to the right of $$$v$$$.

To prove a contracdiction in choosing deletation-candidate, we have to prove there is a strictly better solution than a current solution which is when the above tie-breakers come in play. If the $$$-$$$ interval $$$v$$$ did not got transformed in the transformed graph, meaning there is no holes between its pair of odd rows, that mean $$$+$$$ interval $$$f$$$ will have its left bound lies strictly to the right. If it's a transformed ball interval then by the tie-breaker the $$$+$$$ interval $$$f$$$ to the right of it will also have its left bound lies strictly to the right. Because of the left bound lies strictly to the right, exchaging matching $$$u, e$$$ will yield strictly better result, which is a contradiction.

So we can add another condition : (10)

• If a hole $$$p$$$ is removable at height $$$W$$$ and another hole $$$q$$$ that is removable at height $$$T \gt W$$$, then $$$p$$$ is to the left of $$$q$$$.

So if there is a ball $$$(x, y)$$$ a bad match, holes $$$(x, h_1), (h_1, h_2), ..., (h_m, y)$$$ have the height $$$w, w + 1, ...., W$$$ and another ball $$$(x', y')$$$ bad match to its right, holes have the height $$$w', w' + 1, ...., W'$$$, we will have $$$w' \gt = W$$$. We can see that ball $$$(x, y)$$$ if one of the height $$$w + 1, ...., W - 1$$$ has another removable hole, that hole isn't in any bad match then we can choose to remove that hole instead, ball $$$(x, y)$$$ won't be penalized. Keeping optimize and finding a way to avoid penalize, we arrive at a structure that is a chain of bad match, the height of the last hole of a bad match from that chain is the height of the first hole of next bad match in the chain, any other bad match have the height of their holes all bigger or smaller than any hole of the chain, and for every height that the bad chain cover there won't be any other removable hole aside the holes in the chain. For any such structure, a $$$+1$$$ penalty is a must, and we can also find out a list of such structure efficiently in the graph. So we can build an efficient algo to compute the penalty cost. (dis 1)

So the grader $$$f'$$$ in the sense of Apr 2 that apply solely to the initial state of the table after applying extra conditions has been built. We can verify that in a solution without any restriction, after moving one piece the grader $$$f'$$$ of new table will drop at most $$$1$$$ compared to original table when one can find the $$$f'$$$ can act on the previous state with at most 1 additional cost compared to how $$$f'$$$ acting on the new state (The $$$f'$$$ grader will be seen more clearly later and I actually didn't verify this so anyone can elaborate efficiently on this is a great help)

At this point we completed the work of optimize Algorithm 1 for both $$$M$$$ odd and even to prepare to deal with Algorithm 2. This part I'm not too confident with optimize the implementation and will just write a rough idea. Any help in optimization is appreciated.

Need to compute the following process

• For every $$$0 \lt = L \lt = R \lt = N - 1$$$
  • Compute the Algorithm 1 of sub-table from row $$$L$$$ to $$$R$$$ = Determinate the match between adjacent odd rows, run the $$$stk$$$ algo on sub-table from row $$$L$$$ to $$$R$$$, compute the sum of 2 x contribution of matching at each height that may have equal or 1 more $$$+$$$ hole (return 0 if there is a height with more $$$-$$$) plus the contribution of penalize of bad match

An odd row will have 2 ways to match across all the possible sub-table contain it, which is match to odd row immediately to left or right of it. So we take into consideration both of those scenario first. After that we see that run the $$$stk$$$ on the whole table instead of just $$$L - R$$$ rows, the height will behave the same so we run that first before running through $$$L, R$$$. Algorithm 2 will become

• For every way of 2 ways to match odd row
  • Compute the initial distance cost across when matching adjacent rows across all $$$L, R$$$ (easy !)
  • Run the $$$stk$$$ algo on the largest table that consistent with the odd rows matching, obtain the height of each element
  • For every $$$0 \lt = L \lt = R \lt = N - 1$$$
    • Compute the Algorithm 1 of sub-table from row $$$L$$$ to $$$R$$$ : compute the sum of 2 x contribution of matching at each height that may have equal or 1 more $$$+$$$ hole (return 0 if there is a height with more $$$-$$$) plus the contribution of penalize of bad match

To optimize the complexity, we will try to make computing Algorithm 1 efficiently on multiple $$$L, R$$$ at once, which is :

• For every way of 2 ways to match odd row
  • Compute the initial distance cost across when matching adjacent rows across all $$$L, R$$$ (easy !)
  • Run the $$$stk$$$ algo on the table that remove first or last unmatched odd row if must, obtain the height of each element
  • Compute the Algorithm 1 of general sub-table :
    • Compute the sum of 2 x contribution of matching at each height that have equal $$$+, -$$$ across all $$$L, R$$$ that valid
    • Compute the sum of 2 x contribution of matching at each height that have 1 more $$$+$$$ across all $$$L, R$$$ that valid
    • Compute the contribution of penalizing bad match across all $$$L, R$$$ that valid

A $$$L, R$$$ is valid when there are positive even number of odd rows between those rows and their odd rows matching consistent to the way of matching odd row in consideration. First we try to compute the contribution of penalizing bad match across all $$$L, R$$$ that valid, from the above discussion it can be translate as :

• For every bad match chain, compute the number of valid $$$L, R$$$ that accepts it as a proper bad match chain when apply an algorithm to find out all disjointed height bad match chain on the sub-table.

First we evaluate how to efficiently realize which is the removable element of each height. From the discussion above we will calculate $$$calc$$$ function for each element in largest table that consistent with the odd rows matching, and for a sub-table $$$L, R$$$, at height $$$H$$$ with more $$$+$$$, an $$$+$$$ element $$$a$$$ is removable if $$$calc(a)$$$ is smallest among every $$$+$$$ elements. So we will compute the $$$calc$$$ function first before Algorithm 1 :

• For every way of 2 ways to match odd row
  • Calculate $$$calc$$$ function for each element in largest table that consistent with the odd rows matching $$$....$$$

Now we will study the structure of a valid bad match chain. Supposed there is a chain of pair of odd rows $$$t_1, t_2, ..., t_k$$$ got accepted as an isolated bad match chain after performing an algorithm with (dis 1) argument. Every bad match $$$t_i$$$ of row $$$(x, y)$$$ can be represent as a sequence of holes sandwiched between 2 ball $$$(x, x), (y, y)$$$ in transformed graph. They will have their corresponding sequence of height $$$H_i = h, h + 1, ..., w$$$ such that $$$H_i$$$ and $$$H_j$$$ is disjointed except for their endpoints and the last element of $$$H_i$$$ equal the first element of $$$H_{i + 1}$$$. And every hole of the chain is a remove-candidate of their height.

Supposed a $$$L, R$$$ accept this chain as a valid bad match chain, let $$$l$$$ be the row of first hole of $$$t_1$$$, $$$r$$$ be the row of last hole of $$$t_k$$$, height of them is $$$h_l$$$ and $$$h_r$$$. We can see that there is no remove candidate at height $$$h_l$$$, $$$h_r$$$ that is to the left and right of $$$l$$$ and $$$r$$$ resp and the $$$+, -$$$ elements height array by of $$$L, R$$$ table begin with a height $$$ \lt h_l$$$ or $$$= h_l$$$ but start with a $$$+$$$ interval, and end at a height $$$ \gt h_r$$$ or $$$= h_r$$$ but with a $$$+$$$ interval (condition *). We can obviously see that $$$l, r$$$ interval is a valid pair that is consistent with how odd rows got matched and accept the $$$t_i$$$ as its sole bad match chain.

Without determinate which $$$L, R$$$ to choose, we can't determinate if a hole is a remove candidate or not but we can identity all the pair of row that satisfied condition 5 first and their $$$calc$$$ array used in comparing the cost of deleting element to find out which is remove candidate.

First for each pair of row satisfy condition 5, it can be a bad pair chain on it own so it can be the beginning and ending of a bad pair chain, we will evaluate what next pair of row satisfy condition 5 can be the immediately element to the right of it in a bad pair chain.

Supposed we have bad matched $$$a$$$ with the last hole is $$$ar$$$ with height $$$h$$$, the bad matched immediately to the right of it is $$$b$$$ with first hole is $$$bl$$$ with the same height $$$h$$$, $$$calc(ar) = calc(bl)$$$ and between $$$ar$$$ and $$$bl$$$ the will be no other hole with height $$$h$$$ and $$$calc$$$ of them $$$ \lt = calc(ar)$$$. We see that with a fixed $$$ar$$$ there would be at most 1 $$$bl$$$, so with a fixed pair of row $$$a$$$ satisfied condition 5 there would be at most 1 $$$b$$$ satisfied condition 5 that can be adjacent to it in some bad match chain. The reverse is similar.

So we draw an edge between 2 odd row pairs satisfied condition 5 if those two pairs can be adjacent to each other in a bad match chain. The edges will form a set of non crossing, ordered path. Supposed we have such path $$$a_1, a_2, ..., a_t$$$ of odd row pairs satisfied condition 5 then any sub path $$$a_i, a_{i+1}, ..., a_j$$$ can be a bad match chain in some sub table. We also see that if $$$l, r$$$ is the first and last row of $$$a_i, a_{i+1}, ..., a_j$$$ sequence and $$$L \lt = l \lt = r \lt = R$$$ is a pair of $$$L, R$$$ that satisfied condition (*) then that sequence is also a valid pair of $$$(L, R)$$$. Because by condition supposed $$$l, r$$$ are first and last hole of that chain with height $$$h_l, h_r$$$, then by condition (*) it's a remove candidate of $$$(L, R)$$$ and for each height $$$h$$$ in between, there can't be new remove candidate between $$$(L, l)$$$ and $$$(r, R)$$$ of the height $$$h$$$ by condition (10) so the set of remove candidate of height $$$h$$$ didn't change when expand from $$$(l, r)$$$ to $$$(L, R)$$$.

So we have a way to efficiently represent all the possible valid bad match chain, and for each bad match chain efficiently represent all the possible pair $$$(L, R)$$$ recognize it :

• Build the path by the possible bad match neighbor relation of all the row pair satisfied condition 5. For each row pair satisfied condition 5, calculate and store the number of $$$Rs$$$ and $$$Ls$$$ satisfied condition (*) of its first and last hole. And for each pair of row pair $$$u, v$$$ satisfied condition 5 lies on a path, multiple number of $$$Rs$$$ of $$$v$$$ and $$$Ls$$$ of $$$u$$$ satisfied condition (*) and add it to the contribution of bad match penalty (This part can be trivially optimize using sufix sum) (Algo $$$pen$$$).

So finally we can use Algo $$$pen$$$ to calculate the contribution of bad match penalty. The revised general algo :

• For every way of 2 ways to match odd row
  • Compute the initial distance cost across when matching adjacent rows across all $$$L, R$$$ (easy !)
  • Run the $$$stk$$$ algo on the table that remove first or last unmatched odd row if must, obtain the height of each element
  • Calculate $$$calc$$$ function for each element in largest table that consistent with the odd rows matching
  • Build the path by the possible bad match neighbor relation of all the row pair satisfied condition 5. For each row pair satisfied condition 5, calculate and store the number of $$$Rs$$$ and $$$Ls$$$ satisfied condition (*) of its first and last hole
  • Build the suffix and prefix sum of $$$Rs$$$, $$$Ls$$$ on each of those path.
  • Compute the Algorithm 1 of general sub-table :
    • Compute the sum of 2 x contribution of matching at each height that have equal $$$+, -$$$ across all $$$L, R$$$ that valid
    • Compute the sum of 2 x contribution of matching at each height that have 1 more $$$+$$$ across all $$$L, R$$$ that valid
    • Compute the contribution of penalizing bad match across all $$$L, R$$$ that valid = Algo $$$pen$$$

Now let evaluate how to calculate equal $$$+, -$$$ height contribution. Supposed we have an array of $$$+, -$$$ elements of height $$$h$$$ with equal $$$+, -$$$, so that array start with $$$+$$$ and end with $$$-$$$ or vice versa. Supposed that array start with $$$+$$$ hole $$$l$$$ and end with $$$-$$$ ball $$$r$$$ and there is a sub-table of $$$L, R$$$ that take them as the set of $$$h$$$ height elements, then either the first element of the sub-table is $$$l$$$ or some elements with height $$$HL \lt h$$$, last is either $$$r$$$ or some elements with height $$$Hr \lt h$$$. We would need $$$h \gt = Hr \gt = Hl$$$.

Also each $$$+$$$ in that array will pair with the $$$-$$$ immediately to the right of it in the array, so for each hole $$$a$$$, it would be matched to the ball immediately to the right with same height $$$(nxt(a))$$$. So to calc how many time the cost of matching $$$a$$$ of height $$$h$$$ to $$$(nxt(a))$$$ contributed we will count how many $$$L, R$$$ that has $$$h \gt = Hr \gt = Hl$$$, the nearest height $$$h$$$ element to right and left of $$$L, R$$$ is $$$l, r$$$ such that $$$l$$$ is a $$$+$$$ hole and $$$r$$$ is a $$$-$$$ ball, and $$$a$$$ and $$$nxt(a)$$$ lies between $$$l, r$$$. The same when we want to match $$$a$$$ with $$$prv(a)$$$ the $$$-$$$ immediately to left with same height. Note that the condition the nearest height $$$h$$$ element to right of $$$L$$$ is $$$l$$$ such that $$$l$$$ is a $$$+$$$ hole is equivalent to $$$HL \lt h$$$ or $$$HL = h$$$ and row $$$L$$$ start with a $$$+$$$ element, same with $$$R$$$.

So there is a process to calculate the contribution of each $$$+$$$ equal $$$-$$$ array of all height by calculating the contribution of each matching a $$$+$$$ to its 2 neighbors $$$-$$$

• Build an array to store $$$nxt(a)$$$, $$$prv(a)$$$ each $$$+$$$ element
• Start building a structure that would process through each $$$+$$$ element $$$a$$$ from left to right and calculate the contribution of matching $$$a$$$ to $$$nxt(a)$$$ that can be modified dynamically between successive $$$+$$$ elements
  • Each match $$$a$$$ to $$$nxt(a)$$$ will be accounted by multiplication number of $$$L, R$$$ such that the first element of $$$L$$$ row have its height < height of $$$a$$$ or = height of $$$a$$$ and that first element is $$$+$$$, same reason with $$$R$$$
  • We naturally want to maintain an array $$$Lh[]$$$ and $$$Rh[]$$$ such that $$$Lh[i], Rh[i]$$$ is number of $$$L, R$$$ to the left and right of $$$a$$$ that has their resp element height $$$i$$$. Also $$$Lp[]$$$ and $$$Rn[]$$$ number of $$$L, R$$$ to the left and right of $$$a$$$ that has their resp element height $$$i$$$ with additional condition element of $$$L$$$ is a $$$+$$$ and $$$R$$$ is a $$$-$$$.
  • The times the match $$$a$$$, $$$nxt(a)$$$ of height $$$h$$$ be accounted would be sum of all the number $$$Lh[i] \times Rh[j]$$$, $$$Lp[h] \times Rn[h]$$$, $$$Lh[i] \times Rn[h]$$$ with all $$$i \lt = j \lt h$$$.
  • We naturally also maintain array $$$Contr[]$$$ such that $$$Contr[h]$$$ is the sum of all $$$Lh[i] \times Rh[j]$$$ with all $$$i \lt = j \lt h$$$, also $$$SumLh[]$$$ and $$$SumRh[]$$$ that $$$SumLh[i]$$$ is sum of $$$Lh[j]$$$ with all $$$j \lt i$$$, same with $$$SumRh[]$$$
  • Now we study what will be changed after successive iteration of $$$+$$$ elements and additional structures to maintain
    • The $$$Lh, Rh, Lp, Rn$$$ array will simply change O(1) elements in O(1) time
    • With each change of $$$Lh, Rh$$$ will change a range of $$$SumLh, SumRh$$$, we will maintain them as a segtree
    • With a change of $$$Rh[i]$$$, the would be a change calculate by multiple it with $$$SumRh[i]$$$ and apply to a range of $$$Contr[]$$$, so we also maintain $$$Contr$$$ as a segtree.
    • But with a change of $$$Lh[i]$$$, each $$$j \gt i$$$, $$$Contr[j]$$$ will change a fixed value but multiple with the sum of all $$$R[j]$$$ with $$$i \lt j \lt h$$$ which is not fixed. To handle this instead of store $$$Contr[]$$$ directly, we build a segtree with $$$Tree[l, r]$$$ having information of the sum of $$$Lh[i]$$$, sum of $$$Rh[j]$$$ , sum of $$$Lh[i] \times Rh[j]$$$ with all $$$l \lt = i \lt j \lt = r$$$ and $$$Contr[h]$$$ is deduced by getting unite information of $$$Tree[0, h - 1]$$$
  • With that argument, we built a structure consist of $$$Lh, Rh, Lp, Rn, SumLh, SumRh, Tree$$$ to efficiently compute contribution of matching $$$a$$$, $$$nxt(a)$$$ when changing $$$a$$$ dynamically from left to right.
• Do the similar with matching $$$a$$$ with $$$prv(a)$$$

So we finished building data structure and algo to calculate contributions in case of equal $$$+, -$$$ of a height. Now move to the case of having 1 more $$$+$$$. This case is more simpler, supposed the height is $$$h$$$ and the array start with a $$$+$$$ and end with a $$$+$$$, choose to remove the leftmost remove candidate $$$+$$$ which is the leftmost $$$+$$$ with minimum $$$calc$$$ and match the $$$+$$$ to the left of it to its right $$$-$$$ and similar to $$$+$$$ to the right. The $$$L, R$$$ choice to accept such an array must be chosen so that the element corresponding to $$$L$$$ is the first element of $$$h$$$ height array itself, or have height $$$ \lt h$$$ and between the element of $$$L$$$ and first element having $$$h$$$ height there are no $$$h$$$ height element, similar $$$R$$$ correspond to the last element or having the height $$$ \gt h$$$ with no $$$h$$$ height elements between (condition **). As long as they sastify that condition then $$$L, R$$$ will accept the array as $$$h$$$ height array.

From that observation we can build a process to calculate contribution :

• Iterate through each height $$$h$$$ and through each $$$+ h$$$ height elements sorted by their $$$calc$$$ with tie breaker is the left element come first if same $$$calc$$$
  • The current elements $$$a$$$ will be choose as the $$$+$$$ removed in a $$$h$$$ height array
  • The current elements $$$a$$$ will lie in a segment of untouched $$$+$$$ elements of height $$$h$$$ and the $$$L, R$$$ will not contain any iterated elements or else the current elements will not be chosen to be removed
  • Supposed there is an $$$+$$$ element $$$l$$$ and $$$r$$$ to left and right of $$$a$$$ chosen as the first and last element of the $$$h$$$ array, the total contribution will be sum of all the distance cost when matching a $$$+$$$ element to its right $$$-$$$ in the range $$$[l, a)$$$, and match to its left $$$-$$$ in the range $$$(a, r]$$$, mutiple with the way to choose $$$L, R$$$ to the left and right of $$$l, r$$$ sastify condition (**)
  • We can easily reformulate the contribution sum into indepedent sum and use suffix array to calculate the total contribution with simple pre-processing.

So we've also done with the case 1 more $$$+$$$. Which is also the end of $$$M$$$ odd case

$$$M$$$ even case is way more simple and the editorial about that part is quite clear, so I won't talk about that here.

This is the end of my interpretation of the editorial. Please give comments PLS PLS PLS