Strona 1 z 1

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

: 13 gru 2011, o 12:09
autor: adambak
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..

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

: 13 gru 2011, o 12:41
autor: Afish
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).

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

: 13 gru 2011, o 12:46
autor: paladin
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

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

: 13 gru 2011, o 13:05
autor: adambak
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..

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

: 13 gru 2011, o 13:18
autor: Afish
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ą.

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

: 13 gru 2011, o 14:10
autor: adambak
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?)

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

: 13 gru 2011, o 20:29
autor: Afish
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.

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

: 13 gru 2011, o 23:00
autor: adambak
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

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

: 14 gru 2011, o 19:07
autor: ordyh
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.

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

: 14 gru 2011, o 21:15
autor: Afish
To ciekawe, bo mój program wykorzystujący multiset wylatywał przez pamięć. No ale dawno to było, mogę coś mieszać.