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

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.me/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;

}