Zadanie

V Číne majú veľa malých chlapcov a dievčat. Chlapcov trochu viac. A ešte viac ryže.

V poslednom čase je ale v ich škôlkach stále viac a viac plačúcich a nešťastných detí. Začali sa totiž učiť matematiku. Konkrétne, zatiaľ sa naučili počítať do veľkých čísel a tiež násobiť a deliť dvomi.

Mohli by ste si myslieť, že majú množstvo domácich úloh, alebo že ich matematika nebaví. Opak je však pravdou. Akonáhle získali túto novú superschopnosť, využívajú ju každý deň. Hlavne pri obede. Skôr než sa pustia do jedenia, každý si spočíta svoje zrnká ryže.1

Keď má každý spočítanú svoju ryžu, začne sa druhá fáza obeda. Porovnávanie. Ak niekto zistí, že má dvakrát viac zrniek ako spoluškôlkar, má právo povyšovať sa a vysmievať sa mu. Potom nasleduje plač, alebo si ublížený chlapec či dievča nájde niekoho, kto má ešte dvakrát menej ryže. Deti niekedy bývajú kruté.

Pani vychovávateľky sú bezradné. Toľko plaču a kreatívnych nadávok, koľko počuli za posledné obdobie ešte nikdy nezažili. Proces výučby sa samozrejme rýchlo zastavil, no nedá sa deti odnaučiť od toho, čo už vedia.

Preto by, ako náhradné riešenie, chceli niektorým deťom zobrať ryžu a dať im tofu. Ryžu treba zobrať deťom tak, aby nemali žiadni dvaja škôlkari \(x\) a \(2x\) zrniek ryže. Pani vychovávateľky si uvedomujú, že tofu nemá nikto rád2, a preto by ho chceli dať čo najmenej deťom. Tiež by ich zaujímalo, koľkými spôsobmi sa dá deťom zobrať najmenší počet ryžových tanierov a rozdať tofu.

Úloha

Na obed je pripravených \(n\) porcií ryže. O každej porcii sa dozviete jedno číslo – počet zrniek ryže. Tieto čísla sú na vstupe usporiadané vzostupne. Niektoré porcie potrebujete odobrať tak, aby nikto nedostal dvakrát viac ryže ako hocikto iný. Inak povedané, aby nezostali žiadne dve porcie, ktoré majú \(x\) a \(2x\) zrniek. Snažíte sa odobrať čo najmenej porcií.

Zistite tiež, koľkými spôsobmi sa dajú porcie odobrať tak, aby boli splnené predošlé požiadavky. Dva spôsoby sú rôzne ak existuje aspoň jedna porcia, ktorú sme v jednom spôsobe nechali a v druhom nie. Keďže týchto spôsobov môže byť veľmi veľa, vypíšte len zvyšok po delení prvočíslom \(1\,000\,000\,009\).

Formát vstupu

Na prvom riadku vstupu je kladné celé číslo \(n\) neprevyšujúce \(1\,000\,000\) udávajúce počet porcií. Na ďalšom riadku nasleduje \(n\) čísel \(r_i\) oddelených medzerami, pričom pre každé z nich platí \(0 < r_i < 10^{18}\). Čísla \(r_i\) sú zoradené od najmenšieho po najväčšie.

Formát výstupu

Vypíšte dve celé čísla oddelené medzerou: najväčší možný počet porcií, ktoré zostanú po odobratí potrebných tanierov a počet spôsobov ich výberov premodulovaný \(1\,000\,000\,009\). Výstup ukončite znakom nového riadku.

Príklad

Input:

8
1 2 2 3 4 5 5 6

Output:

5 4

Žiadne povyšovanie a čo najmenej tofu dosiahneme ak necháme deťom tieto porcie: 1 3 4 5 5, 1 4 5 5 6, 2 2 3 5 5, 2 2 5 5 6


  1. Vďaka tejto zábavke tiež obedujú niekoľko hodín, a tak nemusia ísť poobede spať.

  2. A všetku tú ryžu musí tiež niekto zjesť.

Najprv si povieme, prečo je výhodné rozdeliť čísla zo vstupu na reťaze. Ďalej sa dozviete, ako spočítať celkový výsledok z čiastkových výsledkov pre reťaze a potom ukážeme rôzne spôsoby ako rozdeliť vstup na reťaze a ako vypočítať najlepší výber prvkov a počet týchto výberov pre jednu reťaz.

