• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie A Może Mediana?

VPS Starter Arubacloud
0 głosów
335 wizyt
pytanie zadane 26 stycznia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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ę.

1 odpowiedź

0 głosów
odpowiedź 26 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.

Podobne pytania

0 głosów
0 odpowiedzi 682 wizyt
0 głosów
1 odpowiedź 206 wizyt
0 głosów
1 odpowiedź 766 wizyt
pytanie zadane 5 lipca 2019 w C i C++ przez niezalogowany

92,782 zapytań

141,712 odpowiedzi

320,598 komentarzy

62,114 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...