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

In fact we can directly get a formula using lagrange inversion. the final result (plus 2) is the $$$x^{n-1}$$$ coefficient of $$$2(n-1)!(\frac{x}{2x+1-e^x})^n$$$

Oh this $$$O(n)$$$ is better than std's $$$O(n\log n)$$$ :)

Through this comment, I want to address the cheating charges levied on me and Numinous , for having a coinciding solution to problem C in Educational Round 142. The submissions are 190386013 and 190353992. The reason for getting plagiarised was having a similar template, going through solve function for both speaks out the difference clearly. I hereby in my humble opinion ask MikeMirzayanov Neon BledDest adedalic vovuh awoo to provide us justice and the ratings we deserve . Thank You for your time and effort .

IMO the problems were great. I enjoyed thinking about and solving them. Also I got caught on the special case for B (a1 == 0) haha.

Hi my submission 190325251 is said to coincide with submission 190323813. I believe the logic to this problem is very straight forward and the solve() template we both used is very standard. Any of my previous submission uses a similar template + style and I believe this is just a mistake from the automated plagiarism checking system. Please update I dont want to be flagged for cheating :(

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