Zadanie

Predstavte si post- a zároveň pred- apokalyptický svet, v ktorom ľudstvo skoro vymrelo od hladu (preto post-) a čoskoro pravdepodobne aj vymrie (preto pred-). Hoci ste špičkoví programátori, musíte proti svojej vôli pracovať v poľnohospodárstve, aby ste mali čo jesť vy, vaše deti a iní príbuzní, nehovoriac o zvyšku ľudstva.

Keďže ľudstvo zanevrelo na vedu, a tak odsúdilo Zem k úplnej záhube, jedinou nádejou na prežitie (okrem pestovania kukurice) je opustenie našej zničenej planéty. Aby sme Zem mohli opustiť, musíme najprv nájsť nejakú inú prívetivú planétu a chceme si byť istí, že bude skutočne obývateľná.

Problémom je, že všetky takéto planéty sú veľmi ďaleko a tak nám naše sondy vedia posielať len veľmi malé množstvo informácií. Mohli by sme sa uchýliť k tomu, že nám sondy budú posielať len akési čísla a písmenká o prívetivosti planét, ale ako sa hovorí: ,,Lepšie raz vidieť, ako stokrát počuť.’’

Čo ak na jednej planéte rastú kokosové palmy, šumí more a príjemne hreje neSlniečko a na druhej rastú kaktusy, šumí piesok a nepríjemne páli obrovská ohnivá guľa a my z oboch planét dostaneme rovnakú správu? To teda nie! Ak raz niekto bude posielať takéto sondy, nedajbože aj s ľudskou posádkou, určite im treba dať aj foťáky a nejak vymyslieť, aby sa dali fotky posielať.

Keďže vás úplne prestalo baviť pestovanie kukurice a zatúžili ste po troške dobrodružstva, na večernej prechádzke lesom ste sa snažili vlámať na oplotený súkromný pozemok. Za trest vás okamžite najali majitelia pozemku a za úlohu vám dali vyriešiť problém vesmírnej komunikácie: Ako posielať čo najkvalitnejšie fotografie v malom množstve dát?

Musíte to vymyslieť rýchlo. Majú vaše deti. A predsa len, je to zábavnejšie ako jazdenie na kombajne.

Úloha

Dostanete čiernobiely obrázok v textovom formáte veľkosti \(w\times h\). Vašou úlohou je skomprimovať obrázok pomocou pár referenčných bodov tak, aby sa čo najviac podobal originálu.

Komprimovaný obrázok pozostáva z najviac \(w+h\) bodov, pričom každý bod je popísaný súradnicami \(x, y\) a intenzitou \(I\).

Pôvodný obrázok sa dekompresiou získa tak, že intenzita referenčných bodov zostane rovnaká a intenzita každého zvyšného pixelu sa vypočíta ako vážený priemer intenzít referenčných bodov, váhovaných prevrátenou hodnotou druhej mocniny vzdialenosti. Teda intenzitu pixela \(x,y\) z referenčnýxh bodov \((x_1,y_1,I_1),\dots,(x_n,y_n,I_n)\) určíme ako: \[I = \frac{\frac{I_1}{dx_1^2 + dy_1^2} + \frac{I_2}{dx_2^2 + dy_2^2} + \dots +\frac{I_n}{dx_n^2 + dy_n^2}} {\frac{1}{dx_1^2 + dy_1^2} + \frac{1}{dx_2^2 + dy_2^2} + \dots +\frac{1}{dx_n^2 + dy_n^2}} \] kde \(dx_i = (x-x_i)\) a \(dy_i = (y-y_i)\).

Obrázky

Stiahni si zip archív z našej stránky. V ňom sa nachádzajú tri cvičné obrázky a 15 súťažných obrázkov. Každý obrázok sa nachádza vo formáte .jpg (klasický JPEG formát) a v takomto formáte .in:

Prvý riadok .in súboru obsahuje dve čísla \(w, h\) (\(1 \leq w,h \leq 500\)) oddelené medzerou – šírku a výšku obrázku.

Nasleduje \(w\times h\) čísel \(p_{i}\), ktoré môžu byť oddelené medzerou, alebo znakom nového riadku. Každé číslo \(0 \leq p_{i} \leq 255\) vyjadruje intenzitu/odtieň sivej pixelu obrázku. Pixely sú zapísané v poradí zľava doprava, zhora dole, teda tak, ako by ste ich normálne čítali.1

0 je čierna, 255 je biela, čísla medzi určujú svetlejšie a tmavšie odtiene sivej.