Stačí sa pozerať na \(60\) čísel z \(1\,000\,000\)

Podľa zadania je potrebné z \(n\) čísel odstrániť čo najmenej tak, aby nezostali žiadne \(2\) čísla \(x, 2x\). Prvé pozorovanie, ktoré urobíme je, že každé číslo \(x\) sa vylučuje s najviac dvoma inými číslami: \(\frac{x}{2}, 2x\). Ďalej sa \(2x\) vylučuje s \(x\) a \(4x\), \(4x\) s \(2x\) a \(8x\) atď.

\(x,2x,4x,...,2^{k}x\) sa navzájom ovplyvňujú. Ostatné čísla, ku ktorým sa nevieme dostať z \(x\) násobením a delením dvomi, môžeme pri riešení \(2^{k}\)-násobkov \(x\) úplne ignorovať.

  • Každé prirodzené číslo vieme jednoznačne zapísať ako \(x = 2^{u} \cdot z\), kde \(z\) je nepárne číslo, ktoré z čísla \(x\) získame tak, že ho delíme \(2\) kým sa dá, teda \(u\)-krát. Pokiaľ majú dve čísla rôzne \(z\), určite sa nebudú ovplyvňovať.

  • Ak máme vo vstupe čísla \(x, 2x, 8x\) ale nie \(4x\), zjavne ani \(8x\) nebude nijak závisieť od toho, či \(x, 2x\) odstránime alebo necháme.

Vstup sa nám teda oplatí porozdeľovať na reťaze čísel, ktoré spolu súvisia. Podľa predošlých dvoch argumentov budú dve čísla v jednej reťazi, ak vieme jedno z nich prerobiť na druhé opakovaným násobením \(2\) a každý medzivýsledok je vo vstupnej postupnosti.

Keďže čísla na vstupe sú najviac \(10^{18} \approx 2^{60}\), reťaze budú mať dĺžku najviac 60 a budú navzájom nezávislé. Ak teda zistíme najlepší výber čísel a počet týchto výberov pre každú reťaz zvlášť, budeme vedieť vypočítať aj celkové výsledky.

Ako spočítať celkové výsledky z čiastkových

Vstup sme si porozdeľovali na reťaze a predpokladajme, že vieme pre každú reťaz zistiť, aký najväčší počet čísel v nej môže zostať1 – označíme \(C(retaz)\). Počet rôznych možností ako poodstraňovať čísla z jednej reťaze si označíme ako \(M(retaz)\).

Keďže každé číslo sa nachádza v práve jednej reťazi, najväčší počet čísel, ktoré vieme zachovať spočítame jednoducho ako súčet \(C(r)\) pre každú reťaz.

Keďže reťaze sa nijak neovplyvňujú, pre každú z nich môžeme zvoliť ľubovoľný spôsob výberu čísel, a vďaka tomu bude celkový výsledok súčin \(M(r)\) pre všetky reťaze.

Ako porozdeľovať čísla do reťazí

Po rozdelení čísel do reťazí už nebude záležať na hodnote čísel, iba na ich poradí v reťazi a na počtoch rovnakých čísel. Reťaz \(3,3,3,6,6,12,24,48,48\) si preto zapamätáme len ako postupnosť počtov čísel s rovnakými mocninami dvojky (podľa hodnoty \(u\) v zápise \(x = 2^{u} \cdot z\)), t.j. ako \(3,2,1,1,2\).

Na vytvorenie reťaze potrebujeme rýchlo zisťovať, či je vo vstupnej postupnosti číslo \(x\), ak áno, koľkokrát. Pri tvorení reťaze si vyberieme začiatočné číslo a pridáveme dvojnásobky. Ak sú také čísla vo vstupnej postupnosti, pridáme ich do reťaze, ak nie sú, ukončíme reťaz a pokračujeme s ďalšou.

Rozdeľovanie do reťazí – Binárne vyhľadávanie

