Please read the new rule regarding the restriction on the use of AI tools. ×

1816B.Grid Reconstruction: General Case

Revision en2, by 2the0No0Star2Boy, 2023-06-18 01:52:20

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

Tags constructive

History

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