#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Can the solution bellow be applied (with small modification) to the general case of N x N? (Solution in One Note).

#### BTW: use dark mode for better reading. 1816B - Grid Reconstruction

Solution

As you could ( maybe ) understand, my idea is use the fact that maximizing minimum cost path, is equivalent to maximizing all paths. Because if you maximize only a subset of paths, than is easy to show that minimum cost path changes.

Btw2: I did think about adding a "virtual" row and/or column to make matrix even by even, and saying that values of positions are 0, so the answer will (maybe?) not be affected.

link to problem: https://codeforces.net/problemset/problem/1816/B

Note: english is not my native langue, sorry for (maybe) poor comunication, i did my best.

culver0412 did i miss understand something in the general case?

My code in c++:

include <bits/stdc++.h>

define dbg(var) cout << #var << " = " << var << "\n"

using namespace std;

int main(){

ios_base::sync_with_stdio(0);

cin.tie(NULL);

int t;

cin>>t;

while(t--){

    int n;

    cin>>n;

    int grid[3][n+1];

    int p_grid[3][n+1];

    for(int j = 1; j <= n; j++){

================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================ p_grid[1][j] = n-(j-1); ================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

       p_grid[2][j] = n-(j-1);

    p_grid[2][1] = p_grid[1][n] = 1;

    p_grid[1][1] = p_grid[2][n] = n;

    for(int j = 1; j <= n; ++j){

       grid[1][j] = (j%2!=0? 2*n - j : j);

    for(int j = 1; j <= n; ++j){

       grid[2][j] = (j%2!=0? j : 2*n - j);

    grid[2][n] = 2*n;

    //using p_grid to get a better answer

    for(int j = 1; j <= n-1; j++){

       if( (p_grid[2][j] > p_grid[1][j+1]) ){

         if( grid[2][j] > grid[1][j+1]){

          int temp = grid[2][j];

          grid[2][j] = grid[1][j+1];

          grid[1][j+1] = temp;

    for(int i = 1; i <= 2; i++){

       for(int j = 1; j <= n; j++){

         cout<<grid[i][j];

         if(j != n) cout<<" ";

       cout<<"\n";

return 0;

Rev.	By	When	Δ	Comment
en12	2the0No0Star2Boy	2024-04-29 00:05:20	4	Tiny change: 'd, my idea is use the f' -> 'd, my idea, use the f'
en11	2the0No0Star2Boy	2023-06-18 02:05:53	0	(published)
en10	2the0No0Star2Boy	2023-06-18 02:05:12	13
en9	2the0No0Star2Boy	2023-06-18 02:03:59	23
en8	2the0No0Star2Boy	2023-06-18 02:03:33	116
en7	2the0No0Star2Boy	2023-06-18 02:02:57	4
en6	2the0No0Star2Boy	2023-06-18 02:02:09	50788	Reverted to en4
en5	2the0No0Star2Boy	2023-06-18 02:01:07	50788
en4	2the0No0Star2Boy	2023-06-18 02:00:13	8	Tiny change: ' in c++:\n#include' -> ' in c++:\n\n\n\n\n#include'
en3	2the0No0Star2Boy	2023-06-18 01:59:44	1244
en2	2the0No0Star2Boy	2023-06-18 01:52:20	250
en1	2the0No0Star2Boy	2023-06-18 01:47:43	649	Initial revision (saved to drafts)