8. Okná sa vymieňajú vzorové riešenie

2
4 11 2
4 11 3

4
2

Opäť úloha podľa môjho gusta. Dôvod, prečo sa mi páči je ten, že na jej riešenie nie je potrebné dostať správny nápad, ale postupne zlepšovať riešenie v sérii malých krokoch. Nuž a tieto kroky si v tomto vzorovom riešení ukážeme.

Pomalý začiatok

Keď si nevieme poradiť s nejakou úlohou, vždy je dobré začať pomalým riešením, poprípade sa pozrieť na malé príklady a zistiť, ako sa to správa na nich. Začneme teda tak, že si naprogramujeme jednu funkciu, ktorá bude simulovať náš komprimátor – bude zisťovať počet jednotiek v binárnom zápise čísla \(a\), a druhú funkciu, ktorá bude počítať, koľkokrát musíme použiť tento komprimátor na to, aby sme z čísla \(a\) dostali číslo \(1\). Takéto niečo by malo byť veľmi jednoduché na naprogramovanie a nemali by ste s tým mať problém.

Následne spustíme náš program na prvých \(100\) číslach a pozeráme, aké výsledky dostávame. Prekvapivo, sú to všetko veľmi malé čísla, najväčšie, ktoré nájdeme je \(3\). Skúsime to pre prvých milión čísiel a zistíme, že najväčší počet komprimácií, ktorý vieme dosiahnuť je \(4\). To vyzerá nanajvýš podozrivo, skúsme sa teda zamyslieť, prečo sú tieto čísla také malé.

Keď sa pozrieme na formát vstupu, zistíme, že najväčšie číslo, ktoré môžeme dostať je \(10^{18}\) – čo je číslo, ktoré sa pohodlne zmestí do \(64\) bitovej premennej. To ale znamená, že najviac \(64\) bitov môže byť rovných \(1\).¹ Teda po prvej komprimácii ľubovoľného čísla v našom rozmedzí \(l\) až \(h\) dostaneme číslo menšie ako \(64\). A pre takto malé čísla už vieme, že na komprimáciu na \(1\) potrebujeme najviac \(3\) komprimácie. To znamená, že najväčšie \(k\), pre ktoré existuje nenulová odpoveď je \(4\).²

Toto pozorovanie bude veľmi kľúčové pre ďalší postup. Aj bez neho však máme veľmi jednoduché riešenie, ktoré pre každé číslo \(l\) až \(h\) zistí, koľko potrebuje komprimácií aby z neho vzniklo číslo \(1\) a ak sa toto číslo rovná \(k\), zväčší o jedna svoju odpoveď.

Od stredu k riešeniu

Interval \(l\) až \(h\) je pomerne veľký, môže obsahovať veľké množstvo čísiel. Predchádzajúce pozorovanie nám však vraví, že po prvom kroku budú všetky čísla komprimované na niečo menšie ako \(64\). Skúsime to teda riešiť od tohoto zlomového okamihu, po prvej komprimácií, a skúsime spočítať všetky vhodné čísla. Z hodnoty čísla \(k\) vieme, že musíme spraviť ešte \(k-1\) komprimácií. Pozrieme sa teda na prvých \(63\) čísiel a zistíme, ktoré z nich potrebujú ešte \(k-1\) komprimácií na to, aby sme dostali \(1\). Do nášho riešenia teda chceme zarátať všetky čísla, ktoré sa po prvej komprimácii zmenia na niektoré z týchto čísiel. Dokopy totiž budú potrebovať práve \(k\) komprimácií.

Nuž a čo vieme povedať o čísle, ktoré sa skomprimuje na číslo \(a\)? Že v jeho binárnom zápise sa nachádza práve \(a\) jednotiek. Uvedomme si teraz, že ak by sme vedeli odpovedať na nasledovnú otázku, máme vyhrané: ``Koľko je takých čísiel medzi \(l\) a \(h\), že majú práve \(a\) jednotiek v binárnom zápise?’’

Náš program by teraz vyzeral nasledovne. Predrátali by sme si riešenie pre prvých \(63\) čísiel. Následne by sme cez ne prešli a vždy, keď by nejaké číslo \(a\) potrebovalo \(k-1\) komprimácií, k výsledku by sme pripočítali počet čísiel medzi \(l\) a \(h\), ktoré majú \(a\) jednotiek v binárnom zápise. Každé také \(a\) nám dá vlastnú nezávislú množinu čísiel, všetky dokopy dávajú odpoveď. Ostáva už len zistiť, ako odpovedať na našu otázku.

Jedno ohraničenie namiesto dvoch

Tento trik by mal byť pomerne známy a dá sa veľmi pekne využiť aj v našej úlohe. Otázka, ktorú sa pýtame má dve ohraničenia \(l\) a \(h\). Veľmi ľahko to však vieme zmeniť len na to horné. Presnejšie, budeme chcieť vedieť, koľko je takých čísiel menších alebo rovných ako \(h\), že potrebujú \(k\) komprimácií. Toto nám samozrejme dá nejaké čísla navyše. To sú ale tie čísla, ktoré potrebujú \(k\) komprimácií a sú menšie alebo rovné ako \(l-1\). Ak teda máme funkciu, ktorá odpovedá na našu otázku pre horné ohraničenie, na interval to vieme zmeniť odčítaním riešení pre \(h\) a \(l-1\).

Takéto zjednodušenie nám môže výrazne pomôcť pri programovaní aj rozmýšľaní, lebo nám stačí dodržiavať len jednu podmienku. V tomto prípade to bude značná pomoc.

Posledný kúsok

