[Algorytmy] Segment o danej właściwości

adambak
Użytkownik
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

Post autor: adambak » 13 gru 2011, o 12:09

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[i]-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..

Afish
Moderator
Moderator
Posty: 2810
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 352 razy

[Algorytmy] Segment o danej właściwości

Post autor: Afish » 13 gru 2011, o 12:41

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).

Awatar użytkownika
paladin
Użytkownik
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

Post autor: paladin » 13 gru 2011, o 12:46

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

adambak
Użytkownik
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

Post autor: adambak » 13 gru 2011, o 13:05

paladin pisze:O, całkiem fajne zadanie Skąd pochodzi?
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 Pana

zmieniam zdanie, skoro to konkursowe to jednak lubię, ale trudniejsze niż myslałem.. zabieram się za próby zrozumienia..

Afish
Moderator
Moderator
Posty: 2810
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 352 razy

[Algorytmy] Segment o danej właściwości

Post autor: Afish » 13 gru 2011, o 13:18

paladin pisze:Uwaga do przedmówcy: Set w Pascalu? Powodzenia ;)
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ą.

adambak
Użytkownik
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

Post autor: adambak » 13 gru 2011, o 14:10

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?)

Afish
Moderator
Moderator
Posty: 2810
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 352 razy

[Algorytmy] Segment o danej właściwości

Post autor: Afish » 13 gru 2011, o 20:29

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.

adambak
Użytkownik
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

Post autor: adambak » 13 gru 2011, o 23:00

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

ordyh
Użytkownik
Użytkownik
Posty: 255
Rejestracja: 6 paź 2009, o 18:04
Płeć: Mężczyzna
Pomógł: 66 razy

[Algorytmy] Segment o danej właściwości

Post autor: ordyh » 14 gru 2011, o 19:07

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:

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
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.

Afish
Moderator
Moderator
Posty: 2810
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 352 razy

[Algorytmy] Segment o danej właściwości

Post autor: Afish » 14 gru 2011, o 21:15

To ciekawe, bo mój program wykorzystujący multiset wylatywał przez pamięć. No ale dawno to było, mogę coś mieszać.

ODPOWIEDZ