Matematyka.pl

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

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

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

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

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

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

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.

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

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.

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