Odovzdávanie

Odovzdáva sa zip archív, ktorý obsahuje súbory 01.out, 02.out, atď až po 15.out. Nemusíte odovzdať všetky súbory, body dostanete za tie súbory, ktoré sa v archíve nachádzajú. (Ako obyčajne, do výsledkovky sa počíta len posledný odovzdaný zip archív, takže v ňom je odporúčané mať všetkých 15 súborov). Môžete do archívu pribaliť aj 00.sample.*.out súbory, ale tieto sú len cvičné a nedostanete za ne body.

Každý z odovzdaných súborov musí mať nasledovný formát:

Na prvom riadku sa nachádza číslo \(n \leq w+h\) – počet bodov, ktorými chcete obrázok popísať.

Následne na \(n\) riadkoch sú po 3 čísla oddelené medzerami: \(x, y, I\) – súradnice a intenzity referenčných bodov. Zadané body musia ležať v obrázku, teda \(1 \leq x \leq w, 1 \leq y \leq h\). Intenzity musia byť v rozmedzí od \(0\) po \(255\) vrátane.

Hodnotenie

Každý obrázok sa hodnotí samostatne. Na základe referenčných bodov obrázok dekomprimujeme a porovnáme ho s originálom pixel po pixeli.
Pre obrázok vypočítame strednú kvadratickú odchýlku na základe rozdielov intenzít pixelov, teda sčítame druhé mocniny rozdielov intenzít a na záver výsledok predelíme počtom pixelov obrázku a odmocníme.

Za každý obrázok dostanete nejaký počet bodov od 0 po 1, podľa toho ako malá je vaša kvadratická odchýlka v porovnaní s referenčnou. Ak je vaša odchýlka \(o\) a referenčná odchýlka je \(r\), tak počet bodov, ktoré dostanete bude \(\max(0, min(1, \frac{50+r-o}{50}))^2\), čo v praxi znamená, že plný počet bodov máte ak ste aspoň takí dobrí ako referenčná odchýlka a 0 bodov máte ak ste aspoň o 50 horší. Body, ktoré takto dostanete vám ešte nemusia ostať, zmenia sa, keď sa zmení referenčná odchýlka.

V tejto úlohe budete súťažiť proti sebe, takže referenčná odchýlka sa vypočíta na základe najlepšieho odovzdaného riešenia. Počas behu série budeme odchýlku aktualizovať približne raz za týždeň a po skončení série ju aktualizujeme znova a vypočítame finálne body.

Keďže neodovzdávate programy a nás zaujíma, ako úlohu riešite, môžete k úlohe odovzdať aj popis, kde stručne popíšete, ako ste úlohu riešili a priložíte zdrojové kódy programov, ktoré ste pri riešení použili. Za popis môžete získať 3 body. (Nemusíte odhadovať časovú zložitosť ani dokazovať správnosť riešenia, jednoducho napíšte, čo ste robili.)

Príklady s cvičnými obrázkami

Input:

7 7
255 255 255 255 255 255 255
255 255 0 255 0 255 255
255 255 255 255 255 255 255
255 0 255 255 255 0 255
255 255 0 255 0 255 255
255 255 0 0 0 255 255
255 255 255 255 255 255 255

Output:

9
1 1 255
7 1 255
3 2 0
5 2 0
4 3 255
3 5 0
5 5 0
1 7 255
7 7 255

Stredná kvadratická odchýlka tejto kompresie je 120,597746.

Input:

3 3
255 255 255
255 255 255
255 255 255

Output:

1
2 2 0

Úplne zlá kompresia má kvadratickú odchýlku 255. Ak by sme zmenili zadanú intenzitu na 255, kompresia by bola dokonalá a mala by odchýlku 0.

Na prvom obrázku je originálna fotografia, na druhom môžete vidieť referenčné body, ktorými sa obrázok komprimuje. Na posledom obrázku vidíte, ako by vyzeral obrázok po rekonštrukcii z referenčných bodov. Kvadratická odchýlka tejto kompresie je 49.131287. Vstupný súbor tohto obrázku si viete stiahnuť tu, a výstup našej nedokonalej kompresie tu.


  1. \(p_i\) označuje intenzitu pixelu \([(i\:\mathrm{mod}\: w)+1,(i\: \mathrm{div}\: w)+1]\), kde mod je zvyšok po delení, div je celočíselné delenie a \(0 \leq i \leq w\times h -1\)

