Recent actions

If I have understood it correctly, the proof is:

Let's solve this problem for a 1D case, then we will extend it to 2D. Say, n = 3. So, the values are: 1, 2, 3, 4, 5, 6, 7, 8, 9 (from 1 to n*n) Here, the minimum value is 1 and the maximum value is 9, so, no matter what, the absolute difference will be at most 8 (when |9-1|) and the minimum absolute difference will be 1 (when |9-8|), and the other values will be in between. Our target is to maximize the total various types of such absolute differences. If we order the numbers in the following way: 9, 1, 8, 2, 7, 3, 6, 4, 5 then the target can be maximized. As in this case we are getting these all kinds of absolute differences we could ever get from them taking side-adjacent values. That are: 8 (i.e, |9-1|), 7 (i.e, |8-1|), 6 (i.e, |8-2|), ..., 1 (i.e, |5-4|)

Two numbers in an array are side-adjacent when they are positioned one after another either in the same row or in the same column. For example, for a 5x5 matrix, the indices are as follows:

(1, 1) (1, 2) (1, 3) (1, 4) (1, 5) 
(2, 1) (2, 2) (2, 3) (2, 4) (2, 5) 
(3, 1) (3, 2) (3, 3) (3, 4) (3, 5) 
(4, 1) (4, 2) (4, 3) (4, 4) (4, 5) 
(5, 1) (5, 2) (5, 3) (5, 4) (5, 5)

So, the side adjacent to position (3, 3) are (3, 2), (3, 4), (2, 3), and (4, 3) positions. We have to find all possible side-adjacent positions for each position and take absolute differences of corresponding values and count how many unique absolute difference values we get. And obviously, we have to find an arrangement in such a way, that the number of possible such values maximizes.

Going back to 3x3 cases (for better manageability), a deterministic solution is to arrange the 1D array (which maximizes the result in 1D case, i.e: 9, 1, 8, 2, 7, 3, 6, 4, 5), in a zig-zag fashion. So, the solution is:

9, 1, 8
3, 7, 2
6, 4, 5

which follows the following pattern:

--->----
       |
       v
---<----
|
v
---->---

This will work because the zig-zag pattern is nothing but the same 1D array (just in an entangled fashion). But the values which were side-adjacent in 1D cases are still side adjacent in 2D cases (if we just follow this path). Obviously, as it is now in 2D, there will be more side-adjacent pairs that are not shown in the path (each position can have at most 4 side-adjacent positions, namely: left, right, up and down position), but we simply don't care for them, as we already have maximized the result and the other side-adjacent values will just create duplicate absolute difference values which we already found while traversing the path.

Solution: https://codeforces.com/contest/1783/submission/190766740

Created or updated the text
Created or updated the text
Created or updated the text
Created or updated the text
Created or updated the text