Runda 21 - omówienie zadań

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Re: Runda 21 - omówienie zadań

Postautor: kokosek » 03 kwie 2015, 17:41

Ja nie zrobiłem żadnego preprocessingu. Może przez niego masz TLE.
Wystarczy mnożyć macierz od nowa dla każdego testu. W końcu jest ich tylko 10.
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 21 - omówienie zadań

Postautor: pm12 » 15 lip 2015, 01:39

Jak znajdować za pomocą stosu najbliższej z lewej strony liczby większej od zadanej ?
pm12
 
Posty: 3
Rejestracja: 09 lip 2015, 13:53

Re: Runda 21 - omówienie zadań

Postautor: Crucian » 18 lip 2015, 18:07

@pm12:
Przechodzisz ciąg od lewej i wrzucasz kolejno liczby na stos, lecz przed wrzuceniem kolejnej usuwasz ze szczytu stosu wszystkie liczby mniejsze niż dana liczba.
Kod: Zaznacz cały
stack <int> stos;
for(int i = 1; i <= n; i++) {
   while(stos.size() > 0 && stos.top() < a[i]) stos.pop();
   // na szczycie stosu masz szukany element
   stos.push(a[i]);
}
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 21 - omówienie zadań

Postautor: narbej » 11 wrz 2015, 17:25

Bombowa ucieczka

Malutka optymalizacja
Opcję -1 sprawdzamy na samym początku, a dopiero potem pozostałe.

Większa optymalizacja [jeszcze nie testowałem]
  1. Sprawdzamy opcję -1 i jeżeli tak kończymy program.
  2. Szukamy pierwszej [najkrótszej] ścieżki ze startu do mety, jeżeli nie ma wypisujemy 0 i exit.
  3. Blokujemy całą 1 ścieżkę i szukamy następnej ścieżki ze startu do mety, jeżeli nie ma wypisujemy 1 i exit.
  4. Blokujemy całą 2 [+1] znaleźioną ścieżkę i szukamy następnej ścieżki ze startu do mety, jeżeli nie ma wypisujemy 2 i exit.
  5. Blokujemy całą 3 [i pozostałe] znaleźioną ścieżkę i szukamy następnej ścieżki ze startu do mety, jeżeli nie ma wypisujemy 3 i exit.
  6. W takim razie są cztery całkowicie niezależne ścieżki. Wypisujemy 4 i exit
.

Nie wiem, czy nie popełniam tu jakiegoś błędu myślowego, ale to wyjdzie w praniu.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 21 - omówienie zadań

Postautor: sebastian05 » 06 paź 2016, 14:04

Mógłby ktoś rozwinąć to geometryczne podejście do Tortu 2? Dlaczego to działa i tym podobne.
sebastian05
 
Posty: 2
Rejestracja: 06 lip 2015, 21:20

Poprzednia

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron