Zadanie

Usáma dostal na Vianoce obrovskú kopu darčekov. A to vôbec nepreháňam! Bolo ich tak veľa, že ich ani nestihol začať rozbaľovať. Usáma totiž vie, že rozbaľovať darčeky nemôže len tak. Musí postupovať podľa špeciálneho, ním patentovaného postupu, ktorý je veľmi zložitý na prípravu.

Po skúsenostiach z predchádzajúcich Vianoc si popri práci zhotovil program, ktorý mu vie o každom darčeku celkom dobre predpovedať, koľko radosti získa z jeho otvorenia1. Podľa svojho programu si svoje darčeky usporiadal do radu s rastúcou predpovedanou radosťou, dokonca mu to tento rok vyšlo tak pekne, že každý darček mal inú predpovedanú radosť a boli to čísla od \(1\) po počet darčekov. Z dĺžky tohto radu sa mu však zamotala hlava a rozhodol sa nechať si otváranie na ďalší deň.

Prišlo vytúžené ráno a Usáma celý naradostený vybehol z postele. Čakalo ho však nemilé prekvapenie. Jeho precízne zostrojený rad bol celý poprehadzovaný. K jeho radu darčekov sa totiž dostala jeho snúbenica Maru a preusporiadala ho podľa kto vie čoho2. Rozhodol sa, že namiesto toho, aby darčeky začal otvárať preusporiadané, alebo že by medzi nimi pobehoval ako veverička na káve, zoradí si ich tak, aby sa ich poradie páčilo v každom momente aj Maru. Aby s tým nemal toľko roboty, rozhodol sa, že to celé docieli iba vymieňaním dvojíc darčekov.

Začal teda vymieňať dvojice darčekov a všimol si, že občas mu to Maru dovolí, ale občas ich hneď vymení späť. Po chvíli testovania si všimol, že Maru vadí, ak vymieňa darčeky na na určitých dvojiciach pozícií. Pre každú dvojicu pozícií si teda zistil, či mu Maru dovolí vymeniť darčeky na nej, alebo nie.

Keďže Maru nezaujímajú darčeky, ktoré vymieňa, ale len ich pozície, dá sa ľahko oklamať. Predstavme si, že na pozíciách \(1\), \(2\) a \(3\) sú darčeky A, B a C, čo si môžeme značiť ako (A, B, C). Usáma vie, že môže vymeniť darčeky na pozíciách \((1,2)\), \((2,3)\), ale v žiadnom prípade nemôže vymeniť \((1,3)\). Napriek tomu vie dostať stav (C, B, A), akurát ho to bude stáť viac operácií. Najskôr totiž vymení prvý darček z druhým, potom druhý s tretím (v tomto okamihu vyzerá jeho rad ako (B, C, A)) a opäť prvý z druhým.

Bohužiaľ, napriek tomu sa jeho darčeky nemusia dať zoradiť do pôvodného stúpajúceho poradia. Rád by sa však k tomuto poradiu aspoň čo najviac priblížil. Pokúste sa mu pomôcť.

Úloha

Usáma dostal \(n\) darčekov. Postupnosť čísiel \(1\)\(n\), kde sa každé číslo nachádza práve raz, nazveme permutácia. Na vstupe dostanete permutáciu \(n\) čísiel, ktorá predstavuje rad v momente keď sa Usáma zobudil. Pre každú dvojicu pozícií sa naviac dozviete, či môžete vymeniť prvky na týchto pozíciách alebo nie.

Vašou úlohou je nájsť najmenšiu permutáciu, ktorú môžete vytvoriť z permutácie na vstupe len výmenou dovolených dvojíc. Permutácia \(A\) je menšia ako permutácia \(B\), ak má na prvej pozícii, kde sa tieto dve permutácie líšia, menšiu hodnotu.

Polovica bodov sa dá získať za riešenie, ktoré predpokladá, že ak sa dajú vymeniť darčeky na daných pozíciách nejakou postupnosťou výmen, tak sa dajú vymeniť aj priamo. Príklad z rozprávky túto vlastnosť nemá, keďže prvky na pozíciach \(1\) a \(3\) sa dajú vymeniť nejakou postupnosťou výmen, ale nie priamo.

 Formát vstupu

Na prvom riadku dostanete číslo \(n\) (\(1 \leq n \leq 1\,000\)) udávajúce počet čísel v permutácii. V druhom riadku bude \(n\) čísel z rozsahu \(1\)\(n\), každé práve raz, udávajúce počiatočnú permutáciu.

Nasleduje \(n\) riadkov, v každom z nich \(n\) číslic, každá buď 0 alebo 1, s nasledujúcim významom: Ak je v \(i\)-tom riadku a \(j\)-tom stĺpci 1, tak je možné priamo vymeniť darček na pozícii \(i\) s darčekom na pozícii \(j\). Môžete predpokladať, že číslo v \(i\)-tom riadku a \(j\)-tom stĺpci sa zhoduje s číslom v \(j\)-tom riadku a \(i\)-tom stĺpci. Taktiež môžete predpokladať, že v \(i\)-tom riadku a \(i\)-tom stĺpci bude vždy 1.

