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

Zadanie A Może Mediana?

Aruba Cloud - Virtual Private Server VPS
0 głosów
489 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 820 wizyt
0 głosów
1 odpowiedź 305 wizyt
0 głosów
1 odpowiedź 1,160 wizyt
pytanie zadane 5 lipca 2019 w C i C++ przez niezalogowany

93,329 zapytań

142,323 odpowiedzi

322,400 komentarzy

62,663 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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...