[Algorytmy] Segment o danej właściwości
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Segment o danej właściwości
Dany jest typ \(\displaystyle{ \text{ tab=array[1..n]of Integer }}\), przy czym \(\displaystyle{ n>0}\). Dla tablicy \(\displaystyle{ \text{A:tab}}\) oraz liczby całkowitej \(\displaystyle{ k}\) powiemy, że segment \(\displaystyle{ \text{A[d..g]}}\) jest \(\displaystyle{ k}\)-płaski, jeśli dla każdych \(\displaystyle{ i,j}\) takich, że \(\displaystyle{ d\le i,j\le g}\) zachodzi nierówność \(\displaystyle{ A-A[j]\le k}\). Napisz funkcję
\(\displaystyle{ \text{kaplaski(const A:tab, k:Integer):Integer}}\)
która wyznaczy długość najdłuższego \(\displaystyle{ k}\)-płaskiego segmentu w tablicy \(\displaystyle{ \text{A}}\)..
nie lubię takich zadań, nic mi nie przychodzi do głowy lepszego niż kwadratówka.. jakieś pomysły? oczywiście wystarczy zarys algorytmu, problemem nie jest Pascal..
\(\displaystyle{ \text{kaplaski(const A:tab, k:Integer):Integer}}\)
która wyznaczy długość najdłuższego \(\displaystyle{ k}\)-płaskiego segmentu w tablicy \(\displaystyle{ \text{A}}\)..
nie lubię takich zadań, nic mi nie przychodzi do głowy lepszego niż kwadratówka.. jakieś pomysły? oczywiście wystarczy zarys algorytmu, problemem nie jest Pascal..
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Segment o danej właściwości
Zadanie podobne do Pilotów z finału XVII OI bodajże. Jeżeli masz jakiś podciąg z tablicy, to znajdź w nim największy i najmniejszy element, sprawdź, czy różnica jest mniejsza lub równa od k. Jeżeli tak, to cały ten podciąg jest k-płaski. Teraz rozszerzasz ten podciąg o kolejny element i sprawdzasz, czy ten element jest większy od poprzedniego największego / mniejszy od poprzedniego najmniejszego. Jeżeli tak, to odpowiednio skracasz przedział. Powinno dać się bez większych problemów zrobić w \(\displaystyle{ n \log n}\) przy użyciu seta, da się też zejść do liniówki (i nie jest to bardzo trudne).
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Algorytmy] Segment o danej właściwości
O, całkiem fajne zadanie Skąd pochodzi?
Robimy to czymś na kształt algorytmu dynamicznego: dla pozycji \(\displaystyle{ j}\) pamiętamy \(\displaystyle{ a_j}\): najwcześniejsze miejsce, gdzie może zacząć się \(\displaystyle{ k}\)-płaskie słowo kończące na \(\displaystyle{ j}\).
Pozycję \(\displaystyle{ a_{j+1}}\) możemy wyliczyć tak: ustawiamy wskaźnik \(\displaystyle{ p = a_j}\), a następnie przesuwamy go do przodu, aż różnica między największą i najmniejszą liczbą w przedziale \(\displaystyle{ [p,j+1]}\) spadnie poniżej \(\displaystyle{ k}\). Cały problem jest w tym, skąd wiedzieć, jaka jest największa i najmniejsza liczba w zadanym przedziale. Pokażę dla największej: pamiętamy wszystkich "kandydatów" w dwustronnej kolejce uporządkowanej malejąco. Jeśli przedział się zwiększa dostawiamy jeden element na koniec kolejki (ściągając wszystkie mniejsze), jeśli zmniejsza - usuwamy z początku kolejki. Przy odpowiedniej implementacji działa to liniowo.
Uwaga do przedmówcy: Set w Pascalu? Powodzenia
Robimy to czymś na kształt algorytmu dynamicznego: dla pozycji \(\displaystyle{ j}\) pamiętamy \(\displaystyle{ a_j}\): najwcześniejsze miejsce, gdzie może zacząć się \(\displaystyle{ k}\)-płaskie słowo kończące na \(\displaystyle{ j}\).
Pozycję \(\displaystyle{ a_{j+1}}\) możemy wyliczyć tak: ustawiamy wskaźnik \(\displaystyle{ p = a_j}\), a następnie przesuwamy go do przodu, aż różnica między największą i najmniejszą liczbą w przedziale \(\displaystyle{ [p,j+1]}\) spadnie poniżej \(\displaystyle{ k}\). Cały problem jest w tym, skąd wiedzieć, jaka jest największa i najmniejsza liczba w zadanym przedziale. Pokażę dla największej: pamiętamy wszystkich "kandydatów" w dwustronnej kolejce uporządkowanej malejąco. Jeśli przedział się zwiększa dostawiamy jeden element na koniec kolejki (ściągając wszystkie mniejsze), jeśli zmniejsza - usuwamy z początku kolejki. Przy odpowiedniej implementacji działa to liniowo.
Uwaga do przedmówcy: Set w Pascalu? Powodzenia
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Segment o danej właściwości
sam nie wiedziałem, Pan Profesor dał nam jako jedno z zadań przygotowawczych przed kolokwium w ten czwartek.. teraz się okazuje, że to jest właściwie to samo zadanie o którym pisze Afish i to autorstwa właśnie tego Panapaladin pisze:O, całkiem fajne zadanie Skąd pochodzi?
zmieniam zdanie, skoro to konkursowe to jednak lubię, ale trudniejsze niż myslałem.. zabieram się za próby zrozumienia..
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Segment o danej właściwości
Na OIu trzeba było seta, to i w Pascalu jakoś dało się zrobić Polecam rozkminić liniówkę, nie jest taka trudna, a ma o wiele mniejszą złożoność pamięciową.paladin pisze:Uwaga do przedmówcy: Set w Pascalu? Powodzenia
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Segment o danej właściwości
a tak z ciekawości - jak set (a właściwie chyba multiset, tak czy siak pewnie tak samo szybko działają) się sprawuje na konkursach jak olimpiada? pewnie maksa dostać na nim nie możnabyło, skoro liniówka jest wzorcowa, ale bardziej w granicach 90pkt czy 60pkt? ciekawi mnie to czy np w takiej sytuacji kiedy złożoność liniowo-logarytmiczna jest bardziej oczywista to ufać STLowi czy lepiej pisać własną strukturkę? (niby dłużej zejdzie ale może więcej pkt?)
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Segment o danej właściwości
Tutaj problemem nie była szybkość (różnica między liniówką a liniowo-logarytmiczną jest często niemierzalna), bardziej chodziło o pamięć. Multiset się nie mieścił i chyba dwa albo trzy ostatnie testy nie przechodziły. Własne struktury możesz klepać, ale tylko wtedy, gdy znasz je na pamięć i potrafisz zakodzić w 5 minut. W pozostałych przypadkach chyba nie ma co kombinować i lepiej zbijać złożoność, niż szukać szybkości w optymalizacjach struktur.
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
[Algorytmy] Segment o danej właściwości
rozumiem.. fakt, ciężko by było chyba dać takie testy z którymi czasowo by \(\displaystyle{ n\log n}\) nie dawało rady, a liniówka tak.. musiałyby być chyba ogromne..
dzięki wielkie za odpowiedzi
dzięki wielkie za odpowiedzi
[Algorytmy] Segment o danej właściwości
W Pilotach akurat problemem nie była pamięć (64 mb był limit), a czasy, to są czasy z ostatnich testów, rozwiązanie na multisecie:
W tych testach gdzie jest program wywłaszczony, jest duże \(\displaystyle{ k}\), przez co trzeba było trzymać w multisecie dość dużo elementów (do 3 milionów), no i nie wyrobiło takie rozwiązanie czasowo. Liniówka na ostatnich testach ma czasy < 1.2s.
Kod: Zaznacz cały
8a Program wywłaszczony --/1.50s 0/10
8b OK 0.69s/1.50s
8c OK 1.22s/1.50s
8d OK 0.67s/1.50s
8e OK 0.77s/1.50s
9a Program wywłaszczony --/2.00s 0/10
9b OK 1.08s/2.00s
9c OK 1.56s/2.00s
9d OK 1.13s/2.00s
9e OK 1.14s/2.00s
10a Program wywłaszczony --/3.50s 0/10
10b OK 2.09s/3.50s
10c OK 1.92s/3.50s
10d OK 2.18s/3.50s
10e OK 2.26s/3.50s
10f Program wywłaszczony --/3.50s
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
[Algorytmy] Segment o danej właściwości
To ciekawe, bo mój program wykorzystujący multiset wylatywał przez pamięć. No ale dawno to było, mogę coś mieszać.