**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.↵
[problem:1816B]↵
↵
<spoiler summary="Solution">↵
https://ufesbr-my.sharepoint.com/:o:/g/personal/pedro_i_morais_edu_ufes_br/EsgqVd-xXTRHh4SsNdn23r8BTzK-g76V6fmOkUr8_02PZw?e=9qZ1Dx↵
</spoiler>↵
↵
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.com/problemset/problem/1816/B↵
↵
Note: english is not my native langue, sorry for (maybe) poor comunication, i did my best.↵
↵
[user:culver0412,2023-06-18] did i miss understand something in the general case?↵
↵
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;↵
}↵
↵
↵
**BTW:** use dark mode for better reading.↵
[problem:1816B]↵
↵
<spoiler summary="Solution">↵
https://ufesbr-my.sharepoint.com/:o:/g/personal/pedro_i_morais_edu_ufes_br/EsgqVd-xXTRHh4SsNdn23r8BTzK-g76V6fmOkUr8_02PZw?e=9qZ1Dx↵
</spoiler>↵
↵
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.com/problemset/problem/1816/B↵
↵
Note: english is not my native langue, sorry for (maybe) poor comunication, i did my best.↵
↵
[user:culver0412,2023-06-18] did i miss understand something in the general case?↵
↵
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;↵
}↵
↵