Formát výstupu

Vypíšte jeden riadok a v ňom \(n\) čísel, najmenšiu permutáciu, korú vie Usáma zostrojiť z pôvodnej, vymieňaním iba povolených dvojíc pozícií.

Hodnotenie

Je päť sád vstupov.

Počet darčekov v týchto sadách je postupne 10, 50, 200, 500, 1000. V prvej, druhej a štvrtej sade navyše platí, že ak sú dve čísla vymeniteľné nejakou postupnosťou výmen, dajú sa vymeniť aj priamo.

Príklady

Input:

3
3 2 1
110
111
011

Output:

1 2 3

Darčeky 3 a 1 nemôže Usáma vymeniť priamo, ale môže ich vymeniť pomocou druhého darčeka.

Input:

3
2 3 1
100
010
001

Output:

2 3 1

Tu si Usáma nijako neporadí, nemôže totiž nič vymieňať.

Input:

4
2 3 1 4
1001
0110
0110
1001

Output:

2 1 3 4

  1. To viete, ak dostane od rodičov niečo veľkosti svetra, vie takmer na istotu povedať, že ide o sveter. Ale od niekoho iného môže ísť o niečo vskutku exotické.

  2. Ženy.

Riešenie tejto úlohy pozostávalo z viacerých krokov. Najprv sa teda pozrieme, aké riešenie vám stačilo na polovicu bodov a nakoniec sa pozrieme na celý problém.

Zjednodušená úloha

Ľahšou úlohou bolo vyriešiť problém, pokiaľ pre každú pozíciu vieme bez akýchkoľvek výpočtov povedať, s ktorými pozíciami ju vieme vymeniť. Celkom zjavne najmenšia permutácia vznikne tak, že na jej prvé miesto dáme najmenšie možné číslo. Podobne na každú ďalšiu pozíciu chceme dať najmenšie možné číslo, pričom niektorým číslam sme už priradili ich pozíciu.

To nám dáva priamočiary postup, ako našu permutáciu vygenerovať. Postupne spracujeme pozície zľava doprava. Pre každú pozrieme všetky pozície od nej ďalej, z nich vyberieme pozíciu s najmenším číslom vymeníme čísla na týchto dvoch pozíciach. Takto dostaneme riešenie úlohy v časovej zložitosti \(O(n^2)\). Ak navyše riadky matice zo vstupu spracujeme priebežne, bude nám stačiť lineárna pamäťová zložitosť.

Teraz sa na to pozrieme z inej strany. Rozoberme si pozície na skupiny tak, že pozície v jednej skupine sú vymeniteľné každá s každou, ale s nijakou mimo tejto skupiny. Keď teraz začneme vypĺňať našu výslednú permutáciu od prvej pozície, čo môžeme spraviť, je pozrieť sa, do ktorej skupiny daná pozícia patrí a zo všetkých nepoužitých čísel tejto skupiny tam presunúť to najmenšie. Nakoniec si už len všimneme, že v riešení sme čísla vrámci jednej skupiny vlastne usporiadali podobným spôsobom, ako funguje minsort. Neskôr to využijeme.

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main () {
    int n, x;
    scanf("%d", &n);
    vector <int> permutacia(n);
    vector <bool> riadok(n);

    //nacitame povodnu permutaciu
    for (int i = 0; i < n; i++) {
        scanf("%d", &permutacia [i]);
    }
    
    //spracujeme po poziciach, zlava doprava
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {

            //nacitame, s ktorymi poziciami sa i-ta moze vymenit
            scanf("%1d", &x);
            riadok [j] = (x == 1);
        }

        //zistime, ake najmensie cislo vieme dostat na i-tu poziciu
        //z este nepouzitych
        int najmensia_pozicia = i;
        for (int j = i+1; j < n; j++) {
            if (riadok [j] && permutacia [najmensia_pozicia] > permutacia [j])
                najmensia_pozicia = j;
        }

        //a vymenime
        swap(permutacia [i], permutacia [najmensia_pozicia]);
    }

    //nakoniec vsetko vypiseme a dame si pozor na medzeru
    //na konci riadka
    for (int i = 0; i < n-1; i++) printf("%d ", permutacia [i]);
    printf("%d\n", permutacia [n-1]);
}

Grafy

Tu si rozoberieme, čo budeme rozumieť pod pojmom graf, cesta v grafe a komponent grafu. Ďalej sa pozrieme na prehľadávanie grafu, ktorým budeme hľadať komponenty. Ak sú vám tieto pojmy známe, odporúčam preskočiť túto podkapitolu.

Graf je štruktúra pozostávajúca z vrcholov a hrán, kde hrany spájajú dvojicu vrcholov. Prirovnať si to môžeme k nejakej cestnej sieti, kde vrcholmi budú mestá pospájané asfaltkami.