Vstup je utriedená postupnosť a preto v nej vieme binárne vyhľadávať. Ak chceme zisiť koľkokrát sa nachádza \(x\) v postupnosti, stačí binárne vyhľadať najmenšiu pozíciu čísla \(x\) a pozíciu najmenšieho väčšieho čísla. V C++ presne tieto úlohy plnia funkcie . Pokiaľ sa číslo \(x\) nachádza v poli, počet jeho výskytov je jednoducho .2 V najhoršom prípade – ak sú všetky čísla vstupu rôzne – musíme každé z nich binárne vyhľadať, teda časová zložitosť takéhoto delenia na reťaze bude \(O(n \log n)\).

vector<int> patri_retazi(n,-1);
vector<vector<int> > retaze;

for(int i=0; i<n; i++){
  if (patri_retazi[i] != -1) continue;                         // ak uz sme i spracovali, pokracujeme s i+1
  ll cur = v[i];
  retaze.push_back(vector<int>(0));                            // vytvorime novu, zatial prazdnu, retaz
  int terajsia_retaz = int(retaze.size())-1;
  while(1){
    int lb = lower_bound(v.begin(), v.end(), cur) - v.begin();
    if(lb == int(v.size()) || v[lb] != cur) break;             // ak 2-nasobok uz vo vstupe nie je, ukoncime retaz
    int ub = upper_bound(v.begin(), v.end(), cur) - v.begin();
    retaze[terajsia_retaz].push_back(ub-lb);                   
    for(int j=lb; j<ub; j++) patri_retazi[j] = terajsia_retaz; // oznacime cisla pridane do retaze ako spracovane   
    cur *= 2LL;
  } 
}

Rozdeľovanie do reťazí – Fronta / dvaja bežci

Vďaka utriedenému vstupu sa čísla dajú rozdeliť do reťazí aj v lineárnom čase.

Predstavme si, že čísla načítavame postupne tak, ako sú na vstupe a vkladáme ich do fronty – queue. Načítali sme číslo \(x\) a pozrieme sa, čo s ním môžeme urobiť:

  • ak je \(x\) rovnaké ako predošlé číslo, vložíme ho do rovnakej reťaze
  • ak je vo fronte číslo \(\frac{x}{2}\) vložíme \(x\) na koniec reťaze, v ktorej je \(\frac{x}{2}\)
  • ak vo fronte nie je \(\frac{x}{2}\) vytvoríme novú reťaz so začiatkom \(x\)

Vieme rýchlo odpovedať na otázku, či je vo fronte \(\frac{x}{2}\)? Z fronty vieme vyberať prvky iba zo začiatku, teda z nej budeme musieť vyhadzovať všetky prvky menšie ako \(\frac{x}{2}\). Nakoniec buď nájdeme \(\frac{x}{2}\), alebo najmenšie väčšie číslo. Dôležité je uvedomiť si, že týmto spôsobom nikdy nevyhodíme čísla, ktoré budeme v budúcnosti hľadať. Zjavne polovice väčších čísel ako \(x\) sú tiež väčšie ako \(\frac{x}{2}\), teda zostanú vo fronte.

Každé číslo zo vstupnej postupnosti najviac raz vložíme do fronty a najviac raz vyberieme, a tak spravíme len \(O(n)\) operácií. Ak máme čísla načítané v poli, frontu môžeme simulovať pomocou dvoch ukazovateľov (bežcov), ktorí budú ukazovať na začiatok a koniec fronty.

vector<int> patri_retazi(n,0);
int zac = 0, dalsi = 1;
retaze.push_back(vector<int>(1,1));

while(dalsi < n){
  if(v[dalsi] == v[dalsi-1]){         // ak su prvky rovnake, zvysime posledne 
    int ret = patri_retazi[dalsi-1];  // cislo v posledne upravovanej retazi 
    retaze[ ret ].back()++;
    patri_retazi[dalsi] = ret;
  }
  else{   
    while(v[zac]*2 < v[dalsi]) zac++; // posuvame zaciatok - z fronty vyberame male prvky
    if(v[zac]*2 == v[dalsi]){         // ak je na zaciatku prave o polovicu mensi prvok
      int ret = patri_retazi[zac];
      patri_retazi[dalsi] = ret;
      retaze[ret].push_back(1);
    }
    else{                             // ak na zaciatku je uz vacsi, pridame novu retaz
      int ret = int(retaze.size());
      patri_retazi[dalsi] = ret;
      retaze.push_back( vector<int>(1,1) );
    }
  }
  dalsi++;
}