Už z prvého pohľadu na túto úlohu by malo byť jasné, že si môžeme nechať zájsť chuť na akékoľvek exaktné optimálne riešenie. Spôsob, akým vyrobíme výsledný obrázok z jeho komprimovanej podoby, nemá žiadne dobré vlastnosti, ktoré by sme vedeli využiť.

Čo nám teda ostáva? Prezerať nejaké možné riešenia a vybrať si najlepšie, ktoré sa nám podarí nájsť.

Hm, ale ani to nevyzerá veľmi nádejne. Keď máme obrázok rozmerov \(500\times 500\) a v ňom môžeme zvoliť \(1000\) referenčných bodov, existuje približne \(1000^{250\,000}\) možností ako obrázok skomprimovať. Skúšanie všetkých možností hrubou silou teda tiež nevyzerá reálne. Vyzerá to, že predsa len budeme musieť aj trochu myslieť.

Jedna z vecí, ktoré si môžeme všimnúť, je samotný vzorec zo zadania. Keď si rozmyslíme, ako funguje, prídeme na to, že síce každý referenčný bod ovplyvňuje celý obrázok, ale najväčší vplyv má vo svojom bezprostrednom okolí – a naopak, ďaleko od neho je už jeho vplyv pomerne malý. Asi teda príliš nepokazíme, keď si to predstavíme tak, že každý referenčný bod ofarbí len svoje okolie, v každom smere po najbližšie iné referenčné body.

Takéto pozorovanie nám už umožní vyrobiť nejaké prvé jednoduché riešenia. Napríklad keď máme obrázok rozmerov \(n\times n\), tak môžeme referenčné body rozmiestniť pravidelne do mriežky rozmerov \(\sqrt{2n}\times\sqrt{2n}\). Ich intenzity určíme napríklad tak, že pre každý referenčný bod zoberieme priemer jeho okolia. Výsledný obrázok síce nebude žiadna výhra, ale programuje sa to rozumne ľahko a nejaké body za to budú.

O čosi lepšie riešenie zrejme vieme dosiahnuť tak, že referenčné body nebudeme rozmiestňovať rovnomerne, ale budeme ich dávať pažravo vždy tam, kde ich je najviac treba. Ako na to? Budeme referenčné body pridávať postupne po jednom. Vždy, keď pridávame nový, vyskúšame všetkých \(256n^2\) možností, kam ho dať. Zakaždým si prepočítame, akú chybu bude mať výsledné riešenie. No a následne zoberieme tú polohu, ktorá viedla k najmenšej chybe.

Takéto riešenie má síce polynomiálnu časovú zložitosť, je však stále dosť pomalé. Na to, aby bolo aspoň trochu použiteľné aj pre obrázky väčšie ako \(10\times 10\), ho treba implementovať šikovne. Urobíme preto jeden trik, ktorý odteraz budú používať aj všetky ďalšie riešenia: Keď už máme nejaké referenčné body, budeme si pamätať pre každý pixel obrázka aj súčet hodnôt (intenzita referenčného bodu krát jeho váha), aj súčet samotných váh. Z nich vieme aktuálnu intenzitu pixelu vypočítať v konštantnom čase. Čo je však dôležitejšie, keď pridáme (alebo odoberieme alebo presunieme) jeden nový referenčný bod, vieme každý pixel v konštantnom čase prepočítať. Nemusíme už teda strácať čas tým, že po každej zmene našej komprimovanej reprezentácie budeme vyhodnocovať celé riešenie od začiatku.

S týmto trikom potrebujeme na vyššie popísané riešenie zhruba \(512n^5\) krokov výpočtu. To je OK pre menšie obrázky, ale pre \(500\times 500\) by takéto riešenie bežalo rádovo roky. Niekde teda treba ušetriť. Kde? Môžeme napríklad prezerať menej možných polôh nového referenčného bodu, z intenzít pixelov v jeho okolí môžeme odhadnúť malý interval intenzít, ktoré má zmysel skúšať pre referenčný bod… fantázii sa medze nekladú.

Lezenie na kopec

My by sme ale chceli nejaký šikovnejší postup, ktorý bude výstupy dávať rýchlejšie a navyše budú mať lepšiu kvalitu. Ako na to? Jednou zo základných techník číselnej optimalizácie je tzv. hill climbing, v preklade teda lezenie na kopec.

