Kolejnym zadaniem z OI były klocki. Mnie najwięcej bólu właśnie ono sprawiło ;) Najpierw uznałem, że jest śmiesznie proste, potem, że jednak moga być problemy, z czasem stwierdziłem, że jest zwyczajnie powalone, a gdy przyszedł pomysł, okazało się, że do najgorszych nie należy ;)
Treść znajdziemy pod tym adresem: http://sio.mimuw.edu.pl/user.phtml/klo.pdf?op=get&id=84850
Co trzeba umieć??
- "cin" i "cout" :O
- "if", "for" i "while"
- myśleć ^^
Co by było dobrze umieć??
- Drzewa licznikowe
Czego się nauczysz??
- Drzew licznikowych ;)
Dobra, no to po kolei, weźmy sobie przykładzik jakiś.
3, 9, 2, 3, 1
Mamy mieć 3 kolejne wieżyczki tej samej wysokości, ok, tylko skąd wziąć tą wysokość?? A no, po długich, wnikliwych i jakże skomplikowanych rozważaniach doszedłem do wniosku, że to bedzie niespotykana dziwna rzecz, która się zwie: mediana :) Kto nie wie co to, to może na wiki poczytać ;)
No więc rozwiązanie nasuwa się samo, wziąć 3 pierwsze liczby - tj. 3, 9 i 2, i co teraz?? Spojrzeć ile ruchów nam trzeba żeby wszystkie wieżyczki "dobiły" do mediany. No to mediana to po skomplikowanych obliczeniach wychodzi 3 ;) 9-3 to 6 i 3-2 to 1, czyli w sumie 7 ruchów, potem sprawdzić kolejny zestaw - 9, 2, 3, o dziwo jest identyczny i ostatni - 2, 3, 1 - okazuje się, że trzeba dwóch ruchów.
Wszystko fajnie, tylko to jest ZA WOLNE!!
- raz, nawet zakładając, że medianę jakimś cudem program z niczego jednym ruchem policzy, to za każdym razem gdy liczymy sumę wykonamy O(k) operacji, ale wykonamy to (n-k) razy, więc wyjdzie nam złożoność nk-k2, czyli funkcja kwadratowa :(
- dwa - medianę w jednym ruchu nie policzymy, ale tak czy siak "jakoś" ją liczyć trzeba i tym się zajmiemy ;)
A więc trzeba wymyślić sposób na szybkie liczenie sumy ruchów… Załóżmy, że już jakimś magicznym sposobem mamy medianę, sumę pierwszego zestawu liczymy tak jak powiedziałem wcześniej, no to zajmijmy się przykładem:
3, 9, 2 - 7 ruchów, mediana 3
9, 2, 3 - 7 ruchów, mediana 3
EUREKA!! :D mamy pierwszą zależność, jeśli z naszego zestawu usuniemy i dodamy taką samą liczbę (u nas 3), to ani ruchy, ani mediana się nie zmienią (co jest chyba oczywiste) ;)
Idziemy dalej
9, 2, 3 - 7 ruchów, mediana 3
2, 3, 1 - 2 ruchy, mediana 2
O_o ojojoj, ale się narobiło, no to jakim cudem my mamy przejść z jednego w drugie?? Ano istnieje sposób i trzeba go będzie wymyślić ;) Może jednak najpierw popatrzmy co się stało - usunęliśmy liczbę większą od mediany (9) i dodaliśmy mniejszą od mediany (2). No cóż, w takim razie można wnioskować, że jak znajdziemy jakiś ogólny wzór na liczenie sumy, gdy usuwamy coś większego niż mediana i dodajemy coś większego, to będzie fajnie. Ale na tym nie koniec, tych wzorów troche będzie, dokładnie 9 ;)
- dodana liczba jest taka sama jak usunięta (to już wcześniej omówiliśmy ;) )
- obie dodana i usunięta są większe niż mediana
- obie dodana i usunięta są mniejsze niż mediana
- dodana liczba=mediana, a usunięta>mediana
- dodana liczba=mediana, a usunięta<mediana
- dodana liczba>mediana, a usunięta=mediana
- dodana liczba<mediana, a usunięta=mediana
- dodana liczba>mediana, a usunięta<mediana
- dodana liczba<mediana, a usunięta>mediana
Jak się okaże, pierwsze 5 przypadków jest śmiesznie prostych, za to kolejne 4 wymagają sporo myślenia.
Obie dodana i usunięta są większe niż mediana
Rozpatrzmy przykład:
8, 5, 3 mediana=5, ruchy=5
5, 3, 6 mediana=5, ruchy=3
Łatwo stwierdzić, że jeśli usuniemy i dodamy jakąś liczbę większą od mediany, to ona wciąż będzie środkową wartością, więc się nie zmieni, zmieni się za to liczba ruchów, a o ile?? o różnicę liczby dodanej i usuniętej ;) Widać?? Jak dodamy liczbę o 2 większa niż usunięta, no to ruchy wzrosną o 2, jeśli dodamy o 3 mniejszą niż usunięta, to ruchy zmniejszą się o 3 ;)
Czyli: ruchy=ruchy+liczba_dodana-liczba_usunięta :)
Obie dodana i usunięta są mniejsze niż mediana
Chyba nietrudno zauważyć, że zasada będzie podobna jak w poprzednim przypadku - mediana się nie zmieni, a suma ruchów się zmieni o różnicę dwóch liczb, które się zmieniły. Jest jednak pewien haczyk, o ile wcześniej im większe liczba, tym więcej ruchów, to teraz im większa jest liczba, tym bliżej mediany, przez co mniej ruchów. Na przykładzie:
3, 5, 8 mediana=5, ruchy=5
5, 8, 2 mediana=5, ruchy=6
Widać, iż teraz liczba ruchów wzrośnie o różnicę liczby usuniętej i dodanej.
Czyli: ruchy=ruchy+liczba_usunieta-liczba_dodana
Dodana jest równa medianie, a usunięta jest większa od mediany
Może to zabrzmi nieco magicznie, ale jakbyśmy się nie starali, to jak wyrzucimy ze zbioru jakąś liczbę i wrzucimy liczbę, która była wcześniej medianą, to mediana się nie zmieni ;) A więc skoro mediana zostanie ta sama, a pozbędziemy się jakiejś liczby, to wystarczy sprawdzić ile klocków z usuniętej wierzyczki trzeba było zabrać, żeby dojść do mediany i odjąć tą liczbę od liczby ruchów ;)
Czyli: ruchy=ruchy-(liczba_usunięta-mediana)
Dodana jest równa medianie, a usunięta jest mniejsza od mediany
Dokładnie ta sama sytuacja co wyżej, tylko tutaj trzeba było na usuniętą wierzyczkę nakładać klocki, więc wykonywaliśmy przy tym mediana-liczba_usunięta ruchów.
Czyli ruchy=ruchy-(mediana-liczba_usunięta)
Dodana jest większa od mediany, a usunięta równa medianie
Tutaj zaczynają się schody, w sumie to tak dokładnie nie pamiętam skąd mi się to już wzięło, więc albo wierzcie mi na słowo, albo zachęcam do własnych rozważań ;) Główny problem polega na tym, że w poprzednich przypadkach mediana się nie zmieniała, a tutaj może (ale nie zawsze musi) się zmieniać po dodaniu nowej wierzyczki
Jeśli liczba k kolumn w zestawie jest NIEPARZYSTA - ruchy=ruchy+liczba_dodana-nowa_mediana
Jeśli liczba k kolumn w zestawie jest PARZYSTA i liczba_dodana=nowa_mediana - ruchy=ruchy-1
Jeśli liczba k kolumn w zestawie jest PARZYSTA, ale nie zachodzi powyższy warunek - ruchy=ruchy-nowa_mediana+stara_mediana+liczba_dodana-nowa_mediana
Dodana jest mniejsza niż mediana, a usunięta równa medianie
Ta sama historia co wyżej ;)
Jeśli liczba k kolumn w zestawie jest NIEPARZYSTA - ruchy=ruchy+nowa_mediana-liczba_dodana
Jeśli liczba k kolumn w zestawie jest PARZYSTA - ruchy=ruchy+stara_mediana-liczba_usunięta
Dodana jest większa niż mediana, a usunięta mniejsza od mediany
Znowu do wszystkiego doszedłem rozpisując sobie ze 20 przykładów i gapiąc się na nie ;)
Jeśli liczba k kolumn w zestawie jest NIEPARZYSTA - ruchy=ruchy-stara_mediana+liczba_usunieta+liczba_dodana-nowa_mediana
Jeśli nie, to - ruchy=ruchy-(stara_mediana-liczba_usunieta)+liczba_dodana-nowa_mediana-(nowa_mediana-stara_mediana)
Dodana jest mniejsza niż mediana, a usunięta jest większa od mediany
Tak dotarliśmy do końca ;) A wyniki tutaj są następujące:
Jeśli liczba k kolumn w zestawie jest NIEPARZYSTA - ruchy=ruchy-liczba_usunięta+stara_mediana-liczba_dodana+nowa_mediana
W przeciwnym wypadku - ruchy=ruchy-liczba_usunięta+stara_mediana-liczba_dodana+stara_mediana
Drzewa licznikowe
OK, no to wiemy jak liczyć sumę ruchów, ale cały czas zakładaliśmy, że "skądś" mamy medianę, ale tak do końca nie wiadomo skąd… Wypadałoby jeszcze w miarę szybko ją wziąć… Do tego właśnie nadadzą się drzewka licznikowe ;)
Pod adresem http://infa.lo2.opole.pl:81/lekcje/drzewo_licznikowe/drzewo_licznikowe.doc znajdziecie artykuł, z którego "mniej więcej" nauczyłem się czego mi trzeba o tych drzewach :)
Tak naprawdę potrzebna nam wiedza o nich taka:
- Jak dodać liczbę do drzewa??
- Jak usunąć liczbę z drzewa??
- Jak znaleźć liczbę numer "x" w drzewie
- Co to jest czapa
OK, zakładam, że zaznajomiliście się z tym ;) Teraz zastanówmy się jakie to drzewo ma być. Zgodnie z treścią zadania liczby mogą być z przedziały 0-1000000, tak więc czapa, to musi być 2 podniesione do potęgi logarytm z 1000000, logarytm ten to 20, a 2^20 = 1048576, zgodnie z artykułem wielkość drzewa będzie równa 2*czapa-1, czyli 2097151. OK, robimy sobie tablicę, która ma tyle liczb, oraz zmienną "czapa", która ma wartość taką, jak wcześniej policzyliśmy ;)
OK, no to niby drzewo mamy, ale co dalej?? Skorzystamy z funkcji, która znajduje element na konkretnym miejscu w drzewie, opisanej w artykule :) w moim programie zwie się ona "mediana_seek" od angielskiego "szukaj mediany", a czego będziemy szukać?? liczby na miejscu (k+1)/2, która zawsze jest medianą ;) Czemu?? jak k=2, to medianą będzie liczba na 3/2=1szym miejscu, a jak k=5, to będzie to liczba na 6/2=3cim miejscu ;)
OK, przepisujemy bezczelnie funkcję z tego arta, dorzucamy nasze warunki do liczenia sumy i voila :)
#include <iostream> using namespace std; const int MAX=2097151; long long suma, best; int tab[MAX], czapa=1048576, liczby[100000], k, n, miejsce; int mediana_seek(int k) //funkcja, która nam znajdzie medianę { int i=1; while(i<czapa) { if (tab[2*i]>=k) i*=2; else { k-=tab[2*i]; i=2*i+1; } } return i-czapa; } int main() { scanf("%d %d", &n, &k); //wczytujemy n i k for (int i=0; i<k; i++) { scanf("%d", &liczby[i]); for (int x=czapa+liczby[i]; x>0; x/=2) //to jest zerżnięta bezczelnie funkcja z arta, która dodaje coś do drzewa ;) tab[x]++; } int mediana=0; mediana=mediana_seek((k+1)/2); //szukamy mediany w pierwszym zestawie for (int i=0; i<k; i++) best+=abs(liczby[i]-mediana); //liczymy pierwszą sumę ruchów jako "best", potem jak znajdziemy lepsze rozwiązanie, to zajmie ono miejsce "best" suma=best; int median_needed=mediana; //median_needed, to mediana najlepszego zestawy, przyda się do wypisania wyników ;) for (int i=k; i<n; i++) { for (int x=czapa+liczby[i-k]; x>0; x/=2) //usuwanie liczby z drzewa tab[x]--; scanf("%d", &liczby[i]); for (int x=czapa+liczby[i]; x>0; x/=2) //i dodawanie nowej ;) tab[x]++; //czas liczyć sumę dla nowego zestawu według wcześniej opisanych kryteriów ;) if (liczby[i-k]==liczby[i]) //dodaj=usun continue; //jak dodajemy i usuwamy to samo, to nie ma sensu dalej myśleć, tylko wziąć kolejny zestaw ;) else if (liczby[i]>mediana && liczby[i-k]>mediana) //dodaj i usun > mediana suma+=liczby[i]-liczby[i-k]; else if (liczby[i]<mediana && liczby[i-k]<mediana) //dodaj i usun < mediana suma+=liczby[i-k]-liczby[i]; else if (liczby[i]==mediana && liczby[i-k]>mediana) //dodaj=mediana usun>mediana suma-=liczby[i-k]-liczby[i]; else if (liczby[i]==mediana && liczby[i-k]<mediana) //dodaj=mediana usun<mediana suma-=liczby[i]-liczby[i-k]; else if (liczby[i]>mediana && liczby[i-k]==mediana) //dodaj>mediana usun=mediana { int temp=mediana; mediana=mediana_seek((k+1)/2); if (k%2==1) suma+=liczby[i]-mediana; else if (liczby[i]==mediana) suma--; else suma=suma-mediana+temp+liczby[i]-mediana; } else if (liczby[i]<mediana && liczby[i-k]==mediana) //dodaj<mediana usun=mediana { int temp=mediana; mediana=mediana_seek((k+1)/2); if (k%2==1) suma+=mediana-liczby[i]; else suma+=temp-liczby[i]; } else if (liczby[i]>mediana && liczby[i-k]<mediana) //dodaj>mediana usun<mediana { int temp=mediana; mediana=mediana_seek((k+1)/2); if (k%2==1) suma=suma-temp+liczby[i-k]+liczby[i]-mediana; else suma-=(temp-liczby[i-k])-(liczby[i]-mediana)+(mediana-temp); } else if (liczby[i]<mediana && liczby[i-k]>mediana) //dodaj<mediana usun>mediana { int temp=mediana; mediana=mediana_seek((k+1)/2); if (k%2==1) suma=suma-liczby[i-k]+temp-liczby[i]+mediana; else suma=suma-liczby[i-k]+temp-liczby[i]+temp; } if (suma<best) //sprawdzamy, czy aktualna liczba ruchów jest lepsza niż dotąd najlepsza ;) { best=suma; miejsce=i-k+1; median_needed=mediana; } } printf("%lld\n", best); //Wypisujemy najmniejsza liczbę ruchów for (int i=0; i<miejsce; i++) printf("%d\n", liczby[i]); //wypisujemy klocki bez zmian aż dojdziemy do miejsca, gdzie zaczyna się najlepszy zestaw for (int i=miejsce; i<miejsce+k; i++) printf("%d\n", median_needed); //wypisujemy najlepszy zestaw for (int i=miejsce+k; i<n; i++) printf("%d\n", liczby[i]); //wypisujemy resztę ;) return 0; }
Tutaj wyniki programu, na który był pomysł na początku (tylko coś mi się widzi, że serwerek wolno chodzi, bo wcześniej miałem 7s, nie 14)
+--------------------------------------+
| 0 | 147 OK | Answer correct |
| 1 | 17 OK | Answer correct |
| 2 | 16 OK | Answer correct |
| 3 | 42 OK | Answer correct |
| 4 | 49 OK | Answer correct |
| 5 | 431 OK | Answer correct |
| 6 | 95 OK | Answer correct |
| 7 | 29 OK | Answer correct |
| 8 | 53 OK | Answer correct |
| 9 | 14334 TL | Time limit exceeded |
| 10 | 13643 TL | Time limit exceeded |
| 11 | 84 OK | Answer correct |
+-----------------------+--------------+
| Statystyki |
+-----------------------+--------------+
| Poprawnych: | 10 |
| Błędnych odpowiedzi: | 0 |
| Poza limitem czasu: | 2 |
| Błędów wykonania: | 0 |
+-----------------------+--------------+
| Czas wykonania |
+-----------------------+--------------+
| Sumaryczny [ms] | 963 |
| Najdłuzszy [ms] | 431 |
| Średni [ms] | 80 |
+-----------------------+--------------+
| Punkty | 83 |
+-----------------------+--------------+
A tutaj "ulepszonego" :)
+--------------------------------------+
| 0 | 192 OK | Answer correct |
| 1 | 16 OK | Answer correct |
| 2 | 19 OK | Answer correct |
| 3 | 20 OK | Answer correct |
| 4 | 20 OK | Answer correct |
| 5 | 254 OK | Answer correct |
| 6 | 58 OK | Answer correct |
| 7 | 18 OK | Answer correct |
| 8 | 25 OK | Answer correct |
| 9 | 617 OK | Answer correct |
| 10 | 242 OK | Answer correct |
| 11 | 20 OK | Answer correct |
+-----------------------+--------------+
| Statystyki |
+-----------------------+--------------+
| Poprawnych: | 12 |
| Błędnych odpowiedzi: | 0 |
| Poza limitem czasu: | 0 |
| Błędów wykonania: | 0 |
+-----------------------+--------------+
| Czas wykonania |
+-----------------------+--------------+
| Sumaryczny [ms] | 1501 |
| Najdłuzszy [ms] | 617 |
| Średni [ms] | 125 |
+-----------------------+--------------+
| Punkty | 100 |
+-----------------------+--------------+
Różnica może mało widoczna, ale jest :)