Rozdeľovanie do reťazí – Hashovacia tabuľka

Pole veľkosti \(10^{18}\) by zaberalo niekoľko miliónov terabajtov, ale ak by boli čísla na vstupe malé (\(\approx\) menšie ako \(10\,000\,000\)), na riešenie by nám stačilo pole malej veľkosti (napr. 10 miliónov prvkov pre čísla menšie ako 10 miliónov). Políčku \(pole[x]\) by sme pripočítali \(1\) za každý výskyt \(x\) vo vstupe a na požadovanú otázku – koľko \(x\)-ov je na vstupe by sme vedeli odpovedať v konštantnom čase. Reťaze by sme tak vedeli vytvoriť v čase \(O(n)\).

Pre veľké čísla si presne takéto údaje môžeme ukladať a odpovedať na otáky v konštantnom čase pomocou hash mapy, ktorá si ,,premenuje’’ prvky – zahashuje – aby sa zmestili do poľa, do ktorého potom indexuje. V C++11 ju nájdete pod názvom . Jej réžia si však vyžaduje konštantne viac času a pamäte oproti riešeniu s frontou/2 bežcami.

Výpočet pre jednu reťaz

V tejto časti popíšeme ako pre jednu reťaz spočítať najväčší možný počet zachovaných prvkov a počet výberov ktorými sa to dá dosiahnuť. Budeme sa sústrediť už len na nasledovnú úlohu:

Máme postupnosť čísel – počty prvkov v reťazi. Chceme vybrať niekoľko čísel tak, aby sme nevybrali žiadne dve vedľa seba a aby počet vybratých bol čo najväčší. Chceme zistiť aj počet rôznych výberov.

Výpočet pre jednu reťaz – Neopakujúce sa čísla

3 body sa dali získať aj za vyriešenie jednoduchšej úlohy – pre neopakujúce sa čísla na vstupe. V takejto verzii úlohy nám stačí poznať len dĺžky jednotlivých reťazí – v reprezentácii, ako bola spomenutá na začiatku časti o rozdeľovaní čísel do reťazí, by sme mali reťaze uložené ako postupnosti samých jednotiek.

Výber čísel z reťaze budeme značiť ako postupnosť \(0/1\), kde \(0\) bude znamenať, že sme číslo odstránili a \(1\), že sme ho zachovali.

  • Pokiaľ je dĺžka reťaze nepárna existuje len jedna možnosť ako dosiahnuť najvačší počet zachovaných čísel a zachová sa ich \(\lfloor \frac{l}{2} \rfloor + 1\), kde \(l\) je dĺžka reťaze a \(\lfloor x \rfloor\) je dolná celá časť x. Výber čísel bude vyzerať nasledovne: \(1010\dots0101\).

  • Ak je dĺžka párna, najväčší počet zachovaných je \(\lfloor \frac{l}{2} \rfloor\). Koľko je ale rôznych možností výberov? Pre \(l=4\) to môže byť \(0101\), \(1010\), ale aj \(1001\). Pre ľubovoľnú párnu dĺžku sú 2 možnosti výberov, kedy sú na krajoch \(0/1, 1/0\). Ak sú však na oboch krajoch jednotky, vnútri postupnosti sme museli odstrániť 2 čísla vedľa seba. Takýchto potenciálnych miest je vo vnútri reťaze \(\lfloor \frac{l}{2} \rfloor - 1\), teda počet možností výberov je celkovo pre párne dlhú reťaz \(\lfloor \frac{l}{2} \rfloor + 1\).

Výpočet pre jednu reťaz – Hrubá sila

Ak by boli všetky reťaze krátke, môžeme dovoliť použiť hrubú silu. Skonštruovali by sme všetky výbery, ako niektoré čísla vynechať – všetky podmnožiny reťaze. V každom takomto výbere by stačilo skontrolovať, či sme v ňom nenechali 2 nasledujúce čísla. Počet rôznych výberov by sme jednoducho zväčšovali o \(1\) za každý výber s najlepším výsledkom.