Komprimovaný obrázok je tvorený \(6n\) číslami: pre každý z \(2n\) referenčných bodov potrebujeme povedať jeho súradnice a jeho intenzitu. Predstavme si teraz týchto \(6n\) čísel ako akési “GPS súradnice” nejakého “bodu” vo “svete”. Samozrejme, tento svet nie je dvojrozmerný (ako u klasických GPS súradníc) ale je až \(6n\)-rozmerný – to však v našich predstavách spokojne odignorujeme.

Každému “bodu” teraz ešte priradíme “nadmorskú výšku”. Tá bude zodpovedať kvalite príslušného riešenia: čím lepšie riešenie je tvorené súradnicami daného bodu, tým vyššia bude nadmorská výška v ňom.

V našej úlohe môžeme urobiť jedno dôležité pozorovanie: keď spravíme malú zmenu “súradníc bodu” (teda keď buď trošku posunieme jeden referenčný bod alebo trošku zmeníme jeho intenzitu), spôsobíme tým len malú zmenu kvality riešenia. Celá naša krajina, ktorú si predstavujeme, je teda v podstate pekná spojitá.

To, čo by sme v ideálnom prípade chceli, je nájsť najvyšší bod celej krajiny – globálne maximum výšok, teda optimálne riešenie. Toto môže byť veľmi ťažké, a tak sa uspokojíme s o čosi horším výsledkom: nájdeme aspoň nejaké kopce, nájdeme vrchol každého z nich (lokálne maximum) a spomedzi nich si vyberieme ten najlepší.

Ako na to? Začneme vždy v náhodnom bode našej krajiny. (Zvolíme si teda náhodne súradnice referenčných bodov aj ich intenzity.) Tento bod zrejme leží na úbočí nejakého kopca. Teda existujú nejaké smery, ktorými keď sa po krajine pohneme, pôjdeme hore kopcom. Dobrý spôsob, ako liezť hore kopcom, je taký, že v každom kroku si vyberieme ten smer, ktorý vedie najstrmšie dohora. Čo to znamená v našej úlohe? Vyskúšame nejaké malé zmeny (trochu posunúť alebo prefarbiť niektorý referenčný bod). Ak žiadna z nich riešenie nezlepší, sme už na vrchole kopca. A ak ho nejaké zmeny zlepšia, tak si vyberieme tú z nich, ktorá ho zlepší najviac. Tú aplikujeme a postup lezenia na kopec opakujeme z nového bodu.

Simulované žíhanie

Naše výstupy sme generovali ešte o čosi šikovnejším postupom. V angličtine je známy pod názvom simulated annealing. Ide o podobnú heuristiku ako lezenie na kopec, len o čosi zložitejšiu, ale zato často o čosi účinnejšiu. (Mimochodom, ide o postup, ktorý bol spoluvynájdený u nás – v roku 1985 ho vymyslel Vlado Černý a aplikoval ho na riešenie problému obchodného cestujúceho.)

Na rozdiel od lezenia na kopec, ktoré sa po krajine pohybovalo “spojito”, pri simulovanom žíhaní po krajine viac “skáčeme”. Na začiatku je povolená veľkosť skoku veľká (teda v našom prípade môžeme napr. zobrať jeden referenčný bod a ľubovoľne mu zmeniť všetky parametre). Po každom skoku vyhodnotíme, či je nové riešenie lepšie alebo horšie ako to staré. Lepšie riešenie si necháme s veľkou pravdepodobnosťou, horšie s malou. Teda ak je napr. nové riešenie horšie od toho čo práve máme, s pravdepodobnosťou 90 percent ostaneme kde sme, ale s pravdepodobnosťou 10 percent aj tak prejdeme do nového bodu. (Toto je dôležité aby sme mali šancu dostať sa preč z nejakého “malého miestneho pohoria”. Pravdepodobnosti samozrejme nemusia byť 10-90, môžu napr. závisieť aj od rozdielu kvality oboch riešení.)

Ako proces hľadania riešenia pokračuje, postupne zmenšujeme povolenú veľkosť skoku. Keďže preferujeme lepšie riešenia pred horšími, časom sa s veľkou pravdepodobnosťou dostaneme do “hornatej oblasti” a zároveň veľkosť skoku klesne natoľko, že už z nej neodídeme – ak by sme aj skočili mimo, ďalší skok nás zase skoro určite vráti späť. A tam sa vlastne stále deje to isté: v rámci oblasti nájdeme nejaké miesto, kde sú kopce ešte vyššie, a keď časom veľkosť skoku ešte viac klesne, už tam ostaneme.