Postupnosť vrcholov, kde každé dva po sebe idúce vrcholy sú spojené hranou, začínajúcu vrcholom \(a\) a končiacu vrcholom \(b\), budeme volať cesta medzi \(a\) a \(b\). Množinu vrcholov, pre ktorú existuje cesta medzi ľubovoľnými dvoma vrcholmi tejto množiny, ale neexistuje žiadna cesta medzi vrcholom z tejto množiny a vrcholom mimo tejto množiny, budeme nazývať komponent grafu.

Ešte si popíšeme, ako zistiť, aké vrcholy ležia v tom istom komponente, ako nejaký zadaný vrchol grafu. Použijeme rekurzívnu funkciu, ktorá ako argument dostane vrchol, ktorý má spracovať a rekurzívne sa zavolá do všetkých ešte neprehľadaných vrcholov, ktoré s ním susedia. K zisteniu, či nejaký vrchol ešte nebol prehľadaný, bude naša funkcia používať jedno globálne pole.

Permutácia ako graf

Tu sa najprv poriadne popozeráme, ako vlastne môžeme narábať s permutáciou v nezjednodušenej verzii úlohy. K tomu sa na ňu pozrieme ešte z iného uhla, predstavíme si to celé ako graf, ktorého vrcholmi budú pozície v našej permutácii a medzi dvoma pozíciami bude hrana, pokiaľ môžeme ich čísla priamo vymeniť.

Keď sa pozrieme na komponenty takéhoto grafu, zistíme, že vhodnou postupnosťou výmen sme schopní vytvoriť ľubovoľné preusporiadanie čísel v jednom komponente (a celkom zjavne do neho nedokážeme dostať číslo z iného komponentu). Ukážeme si, ako vymeniť ľubovoľné dve čísla v tomto komponente. Pomocou dostatočného počtu takýchto výmen by sme už dokázali bez problémov ľubovoľné rozloženie čísel naozaj zmeniť na ľubovoľné iné.

Vezmime si nejakú cestu medzi pozíciami, ktoré chceme vymeniť. Ak vymeníme čísla na prvej a druhej, potom na druhej a tretej a tak ďalej, až na predposlednej a poslednej pozícii z tejto cesty, docielime, že prvý prvok bude na konci, tam kde ho chceme mať a posledný bude na predposlednej pozícii. Potom môžeme podobne presunúť číslo z predposlednej pozície (čiže to, ktoré bolo pôvodne na konci) na prvú pozíciu, čím naozaj ostanú všetky okrem prvého a posledného čísla na svojej pozícii a prvé a posledné budú vymenené1.

Tu už len využijeme riešenie ľahšej podúlohy. Stačí nám prehľadaním zistiť, ktoré pozície sú v tom istom komponente a potom v každom komponente usporiadať čísla od najmenšieho po najväčšie, k čomu môžeme použiť ľubovoľný nanajvýš kvadratický algoritmus.

Celé to bude fungovať s časovou zložitosťou \(O(n^2)\) a rovnakou pamäťovou zložitosťou.

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector <int> permutacia, visited, values;
vector <vector <bool> > maru;
int n;

//Vsetkym poziciam v jednom komponente priradime v poli
//visited hodnotu 2. Do pola values nahadzeme hodnoty
//z tychto pozicii.
void dfs (int v) {
    values.push_back(permutacia [v]);
    visited [v] = 2;
    for (int i = 0; i < n; i++) {
        if (visited [i] == 0 && maru [v] [i]) {
            dfs(i);
        }
    }
}

int main () {
    int x;
    scanf("%d", &n);
    permutacia.resize(n);
    visited.resize(n, 0);
    maru.resize(n, vector <bool> (n));

    //nacitame permutaciu
    for (int i = 0; i < n; i++) {
        scanf("%d", &permutacia [i]);
    }

    //nacitame maticu vymenitelnosti
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &x);
            maru [i] [j] = (x == 1);
        }
    }
    
    //pre kazdu poziciu zistime, ci sme ju uz nahodou
    //nespracovali a ak nie, spracujeme ju
    for (int i = 0; i < n; i++) {
        if (visited [i] == 0) {

            //zistime, co je s nou v komponente
            dfs(i);

            //usporiadame hodnoty
            sort (values.begin(), values.end());
            
            //priradime ich v poradi na prazdne pozicie
            //a danym poziciam nastavime hodnoty v poli
            //visited na 1
            int point = 0;
            for (int j = 0; j < n; j++) {
                if (visited [j] == 2) {
                    visited [j] = 1;
                    permutacia [j] = values [point];
                    point ++;
                }
            }
            values.clear();
        }
    }

    //vypiseme
    printf("%d", permutacia [0]);
    for (int i = 1; i < n; i++) printf(" %d", permutacia [i]);
    printf("\n");
}

Existuje ešte aj riešenie s lineárnou pamäťovou zložitosťou, ktoré sme po vás ale nevyžadovali. Mohli ste zaň dostať jeden bonusový bod. Základnou myšlienkou je vhodne si ukladať informáciu o komponentoch a informáciu o vymeniteľnosti pozícií spracovávať priebežne po riadkoch.


  1. Nakreslite si to!

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