Ako prakticky prezerať všetky možné výbery? Ak si opäť označíme výber prvkov ako reťazec núl a jednotiek, potrebujeme skontrolovať všetky výbery medzi \(00\dots00\) a \(11\dots11\). Tieto binárne reťazce ale môžeme považovať aj za čísla od \(0\) po \(2^l-1\). Stačí nám teda v cykle prejsť cez tieto čísla a pre každé číslo – výber, skontrolovať či v ňom nie sú 2 jednotky za sebou a spočítať súčet čísel, čo zostanú v reťazi.

Ak by sme ohraničili dĺžku reťazí číslom \(l\), časová zložitosť takéhoto riešenia by sa dala odhadnúť ako \(O(n \cdot 2^l)\). Za takéto riešenie ste mohli získať až 6 bodov z praktickej časti.

int najvacsi_pocet = 0;
ll najviac_moznosti = 1LL;
ll MOD = 1000000009LL;

For(r,int(retaze.size())){
  ll moznosti = 0LL;
  int pocet = 0;
  int len = retaze[r].size();
  For(i, (1<<len)){                                // pre vsetky mozne vybery reprezentovane ako cisla
    bool ok = 1;                                   // kontrola, ci nejdu 2 jednotky po sebe
    For(j,len) 
        if( (i & (1<<j)) && (i & (1<<(j+1)))) ok = 0;
    if(!ok) continue;
    
    int poc = 0;                                    // inak aktualizujeme najvacsi pocet cisel a pocet moznosti
    For(j,len) 
      if(i & (1<<j) ) poc += retaze[r][j];          // spocitavame pocet zachovanych cisel v retazi
    if(poc > pocet){ pocet = poc; moznosti = 0LL; }
    if(poc ==pocet) moznosti++;
  }
  najvacsi_pocet += pocet;
  najviac_moznosti = (najviac_moznosti * moznosti) % MOD;
}

printf("%d %lld\n", najvacsi_pocet, najviac_moznosti);

Výpočet pre jednu reťaz – Dynamické programovanie

Na záver si ukážeme, ako spočítať všetko, čo chceme, optimálne – teda v lineárnom čase.

Skúsme výber prvkov z reťaze postupne konštruovať zľava doprava. Na začiatku nech je výber prázdny a postupne do neho budeme pridávať niektoré čísla z reťaze. Pri každom čísle budeme mať na výber dve možnosti: ,,pridať, či nepridať?’’

Začnime prvým prvkom zľava. Ak ho nepridáme, je zjavne len jeden výber s najlepším súčtom – nulovým. Ak ho pridáme, najlepší možný súčet je prvé číslo z reťaze a počet výberov je \(1\).

Poďme pridať ďalšie číslo z reťaze. Ak sme pridali predošlé číslo, druhé číslo pridať nemôžeme. Ak sme predošlé číslo nepridali, môžeme sa rozhodnúť či pridáme alebo nepridáme ďalšie.

Všimnite si, že akonáhle sa rozhodneme jedno číslo nepridať do výberu, zvyšok výberu bude úplne nezávislý od všetkého naľavo. Nemusíme teda výbery konštruovať, stačí nám zapamätať si, aký je doterajší najlepší súčet a koľkými rôznymi spôsobmi sa dá dosiahnuť.

Na základe týchto úvah nájdeme najväčší súčet a počet rôznych výberov postupne pre prvých \(1,2,\dots,i\) prvkov reťaze.

Označme si ako najväčší súčet, ktorý môžeme dosiahnuť výberom z prvých \(i\) prvkov, ak prvok \(i\) nepridáme. bude označovať maximálny možný súčet z prvkov \(0,1,\dots,i\) ak \(i\)-te číslo pridáme.

Podobne označíme počet rôznych výberov z prvkov \(0,1,\dots,i\) s najlepším súčtom ako a opäť podľa toho, či sme \(i\)-te číslo pridali.

Celkový výsledok pre reťaz zistíme ako najväčší súčet čísel z výberu všetkých prvkov, teda
a počet výberov, pri ktorých dosiahneme tento súčet, sa dozvieme z príslušného .

Najlepšie súčty pre prvých \(i\) prvkov vieme určiť z informácií pre prvých \(i-1\) prvkov takto:

  • Ak chceme pridať prvok \(i\), \((i-1)\)-vý sme pridať nemohli. Preto .
  • Ak prvok \(i\) nepridávame, pre výber prvých \(i\) prvkov sa môžeme rozhodnúť či v ňom bude \((i-1)\)-vé číslo z reťaze alebo nie. Vtedy .