Ak to príliš nedáva zmysel, pozrite si animovaný gif na Wikipédii.

No a celý tento proces môžeme samozrejme veľakrát nezávisle na sebe spustiť a vybrať najlepšie z takto zostrojených riešení. Samozrejme, ani táto technika nie je všemocná a nemáme žiadnu záruku, že nájde globálne optimum, ani záruku, ako ďaleko bude nami nájdené riešenie od globálneho optima.

#include <cmath>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int PHASE_COUNT = 6;
const int STARTING_MAX_JUMP = 1 << PHASE_COUNT;
const int STARTING_MAX_FADE = 1 << PHASE_COUNT;
const int STEP_COUNT = 5000;

typedef pair<int,int> point;
typedef pair<point,int> refpoint;

int R, C;
vector< vector<int> > input;

vector<refpoint> best;
double best_score;

vector< vector<double> > isum, wsum;

void load() {
    cin >> C >> R;
    input.resize(R, vector<int>(C,0));
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) cin >> input[r][c];
    isum.resize( R, vector<double>(C,0) );
    wsum.resize( R, vector<double>(C,0) );
}

int square_dist(const point &A, const point &B) {
    return (A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second);
}

void add_reference_point(const refpoint &rp, int weight=1) {
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
        int sd = square_dist( point(r,c), rp.first );
        double w = (sd == 0 ? 1000 : 1./sd);
        isum[r][c] += rp.second * w * weight;
        wsum[r][c] += w * weight;
    }
}

void get_intensities(const vector<refpoint> &attempt) {
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) { isum[r][c] = 0., wsum[r][c] = 0.; }
    for (auto rp : attempt) add_reference_point(rp);
}

double score() {
    double diff = 0.;
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
        double in = isum[r][c] / wsum[r][c];
        diff += (in - input[r][c])*(in - input[r][c]);
    }
    return sqrt( diff / R / C );
}

int main() {
    srand(time(NULL));
    load();
    
    vector<refpoint> attempt;
    for (int n=0; n<R+C; ++n) attempt.push_back( refpoint( point( rand()%R, rand()%C ), rand()%256 ) );

    get_intensities(attempt); 
    best_score = score();
    best = attempt;

    int max_jump = STARTING_MAX_JUMP, max_fade = STARTING_MAX_FADE;

    for (int phase=0; phase<PHASE_COUNT; ++phase) {
        attempt = best;
        double att_score = best_score;
        get_intensities(attempt);

        for (int step=0; step<STEP_COUNT; ++step) {
            
            vector<refpoint> new_attempt = attempt;
            
            int n = rand() % new_attempt.size();
            while (true) {
                int nr = attempt[n].first.first  - max_jump + rand()%(2*max_jump+1);
                int nc = attempt[n].first.second - max_jump + rand()%(2*max_jump+1);
                int ni = attempt[n].second - max_fade + rand()%(2*max_fade+1);
                new_attempt[n] = refpoint( point(nr,nc), ni );
                if (0 <= nr && nr < R && 0 <= nc && nc < C && 0 <= ni && ni < 256) break;
            }

            add_reference_point( attempt[n], -1 );
            add_reference_point( new_attempt[n], +1 );
            double new_score = score();

            if (new_score < best_score) {
                best_score = new_score;
                best = new_attempt;
            }

            bool revert = false;
            if (new_score < att_score && rand()%10 >= 9) revert = true;
            if (new_score >= att_score && rand()%10 >= 0) revert = true;
            if (revert) {
                add_reference_point( attempt[n], +1 );
                add_reference_point( new_attempt[n], -1 );
            } else {
                att_score = new_score;
                attempt = new_attempt;
            }
        }

        max_jump /= 2;
        max_fade /= 2;
    }

    cout << (R+C) << endl;
    for (auto rp : best) cout << (1+rp.first.second) << " " << (1+rp.first.first) << " " << rp.second << endl;
}

Hodnotenie

Bodovanie praktickej časti úlohy je nasledovné. Každý vstup sa hodnotí samostatne a dá sa zaň získať 1 bod. Referenčná odchýlka \(r\) (počet bodov potrebný na plný počet) sa vypočíta ako aritmetický priemer najlepšej účastníckej a najlepšej vedúcovskej odchýlky. Keď vaša odchýlka v konkrétnom vstupe bola \(o\), tak ste dostali \((\max(0, \min(50, r-o+50))\cdot 0.02)^2\) bodov.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.