4. Kruhová knižnica vzorové riešenie

5 5
0 1 2 3 4

6

|X....|
|.X...|
|..X..|
|...X.|
|....X|

3 10
0 0 8

2

|X.........|
|X.........|
|........X.|

2 5
2 3

1

|..X..|
|...X.|

Pomalé riešenie

Predstavme si, že by sme vedeli, do ktorého stĺpca (na ktorú pozíciu) chceme presunúť všetky červené knihy. Označme túto pozíciu \(c\). Vieme nejako vypočítať vzdialenosť, o ktorú treba posunúť knihu, ktorá sa práve nachádza na pozícii \(p\)?

Mohli by sme ju presunúť bez využitia cyklickosti políc. Takto sa kniha posunie o vzdialenosť \(|p-c|\), kde \(|x|\) značí absolútnu hodnotu čísla \(x\) (teda číslo po odobratí znamienka). Ak by sme ju chceli posunúť opačným smerom, teda cez hranicu medzi pozíciami \(0\) a \(s-1\), táto vzdialenosť by bola doplnkom vyššie uvedenej vzdialenosti do celého kruhu (čiže do \(s\)). V tomto prípade teda dostávame vzdialenosť \(s - |p-c|\). Z týchto dvoch vzdialeností vieme vybrať tú menšiu a toto urobiť a posčítať pre všetky police.

Keďže cieľovú pozíciu nepoznáme, musíme vyskúšať všetkých \(s\) možných. Pre každú z nich prejdeme všetky knihy a vyberieme najlepšiu pozíciu. Máme tak riešenie s časovou zložitosťou \(O(ns)\), ktoré zvládne vyriešiť prvé 2 sady.

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long int ll;
using namespace std;

ll bruteForce(int n, int columns, vector<int> positions){
    ll best = 1LL*n*n;
    for (int c=0; c<columns; c++){
        ll current = 0;
        for (int pos: positions)
            current += min(abs(c-pos), columns - abs(c-pos));
        best = min(best, current);
    }
    return best;
}

int main() {
    int n, columns;
    cin >> n >> columns;
    vector<int> positions(n);
    ll best = n*n;
    for (int i=0; i<n; i++) {
        cin >> positions[i];
    }
    cout << bruteForce(n, columns, positions) << '\n';
    return 0;
}

Efektívnejšie riešenie jednoduchšej úlohy

Pozrime sa teraz na jednoduchšiu úlohu, v ktorej police nie sú cyklické, ale majú ľavý a pravý koniec. V takomto prípade je odpoveď jednoduchá – je ňou medián čísel na vstupe. Medián postupnosti je jej stredná hodnota, teda číslo, ktoré po usporiadaní postupnosti skončí v strede. Ak je čísel nepárne veľa, je táto hodnota jednoznačne určená. Ak je čísel párne veľa, medián je definovaný ako priemer dvoch prostredných, ale ako riešenie úlohy je možné vziať ľubovoľnú hodnotu medzi dvomi prostrednými (alebo rovno jednu z nich) a bude to rovnako dobré optimálne riešenie.

Prečo je riešením vždy medián? Začnime s tým, že cieľovú pozíciu, kam chceme knihy premiestniť, dáme úplne naľavo, takže každá kniha bude musieť byť presunutá o určitú vzdialenosť doľava. Keď teraz začneme našu pozíciu posúvať doprava, knihám, ktoré sú od nej napravo, sa potrebná vzdialenosť bude znižovať, zatiaľ čo knihám, ktoré sú od nej naľavo, sa bude znižovať.

Ak je napravo od cieľovej pozície \(j\) kníh a naľavo \(i\), posunom o 1 doprava sa celkový súčet vzdialeností zmenší o \(j\) a zvýši o \(i\), pričom nejaké knihy sa môžu začať nachádzať na opačnej strane od tejto pozície.

Na začiatku sú všetky knihy napravo a približujú sa, na konci sú všetky naľavo a vzďaľujú sa. Ideálnym riešením je stav, kedy je naľavo aj napravo rovnako veľa kníh (vtedy zvyšovanie začne predbiehať znižovanie), čo je práve vtedy, keď sme v mediáne. (Pre prostredný prvok platí, že naľavo aj napravo od neho je rovnako veľa prvkov.)

Vzorové riešenie

Túto myšlienku vieme zovšeobecniť na riešenie našej úlohy. Začnime s cieľovou pozíciou \(0\) a poďme ju posúvať (po kruhu) doprava. Počítajme si pritom, koľko pozícií sa približuje a koľko sa vzďaľuje. Keď poznáme aktuálny celkový súčet vzdialeností a pohneme cieľovou pozíciou, na základe týchto hodnôt vieme celkový súčet aktualizovať.

Ktoré knihy sa k nej približujú a ktoré sa vzďaľujú?

Ak je cieľová pozícia \(0\), približujú sa tie, ktoré sú na pozícii najviac \(s/2\) (najkratšia cesta pre ne vedie priamo k menším pozíciám) a vzďaľujú sa tie, ktoré sú na pozícii väčšej ako \(s/2\) (pre ne je optimálne ísť k \(0\) doprava cez vyššie pozície).

