Zadanie A Może Mediana?

Question

Mam problem z takim zadaniem:

https://sio2.mimuw.edu.pl/c/zwo21/p/amm/

Nie mam pomysłu jak do tego podejść. Myślałem nad jakimś dynamikiem, ale nie mam pomysłu na cokolwiek w sensownej złożonności. Oprócz symulacji na kolejce wszystkich przypadków, ale to jest zawolne napewno. Pewnie wchodzi jakieś O(N^3), bo N <= 500.

Ma ktoś jakiś pomysł?

Z góry dziękuję.

Answer 1

Jedno z lepszych zadań jakie widziałem na wyszukiwanie binarne po wyniku. O(N^2 * log(max A_i)), gdzie max A_i to max wartosc w polu na planszy (i,j). Zauważamy, że zawsze wykonamy 2n-1 kroków w dojściu z pola (1,1) do (n,n). Szukamy binarnie, czy da się ułożyc o medianie x. Zauważmy, że musi być przynajmniej połowa (zaokrąglając w górę) elementów (w stosunku do całej drogi, która przebędziemy (2n-1)) >= x. Więc każdy element zamieniamy na 1, jak jest >= x, a na 0 jak jest mniejszy. I odpalamy klasycznego dynamika, z dojścia z (1,1) do (n,n) zbierając jak największą liczbę diamentów, jak w zadaniu tym: https://szkopul.edu.pl/problemset/problem/8eq2zhM559QZjqVGNXFSv3st/site/?key=statement

lub tym: https://sio2.mimuw.edu.pl/c/zwo20/p/dia/

I jak najlepsza droga > (2n-1) / 2, to zwaracamy w procedurze że się da, jak nie to zwracamy, że się nie da.