Zadanie
V základnej škole Kráľa Svätopluka Prvého majú obrovskú knižnicu. Je to veľká kruhová miestnosť, v ktorej je pozdĺž stien nad sebou umiestnených \(n\) dlhých políc. Každá polica je kruhová a ide kolom dokola celej miestnosti. (Samozrejme, sú tam aj dvere, takže nejde úplne dokola, ale tie pre túto úlohu nie sú zaujímavé.) Každú policu si teda môžeme predstaviť ako kružnicu.
Na každú policu sa vojde \(s\) kníh, pre jednoduchosť majú všetky rovnakú šírku. Na každej z nich je zároveň práve jedna (špeciálna) červená kniha. Medzi inými je tam aj Červená algebra, no sú tam aj knihy, ktoré sú červené len preto, že ich obaly nespolušní žiaci zafarbili voskovkami.
Úloha
Knihovníkovi sa nepáči, ako sú červené knihy na náhodných miestach a nepríjemne to bije do očí. Bol by rád, keby sa všetky červené knihy nachádzali nad sebou v jednom stĺpci. Zároveň by chcel, aby sa knihy presunuli o čo najmenšiu celkovú vzdialenosť.
Vzdialenosť meriame po polici popri stene (teda nie krížom cez miestnosť). Knihy nie je možné meniť medzi policami (každá kniha musí ostať vo svojeje polici). Celkovú vzdialenosť dostaneme tak, že sčítame vzdialenosť, o ktorú sa posunula kniha na každej polici. Knihovník si môže vybrať, ktorým smerom chce knihu posúvať (doľava alebo doprava).
Pozície, na ktorých sú knihy, si môžeme očíslovať od \(0\) do \(s-1\), pričom susedné pozície sú vždy \(i\) a \(i+1\), ale aj \(0\) a \(s-1\) (police sú kruhové). Ak napríklad máme policu s dĺžkou na \(s=16\) kníh a chceme premiestniť červenú knihu z pozície \(4\) na pozíciu \(13\), môžeme ju posunúť v smere rastu čísel (doprava) o \(9\) pozícií (\(13-4=9\)). Lepšie je však posunúť ju opačným smerom, takto prekoná vzdialenosť iba \(7\) pozícií (vzdialenosť \(4\) na pozíciu \(0\) a \(16-13=3\) na pozíciu \(13\)).
Pomôžte knihovníkovi nájsť optimálny spôsob premiestnenia kníh.
Formát vstupu
Na prvom riadku dostanete čísla \(n\) a \(s\) – počet políc v knižnici a veľkosť jednej police.
Na druhom riadku sa nachádza \(n\) celých čísel z rozsahu od \(0\) do \(s-1\) – pozície červenej knihy v jednotlivých policiach.
Formát výstupu
Vypíšte jedno číslo – najmenšiu celkovú vzdialenosť, o ktorú je potrebné červené knihy presunúť. Nezabudnite na znak konca riadka.
Hodnotenie
Sú štyri sady vstupov. Platia v nich nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(8\) | \(1000\) | \(100\,000\) | \(100\,000\) |
\(1 \leq s \leq\) | \(16\) | \(2000\) | \(100\,000\) | \(10^{9}\) |
Príklad
Input:
5 5
0 1 2 3 4
Output:
6
Knižnica má \(5\) políc, každá má veľkosť \(5\). Rozmiestnenie kníh vyzerá takto (X je červená kniha):
|X....|
|.X...|
|..X..|
|...X.|
|....X|
Police sú kruhové, teda pravý okraj je napojený na ľavý. Jedno možné riešenie je presunúť všetky knihy do stĺpca (na pozície) \(2\), v jednotlivých riadkoch teda vykonáme presuny o \(2\), \(1\), \(0\), \(1\) a \(2\) pozície, dokopy je to \(6\). V tomto prípade sme kruhovosť nevyužili, ale rovnako dobre ju využiť vieme a na \(6\) krokov presunúť všetky knihy do stĺpca \(0\) či ktoréhokoľvek iného.
Input:
3 10
0 0 8
Output:
2
Knihu v tretej polici posunieme o dve pozície vpravo, čím sa dostane z pozície \(8\) cez pozíciu \(9\) na pozíciu \(0\).
|X.........|
|X.........|
|........X.|
Input:
2 5
2 3
Output:
1
Knihy sú v susedných stĺpcoch, stačí jednu presunúť k druhej.
|..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;
(int n, int columns, vector<int> positions){
ll bruteForce= 1LL*n*n;
ll best for (int c=0; c<columns; c++){
= 0;
ll current for (int pos: positions)
+= min(abs(c-pos), columns - abs(c-pos));
current = min(best, current);
best }
return best;
}
int main() {
int n, columns;
>> n >> columns;
cin <int> positions(n);
vector= n*n;
ll best for (int i=0; i<n; i++) {
>> positions[i];
cin }
<< bruteForce(n, columns, positions) << '\n';
cout 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
(int n, int columns, vector<int> positions){
ll solve= 1LL*n*columns, goingLeft = 0, goingRight = 0, stagnant = 0;
ll best <pair<int, int>> events;
vectorfor (int i=0; i<n; i++) {
if (columns % 2 == 1 && positions[i] == columns / 2)
++;
stagnantelse if (positions[i] <= (columns-1) / 2)
++;
goingLeftelse
++;
goingRight.push_back({positions[i], ONE});
events.push_back({(positions[i] + columns/2) % columns, OPPOSITE1});
events.push_back({(positions[i] + (columns+1)/2) % columns, OPPOSITE2});
events}
int lastpos = 0;
= 0;
ll current for (int pos: positions)
+= min(pos, columns - pos);
current (events.begin(), events.end());
sort
for (pair<int, int> ev: events){
int curpos = ev.first;
= current + goingRight * (curpos - lastpos) - goingLeft * (curpos - lastpos);
current = min(best, current);
best if (ev.second == ONE){
--;
goingLeft++;
goingRight}
else if (ev.second == OPPOSITE1){
--;
goingRight++;
stagnant}
else if (ev.second == OPPOSITE2){
--;
stagnant++;
goingLeft}
= curpos;
lastpos }
return best;
}
int main() {
int n, columns;
>> n >> columns;
cin <int> positions(n);
vectorfor (int i=0; i<n; i++) {
>> positions[i];
cin }
<< solve(n, columns, positions) << '\n';
cout return 0;
}
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ť.