X-RLE v0.24.2b Problem Dat je niz "objekata", pri cemu svaki objekat ima neki "tip" (broj u opsegu [A,B]) i "tezinu" (broj u opsegu [C,D]). U nizu medjutim postoje i neki "dzoker" objekti (u daljem tekstu: X-objekti) kojima se moze dodeliti proizvoljni tip. Dalje, ako dva uzastopna objekta imaju isti tip, oni se mogu zameniti jednim objektom toga tipa cija je tezina jednaka zbiru tezina dva polazna objekta. Prosta zamena se, medjutim, vrsi samo ako je zbirna tezina u opsegu [E,F]. Ukoliko je pak zbir tezina dva susedna objekta istog tipa veci od gornje granice F, zbir se mora naknadno "razbijati", odnosno optimalno raspodeliti izmedju dva objekta. Ulazni niz pred pocetak kompresije ne sme sadrzati X-objekte. Nakon kompresije, objekti sa pocetnom tezinom u opsegu [E,F] dobijaju novu, E-1 tezinu, dok objekti polazne tezine u intervalu [1,E-1] ostaju nepromenjeni. Potrebno je, dakle, odrediti tipove "dzoker" objekata tako da nakon izvrsenih zamena i kompresije ukupna tezina objekata bude minimalna. Notacija Algoritam predstavlja varijaciju jednostavne RLE kompresije; posto je RLE zadat kao uslov u zadatku, nije dozvoljeno koriscenje drugih algoritama poput Huffman-ovog kodiranja i pored mnogo veceg stepena kompresije. Radi jednostavnosti, zanemaricemo detalje oko trenutne (ionako nekompletne;) implementacije algoritma i zadrzati se na visem, apstraktnijem nivou, jer je ipak vaznije teoretsko resenje problema. U nastavku se koriste sledece vrednosti: A=0, B=127, C=1, D=256, E=3 i F=256. Za prikazivanje objekata koristicemo sledecu notaciju: || 3 X 124 || => vrednost (tip) objekta [A,B] || ---, ---, --- || || 16 8 1 || => tezina pre kompresije [C,D] || || 2 <= ? => 1 => tezina posle kompresije (za X tip - neodredjena) `||' predstavlja granicu izmedju dva nezavisna dela ulaznog niza ("sekcija"). 4 X 16 X 10 || 7 ... ---, ---, ---, ---, ---- || --- ... 2 1 17 254 237 || 73 Ovde je granica izmedju objekta tipa `10' i objekta tipa `7', jer sta god da uradimo u prvom delu niza (`4'-`10'), odnosno kako god da grupisemo (pridruzimo) X-objekte, nikako necemo uticati na objekte iza poslednje "desetke". Jasno, ovakva granica se javlja izmedju svaka dva objekta razlicitog tipa od kojih nijedan nije "dzoker". Da bismo izbegli specijalne slucajeve, ogranicicemo se na nizove koji nikada ne pocinju (niti se zavrsavaju) X objektom, kada se svi uniformno obradjuju. Primeri #1 --------------------------------------------------------------------------- Ulazni niz: || 5 <= X 6 || || ---, ---, --- || || 1 3 256 || Izlazni niz: || 5 6 || || ---, --- || || 4 256 || # tezina pre kompresije 2 2 # tezina posle kompresije # ukupno: [4] #2 --------------------------------------------------------------------------- || 5 X 6 || || ---, ---, --- || || 1 3 7 || a) || 5 <= X 6 || || 5 6 || || ---, ---, --- || => || ---, --- || || 1 3 7 || || 4 7 || 2 2 # ukupno: [4] b) || 5 X => 6 || || 5 6 || || ---, ---, --- || => || ---, --- || || 1 3 7 || || 1 10 || 1 2 # ukupno: [3] #3 --------------------------------------------------------------------------- || 5 X 6 X 8 || || ---, ---, ---, ---, --- || || 1 3 7 249 256 || a) || 5 X => 6 X 8 || || 5 6 <= X 8 || || ---, ---, ---, ---, --- || => || ---, ---, ---, --- || => || 1 3 7 249 256 || || 1 10 249 256 || || 5 6 6 8 || => || ---, ---, ---, --- || || 1 256 3 256 || 1 2 2 2 # ukupno: [7] b) || 5 <= X 6 X 8 || || 5 6 <= X 8 || || ---, ---, ---, ---, --- || => || ---, ---, ---, --- || => || 1 3 7 249 256 || || 4 7 249 256 || || 5 6 8 || => || ---, ---, --- || || 4 256 256 || 2 2 2 # ukupno: [6] #4 --------------------------------------------------------------------------- Nizu iz primera 1 dodajemo jos 3 objekta. || 5 X 6 X 3 || || ---, ---, ---, ---, --- || || 1 3 256 10 254 || Postupamo analogno resenju primera 1: a) || 5 <= X 6 <= X 3 || || 5 6 6 3 || || ---, ---, ---, ---, --- || => || ---, ---, ---, --- || || 1 3 256 10 254 || || 4 256 10 254 || 2 2 2 2 # ukupno: [8] Ako se odlucimo za drugo, manje ocigledno resenje, ipak dobijamo vecu ustedu: b) || 5 X => 6 X 3 || || 5 6 6 <= X 3 || || ---, ---, ---, ---, --- || => || ---, ---, ---, ---, --- || => || 1 3 256 10 254 || || 1 256 3 10 254 || || 5 6 6 3 || => || ---, ---, ---, --- || || 1 256 13 254 || 1 2 2 2 # ukupno: [7] # --------------------------------------------------------------------------- Zadatak Prototip potrebne funkcije: typedef struct _rle_obj { int type; /* [A,B] | JOKER */ int weight; /* [C,D] */ struct _rle_obj *prev; struct _rle_obj *next; } rle_obj; void xreplace(rle_obj *list); Funkcija, dakle, treba da eliminise sve elemente tipa JOKER iz ulaznog niza (liste), pridruzujuci ih susednim objektima, ali tako da ukupan zbir tezina posle kompresije bude minimalan. Dobijena lista se kasnije prosledjuje trivijalnoj funkciji `rle_compress()'. Slijepcevic Dusan, 2001. Hvala: Aleksandar B. Samardzic Djordje Stakic