Kedy sa mení, či sa kniha približuje alebo vzďaľuje

Keď s cieľovou pozíciou prídeme na pozíciu nejakej knihy, táto sa doteraz približovala a odteraz sa začne vzďaľovať. Pri našich kruhových pozíciách môže nastať ešte jeden typ situácie, a to ten, že sa kniha prestane vzďaľovať a začne približovať. Deje sa to vtedy, keď sme na kruhu presne oproti nej. Cieľová pozícia sa od nej vzdialila natoľko, že už je pre knihu lepšie k nej ísť opačným smerom a v tomto smere sa približuje.

Keď sa však pustíme do implementácie, uvedomíme si, že to nie je také jednoduché. Pre párne \(s\) sa kniha v istom momente prestane vzďaľovať a hneď sa začne približovať, napríklad pre \(s=100\) a knihu na pozícii \(10\) sa toto stane, keď cieľová pozícia je \(60\).

Avšak pre nepárne \(s\) sa to stane na neceločíselnej pozícii, napríklad pre \(s=101\) a knihu na pozícii \(10\) sa to stane, keď cieľová pozícia je \(60.5\). My však pracujeme iba s celočíselnými pozíciami. Pre knihu ostáva vzdialenosť rovnaká pre cieľovú pozíciu \(60\) aj \(61\).

Elegantný spôsob riešenia tohto problému je taký, že si nebudeme pamätať len počet kníh, ktoré sa približujú a vzďaľujú, ale aj počet takých, ktoré svoju vzdialenosť nemenia. V tomto stave vie byť každá kniha len po dobu presunu cieľovej pozície o \(1\) (a po dobu \(0\) pri párnom \(s\) – nechceme mať zvlášť implementáciu pre párne a pre nepárne \(s\)).

Dajme to všetko dokopy

Vzorové riešenie teda bude vyzerať nasledovne: najskôr si vypočítame súčet vzdialeností, keby sme všetky knihy chceli presunúť na pozíciu \(0\). Tiež si napočítame počet približujúcich sa a vzďaľujúcich sa kníh (a tých, čo svoju vzdialenosť pri posune z \(0\) na \(1\) nezmenia, to sú tie na pozícii \(\frac{s+1}{2}\), ak to je celé číslo).

Cieľovú pozíciu posúvame doprava a udržiavame si aktuálny súčet vzdialeností a najlepší doteraz nájdený. Aby sme nemuseli prechádzať \(10^9\) pozícii v 4. sade, stačí si uvedomiť, že zaujímavé pozície sú len tie, kde sa niečo mení. Pre každú knihu je to jej pozícia a jedna alebo dve pozície presne naproti nej (podľa parity \(s\)). Tieto udalosti si vieme predpočítať dopredu, usporiadať podľa súradnice a postupne ich všetky spracovať.

Časová zložitosť riešenia je \(O(n \log n)\), pretože výpočet hodnôt pred začatím posúvania cieľovej pozície spravíme v \(O(n)\), potom utriedime \(3n\) udalostí v \(O(n \log n)\) a následne každú udalosť spracujeme v konštantnom čase. Každá udalosť je totiž iba zmena stavu jednej knihy (približuje sa/vzďaľuje sa/nemení sa). Pamäťová zložitosť je \(O(n)\).

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long int ll;
using namespace std;

#define ONE 1
#define OPPOSITE1 2
#define OPPOSITE2 3

ll solve(int n, int columns, vector<int> positions){
    ll best = 1LL*n*columns, goingLeft = 0, goingRight = 0, stagnant = 0;
    vector<pair<int, int>> events;
    for (int i=0; i<n; i++) {
        if (columns % 2 == 1 && positions[i] == columns / 2)
            stagnant++;
        else if (positions[i] <= (columns-1) / 2)
            goingLeft++;
        else
            goingRight++;
        events.push_back({positions[i], ONE});
        events.push_back({(positions[i] + columns/2) % columns, OPPOSITE1});
        events.push_back({(positions[i] + (columns+1)/2) % columns, OPPOSITE2});
    }
    
    int lastpos = 0;
    ll current = 0;
    for (int pos: positions)
        current += min(pos, columns - pos);
    sort(events.begin(), events.end());
    
    for (pair<int, int> ev: events){
        int curpos = ev.first;
        current = current + goingRight * (curpos - lastpos) - goingLeft * (curpos - lastpos);
        best = min(best, current);
        if (ev.second == ONE){
            goingLeft--;
            goingRight++;
        }
        else if (ev.second == OPPOSITE1){
            goingRight--;
            stagnant++;
        }
        else if (ev.second == OPPOSITE2){
            stagnant--;
            goingLeft++;
        }
        lastpos = curpos;
    }
    return best;
}

int main() {
    int n, columns;
    cin >> n >> columns;
    vector<int> positions(n);
    for (int i=0; i<n; i++) {
        cin >> positions[i];
    }
    cout << solve(n, columns, positions) << '\n';
    return 0;
}