Počet výberov prvých \(i\) prvkov s najlepším súčtom vieme tiež zistiť len z informácií pre prvých \(i-1\) prvkov:

  • Keď pridávame prvok \(i\), počet možností výberu zostane rovnaký ako počet výberov prvých \(i-1\) prvkov, keď \((i-1)\)-vý v tomto výbere nebude, teda .
  • Ak \(i\) do výberu prvých \(i\) prvkov nepridáme, môžeme sa rozhodnúť, či je lepší výber prvých \(i-1\) prvkov s alebo bez \((i-1)\)-vého prvku.
    • Ak je jeden výber lepší, počet možností výberov bude rovnaký ako .
    • Ak sú najlepšie výbery s a bez \(i-1\) rovnocenné, teda ak vieme dosiahnuť rovnaký najlepší súčet bez aj s \((i-1)\)-vým prvkom, môžeme použiť všetky tieto výbery a tak výsledný počet rôznych výberov je súčtom počtov výberov .

Pre každý prvok reťaze vypočítame štyri čísla . Každý takýto výpočet je nanajvýš súčtom alebo maximom dvoch čísel, teda sa stíha v konštantnom čase a teda každú reťaz vieme spracovať v čase lineárnom v závislosti od jej dĺžky, teda \(O(l)\). Spracovanie všetkých reťazí dokopy nám potrvá \(O(n)\), lebo každé políčko tabuľky zodpovedá aspoň jednému číslu zo vstupu.

Keďže vo výpočte \(i\)-teho políčka používame len údaje z \((i-1)\)-vého, mierne množstvo pamäte sa dá ušetriť tak, že si nepamätáme celé pole ale len tieto posledné údaje o \((i-1)\) prvých prvkoch.

int najvacsi_pocet = 0;
ll najviac_moznosti = 1LL;
ll MOD = 1000000009LL;

For(r,int(retaze.size())){
  // trikovo pridame este 1 prvok na koniec retaze, aby sme na zaver nemuseli "vypocty dynamiky" pisat 2x
  retaze[r].pb(0);
  int l = int(retaze[r].size());
  vector< vector<int> > S(l,vector<int>(2,0));
  vector< vector<int> > V(l,vector<int>(2,0));
  
  S[0][0] = 0; S[0][1] = retaze[r][0];    // nastavime vysledky pre prvy prvok
  V[0][0] = 1; V[0][1] = 1;
  for(int i=1; i<l; i++){
    S[i][1] = S[i-1][0] + retaze[r][i];   // ak chceme vybrat prvok i, nas osud je predurceny
    V[i][1] = V[i-1][0];

    if(S[i-1][0] == S[i-1][1]){           // ak su vybery s a bez (i-1) rovnocenne
      S[i][0] = S[i-1][0];
      V[i][0] = V[i-1][0]+V[i-1][1];
    }
    else{                                 // ak je jeden z vyberov (i-1) lepsi
      int k = (S[i-1][0] > S[i-1][1] ? 0 : 1);
      S[i][0] = S[i-1][k];
      V[i][0] = V[i-1][k];
    }
  }
  najvacsi_pocet += S[l-1][0];
  najviac_moznosti = (najviac_moznosti * ll(V[l-1][0])) % MOD;
}

printf("%d %lld\n", najvacsi_pocet, najviac_moznosti);

Záver

Rozdelenie vstupu na reťaze sa dá robiť nezávisle od počítania údajov pre jednu reťaz a tak ste si mohli zvoliť rôzne kombinácie algoritmov. Celkovo sa dala úloha vyriešiť spojením prístupu s frontou s dynamickým programovaním v \(O(n)\). Toto je zjavne aj najlepšia asymptotická zložitosť, ktorá sa dá dosiahnuť, keďže už len načítanie vstupu nám potrvá lineárne dlho.


  1. Ako to spočítať si ukážeme neskôr.

  2. Tieto funkcie v C++ vracajú iterátory, ktoré sú adresami prvkov, nie indexami do poľa. Pokiaľ chceme zistiť index x, potrebujeme od iterátora odpočítať adresu začiatku poľa.

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