It took days for me to just to barely understand the editorials so I'm having an idea of making a blog to share my analyzation and insight to reach out to people, any help with correcting and optimizating to my logic is appreciated. 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 on a general table (supposed even number of odd row, other case is trivial), 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 : (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 first element of track $$$b$$$ and append it to the last of $$$a$$$
  • 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 $$$(1)$$$ — 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

A track of the matched rows $$$a$$$,$$$b$$$ clearly has size at least $$$abs(a-b)$$$ + 1, so the number of moves has a lower bound $$$\sum_{a, \,b \,is \,matched \,by \,algo \,(3) \,and \,definition \,(4)}(abs(a-b))$$$ $$$ \gt =$$$ $$$\sum_{a, \,b \,is \,matched \, to \, minimize \, the \, sum}(abs(a-b))$$$. To minimize the sum, it's easy to see that we match the even number of odd rows so that each matched pair of rows has no rows between them and even numbers of other rows on both left and right side of them.