Postupne sme si teda našu úlohu značne zmenili a teraz sa pýtame, koľko existuje čísiel menších ako \(h\), ktoré majú práve \(a\) jednotiek v binárnom zápise. Poďme si tieto čísla postupne vytvárať, jednu cifru za druhou. A, samozrejme, myslíme binárne cifry.

Predstavme si, že číslo \(h\) máme zapísané po binárnych cifrách v poli \(H[]\), ktoré má \(n\) políčok a na \(0\)-tej pozícii je najmenej významná cifra. Budeme postupne vytvárať všetky čísla, ktoré sú nanajvýš takto veľké a obsahujú \(a\) cifier \(1\). Všetky tieto čísla naviac budú mať \(n\) cifier aj keby mali začínať prebytočnými nulami.

Zjavne \(H[n-1]=1\), lebo najdôležitejšia cifra musí byť \(1\). A ako môže vyzerať naše vytvárané číslo? To bude mať na pozícii \(n-1\) buď cifru \(1\) alebo \(0\). Ak tam dáme 0, tak bez ohľadu na to ako bude číslo pokračovať, naše hľadané číslo bude menšie ako \(h\). Takže chceme splniť už len to, aby malo aj správny počet jednotiek. Koľkými spôsobmi vieme uložiť \(a\) jednotiek na \(n-1\) pozícii? To je jednoduché kombinačné číslo \(n-1\) nad \(a\). Všetky tieto čísla teda môžeme pričítať do výsledku. V prípade, že na pozíciu \(n-1\) dáme \(1\), musíme pokračovať v skúšaní ďalších cifier. Minuli sme si jednu jednotku, takže ich chceme rozdať už len \(a-1\).

Pokračujeme teda v skúšaní možností pre pozíciu \(n-2\), \(n-3\), … Pokiaľ narazíme na cifru \(1\) vyriešime to ako v predošlom prípade, ak nájdeme v \(H\) cifru \(0\), tak naše hľadané čísla (tie ktoré sme ešte nezapočítali) musia mať na rovnakej pozícii tiež nulu, inak by boli väčšie ako \(h\).

Takto pokračujeme až kým neprídeme na začiatok poľa \(H\). No a medzičasom sme zrátali všetky možné čísla, ktoré môžu slúžiť ako výsledok.

Rekapitulácia

Ako teda vyzerá celé riešenie pokope? Na začiatku načítame vstup a spravíme nejaké predrátania. Presnejšie, zrátame odpoveď pre prvých \(63\) čísiel a predpočítame si Pascalov trojuholník do hĺbky \(63\). Ten nám bude slúžiť na to, aby sme vedeli rýchlo povedať hodnotu jednotlivých kombinačných čísiel. Stačí nám to počítať do dvojrozmerného poľa postupne od malých hodnôt k väčším, klasickým prístupom – sčítame dve susedné z predošlého riadku.

Pokračujeme tým, že vyrátame výsledok pre horné ohraničenie \(h\). Toto číslo si zmeníme na binárne. Potom prechádzame prvých \(63\) čísiel a vždy, keď vidíme, že nejaké číslo \(a\) má riešenie \(k-1\) komprimácií, zistíme počet čísiel menších ako \(h\), ktoré obsahujú \(a\) jednotiek v binárnom zápise. Toto zistíme vyššie popísaným dynamickým programovaním cez jednotlivé cifry.

Od výsledku odrátame výsledok pre horné ohraničenie \(l-1\) a máme výsledok pôvodnej úlohy. Zostáva už len odhadnúť časovú a pamäťovú zložitosť. Nebudeme sa tváriť, že \(63\) je konštanta, lebo to vzniklo ako logaritmus čísla \(h\) a tak to aj budeme označovať. Pamätať si musíme binárny zápis čísla \(h\) a Pascalov trojuholník, ktorý je kvadratický, takže pamäťová zložitosť bude \(O(\log^2 h)\). A časová zložitosť bude úplne rovnaká, keďže pre najviac \(\log h\) čísiel pustíme dynamiku so zložitosťou \(O(\log h)\).

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)
typedef long long ll;

int A[74];
ll F[63][63];

void predrataj() {
    // počet jednotiek v bin. zápise
    A[1]=0;
    for(int i=2; i<70; i++) {
        int x=i,p=0;
        For(j,10) if(x&(1<<j)) p++;
        A[i]=1+A[p];
    }
    // kombinačné čísla
    F[0][0]=1;
    for(int i=1; i<63; i++) {
        F[i][0]=1;
        for(int j=1; j<=i; j++) F[i][j]=F[i-1][j]+F[i-1][j-1];
    }
}

// koľko je čísel menších ako 'h', ktoré majú v bin. zápise 'jed' jednotiek
ll pocet(ll h, int jed) {
    vector<int> P;
    ll res=0;
    if(jed==1) res=-1;
    ll x=h;
    while(x>0) {P.push_back(x%2); x/=2;}
    reverse(P.begin(),P.end());
    int bity=P.size();
    For(i,P.size()) {
        if(jed<0) break;
        if(P[i]==0) continue;
        res+=F[bity-i-1][jed];
        jed--;
    }
    if(jed==0) res++;
    return res;
}

// koľko je čísel menších ako 'h', ktoré sa skomprimujú na 'kolko' krokov 
ll zrataj(ll h, int kolko) {
    if(h==0) return 0;
    if(kolko==0) return 1;
    ll res=0;
    for(int i=1; i<63; i++) {
        if(A[i]!=kolko-1) continue;
        res+=pocet(h,i);
    }
    return res;
}

int main() {
    predrataj();
    int t;
    scanf("%d",&t);
    while(t--) {
        ll l,r;
        int x;
        cin >> l >> r >> x;
        cout << zrataj(r,x)-zrataj(l-1,x) << endl;
    }
}