7. Nádlab vzorové riešenie

+-------+
| 0247g |
|   11% |
+-------+

1
3 1000
10g 2%
20g 1%
30g 1%

1 %
2 g
3 g

1
3 1010
9g 1%
20g 1%
99g 10%

3 %
1 %
2 g

1
3 1010
9g 1%
20g 1%
100g 10%

1 %
2 g
3 g

1
3 10
10g 1%
10g 1%
10g 1%

3 g
1 g
2 g

Načítavanie

Prvý krok nutný na vyriešenie úlohy je načítanie vstupu. Keďže je to 7. úloha, aj trošku neštandardný formát vstupu by nám nemal robiť problém. Najťažšie je načítať parametre kartičiek – chceme načítať dve čísla na jednom riadku, ale odignorovať posledný znak.

V Pythone vieme tento riadok načítať napríklad nasledovne:

gram, perc = input().split()
gram, perc = int(gram[:-1]), int(perc[:-1])
# alebo kompaktnejšie
gram, perc = map(lambda s: int(s[:-1]), input().split())

V C++ zase takto:

int gram, perc;
// pomocou scanf
scanf("%dg %d%% ", &gram, &perc);
// alebo, keďže `cin`:
// - číselné typy načítava pokým nenarazí na nečíselný znak
// - ignoruje vedúce whitespace
// stačí načítať do čísla a následne načítať koncový znak do typu `char`
char koncovy;
cin >> gram >> koncovy >> perc >> koncovy;

Aby sa nám uľahčil život, ďalej vo vzorovom riešení, pod hodnotou ‘x%’-kartičky myslíme zlomok granadíru ktorý ešte ostane po použití tejto kartičky, teda \(1-x/100\).

Bruteforce

Najprv si uvedomme, že ak vo výsledku máme dve po sebe idúce kartičky použité rovnakým spôsobom (teda obe g alebo obe %), nezáleží na ich poradí.

Ďalej si uvedomme, že sa nám nikdy neoplatí použiť %-kartičku po g-kartičke. Bez ujmy na všeobecnosti nech ide o posledné dve kartičky a nech množstvo granadíru zostávajúceho po použití všetkých zvyšných kartičiek je \(R\). Potom výsledok (koľko granadíru zostane) po použití kartičiek v poradí g% bude \((R - m) \cdot k = R \cdot k - m \cdot k\) zatiaľčo v poradí %g bude \(R \cdot k - m\), kde \(0 \leq b \leq 1\). Vidíme teda, že použitím kartičiek v poradí g% iba zbytočne odčítavame menej. Výsledné kartičky teda obsahujú najprv postupnosť %-kariet a potom už iba g-kariet.

Spojením týchto dvoch uvedomení zistíme, že našou úlohou je iba pre každú kartu rozhodnúť o jej type, čo už potom jednoznačne určuje výsledok. Naskytá sa nám teda priamočiare riešenie vyskúšať všetkých \(2^N\) možností, každú vyhodnotiť a vypísať najmenšiu.

Najťažšou časťou takéhoto programu je iterovanie cez všetky kombinácie. To sa štandardne robí prostredníctvom iterovania cez čísla od 0 po \(2^N-1\). Binárny zápis každého tohoto čísla reprezentuje jednu podmnožinu \(N\)-prvkovej množiny.

for binarna_mnozina in range(1 << N):
    mnozina = set(i for i in range(N) if binarna_mnozina & (1 << i))

Pamäťová zložitosť je \(O(N)\) a časová zložitosť je \(O(N\times 2^N)\). Efektívnou implementáciou tohoto prístupu sa dali prejsť až dve sady.

Stredová stretávka

Pri riešení úloh vieme použiť obmedzenia vstupov ako pomôcku na nájdenie riešenia. V tomto prípade sme si mohli všimnúť, že \(N\) je podozrivo malé, a teda by sa úloha mohla dať riešiť Meet-In-The-Middle prístupom.

Princíp MITM riešení je využiť symetriu problému a rozdeliť ho na dve časti, ktoré sa dajú riešiť nezávisle. Snažíme sa teda nájsť také rozdelenie, aby každá časť bola dostatočne malá na to, aby sme ju vedeli vyriešiť nejakým iným prístupom (napríklad bruteforce) a výsledky z oboch častí dakázali spojiť do výsledného riešenia.

Ako by to vyzeralo? Rozdelíme si množinu kartičiek na dve rovnako veľké disjunktné časti. Pre každú z nich zbehneme bruteforce a zapamätáme si všetky podvýsledky – podvýsledok je optimálne riešenie pre zvolené určenie typov pre danú polovicu kartičiek. Pre každú časť ich bude \(2^{N/2}\).

My už vieme, že určením typov kartičiek je jednoznačne určený výsledok čo nimi vieme dosiahnuť a efekt ich uplatnenia vieme zjednodušene reprezentovať ako dve čísla – súčet všetkých g-kartičiek a súčin všetkých %-kartičiek, teda \((M, K)\).

Skombinovanie podvýsledkov z týchto dvoch podmnožín je potom jednoduché. Ak chceme skombinovať podvýsledok \((M_{1,i}, K_{1,i})\) s podvýsledkom \((M_{2,j}, K_{2,j})\), kombinácia bude \((M_{1,i} + M_{2,j}, K_{1,i} \cdot K_{2,j})\), čo po konzumácii spôsobí zostatok granadíru \((H \cdot K_{1,i} \cdot K_{2,j}) - (M_{1,i} + M_{2,j})\).

Nás by teraz zaujímalo, aký je najlepší možný výsledok. To zistíme tak, že pre každý podvýsledok prvej časti nájdeme preňho najlepší podvýsledok v druhej časti – teda taký, ktorý minimalizuje daný výraz.

Naivným skúšaním všetkých možností by sme znova získali bruteforce (\(O(2^{N/2}\times 2^{N/2})\)). Naším cieľom je pre fixné \((M_{1,i}, K_{1,i})\) minimalizovať \((H \cdot K_{1,i} \cdot K_{2,j}) - (M_{1,i} + M_{2,j})\) cez všetky \((M_{2,j}, K_{2,j})\). Všimnime si, že to je to isté ako minimalizovať \(H_i \cdot K_{2,j} - M_{2,j}\), pre \(H_i := H \cdot K_{1,i}\), keďže \(M_{1,i}\) a \(K_{1,i}\) sú v tomto prípade konštanty. Problém je, že \(H_i\) je konštanta iba pre jedno konkrétne \(K_{1,i}\), pričom rôznych \(K_{1,i}\) je až \(2^{N/2}\).

Konvexný obal

Sťažme si úlohu. Ak by sme vedeli nájsť optimálne \((M_{2,j}, K_{2,j})\) pre každé reálne \(H'\), tak by sme ho predsa vedeli nájsť aj pre ľubovoľné konkrétne \(H_i\). Z \(H_i\) sa teda stáva reálna premenná \(x\) a \(x \cdot K_{2,j} - M_{2,j}\) nám určuje lineárnu funkciu – priamku. Každé jedno \((M_{2,j}, K_{2,j})\) určuje jednu priamku a nás pre každé \(x\) zaujíma najnižší bod ležiaci na niektorej z týchto priamok. Inak povedané, hľadáme konvexný obal týchto priamok.

Hľadanie konvexného obalu priamok je podobné hľadaniu konvexného obalu bodov. Priamky si utriedime podľa ich smernice a potom ich prechádzame od najväčšej po najmenšiu (teda budeme tvoriť KO zľava doprava), pričom si udržiavame doteraz nájdený KO. Každú priamku sa pokúsime pridať do KO. Môžu nastať dve situácie – buď nová priamka nepatrí do KO alebo patrí.

V prípade, že nová priamka \(f_{\mathrm{nová}}\) patrí do KO tak existuje nejaký najľavejší bod, ktorý patrí aj tejto priamke aj KO – teda to bude priesečník \(f_{\mathrm{nová}}\) a niektorej doterajšej priamky \(f_{\mathrm{hľadaná}}\) z KO. Otestujme, či posledná priamka KO \(f_{\mathrm{posledná}}\) je \(f_{\mathrm{hľadaná}}\). Ak je priesečník priamok \(f_{\mathrm{nová}}\) a \(f_{\mathrm{posledná}}\) ľavší než priesečník priamok \(f_{\mathrm{posledná}}\) a \(f_{\mathrm{predposledná}}\), tak \(f_{\mathrm{posledná}}\) nie je \(f_{\mathrm{hľadaná}}\) a dokonca \(f_{\mathrm{posledná}}\) nie je ani súčasťou KO. V takom prípade ju odstránime a pokračujeme v hľadaní najľavejšieho bodu.

Inak povedané: Tým, že sa na priamky pozeráme v poradí s klesajúcou smernicou platí, že najnovšia priamka je vždy lepšia ako nejaký (potenciálne nulový) počet priamok na konci KO. Teda porovnávame novú priamku s poslednou priamkou KO a odstraňujeme túto poslednú priamku pokým je horšia ako nová. Ošetrenie rovnobežných priamok ponechávame na čitateľa.

Časová zložitosť je \(O(N\log(N))\) a pamäťová zložitosť je \(O(N)\), kde \(N\) je počet priamok. Viac si o konvexnom obale môžete prečítať v kuchárke.

Dôsledok

S nájdeným konvexným obalom potom pre ľubovoľné \(H_i\) vieme nájsť najlepšie \((M_{2,j}, M_{2,j})\) binárnym vyhľadávaním. V prípade, že sa na jednotlivé \(H_i\) budeme pýtať v utriedenom poradí ani nemusíme binárne vyhľadávať, ale len prechádzať postupne priamky KO. Tento prístup sa volá Convex Hull Optimization/Trick.

Pamäťová zložitosť je \(O(2^{N/2})\) a časová zložitosť je \(O(2^{N/2}\times\log(2^{N/2})) = O(N\times 2^{N/2})\) (logaritmus pochádza z triedenia v hľadaní KO a triedenia \(H_i\) alebo binárneho vyhľadávania). Oproti bruteforce teda úspešne zvládame približne dvakrát väčšie vstupy. Pre aktuálne obmedzenia toto však nie je dostatočne rýchle riešenie. Na iných vstupoch (ktoré by mali napríklad väčšie hodnoty gramov) by toto bol dobrý prístup. Tento prístup zvláda prejsť až tri sady, ale v hodnotení popisov vie takéto riešenie získať plný počet.

Vzorové riešenie

Čo ďalšie by sme si mohli všimnúť zo zadania? Gramáže kartičiek sú nanajvýš \(10^4\) a spolu s malým \(N\) teda aj súčet gramáží bude malé číslo.

Ako sme si už povedali, pre zvolené určenie typov kartičiek je výsledok závislý iba od súčinu %-kartičiek (\(=k\)) a súčtu g-kartičiek (\(=m\)). Preto ak by sme mali pevne určený nejaký súčin \(k\), našou snahou je maximalizovať súčet \(m\). Naopak, ak by sme mali pevne určený nejaký súčet \(m\), našou snahou je dosiahnuť minimálny súčin \(k\).

A my vieme, že rôznych súčtov \(m\) je málo. Ak pre každé možné \(m\) nájdeme minimálne \(k\), tak sme našli riešenie. Naskytá sa nám celkom štandardné riešenie dynamickým programovaním – stav je určený počtom kartičiek ktorým sme už určili typ a súčtom \(m\) týchto kartičiek. Pre každý stav si pamätáme minimálny súčin \(k\) pre zvyšné kartičky. V každom stave sa do ďalšieho stavu dostaneme určením typu ďalšej kartičky. Teda:

dp[i+1][m] = min(dp[i+1][m], dp[i][m] * k_i) # ak použijeme % kartičku
dp[i+1][m+m_i] = min(dp[i+1][m+m_i], dp[i][m]) # ak použijeme g kartičku

Poznámky k implementácii

Nakoniec, aby sme vedeli vypísať riešenie, musíme vedieť z tabuľky nejako vyčítať ako sme určovali kartičky. Toto si vieme v tabuľke buď priamo pamätať, alebo si to vieme v prípade tejto úlohy jednoducho spätne zistiť (keďže existujú iba dve možnosti), čo nám ušetrí pamäť a kúsok urýchli program (nie asymptoticky, ale iba konštantne).

Vieme ešte riešenie urýchliť? Mohli by sme veľkosť tabuľky ďalej zmenšiť tým, že jednotlivé riadky budú mať veľkosť iba doterajšieho súčtu gramáží kartičiek. Tomuto ďalej pomôžeme ak si kartičky na začiatku utriedime podľa gramáže, keďže v tomto prípade bude veľkosť tabuľky minimálna. Znova, nejde o asymptotické zlepšenie, ale vieme takto reálne program zrýchliť dvojnásobne.

Dynamiku neodporúčame kódiť v Pythone, keďže priamy prepis C++ do Pythonu je často krát 100x pomalší. Dodatočnými optimalizáciami vieme získať násobne zrýchlenia, ale môžeme byť šťastný keď sa dostaneme na 30x spomalenie. Ako malý tip povieme, že je oveľa rýchlejšie napísať if x < y: y = x než y = min(y, x).

V úlohách kde násobíme veľa desatinných čísel a záleží nám na presnosti sa väčšinou oplatí počítať si súčet logaritmov namiesto priameho súčinu. V tomto prípade to však nie je nutné, keďže násobíme maximálne \(40\) čísel, čo zvládneme presne uložiť do dostatočne veľkého dátového typu.

Zložitosť

Časová a pamäťová zložitosť je \(O(N \times \sum A_i) = O(N^2 \times MaxA)\). Vzorové riešenie v C++ zvláda vstupy aj pre \(N=100\).

Často upozorňujeme, že pamäťová zložitosť sa pri úlohách s dynamickým programovaním dá znížiť na veľkosť menšiu ako celkový počet stavov. Väčšinou to dosiahneme tak, že si pamätáme iba posledné dva riadky tabuľky. V tomto prípade si však v tabuľke okrem najlepšieho výsledku implicitne pamätáme aj cestu a teda ich nemôžeme zabudnúť! Alebo? V skutočnosti to je možné a dokonca bez toho aby sa nám zhoršila časová zložitosť. Viac informácií nájdete v tomto codeforces tutoriáli v poslednom odseku sekcie Store results only for two layers of DP state domain.

Uvedomme si, že všetky tri uvedené riešenie prehľadajú všetkých \(2^N\) možností. Prvý prístup naivne, druhý šikovne a tretí iba tak, že nevykonáva žiadnu robotu dva krát – dynamické programovanie pracuje iba na stavoch, ktoré sú relevantné a pre každý takýto stav si pamätá iba jeden výsledok. Toto je dôvod, prečo tieto riešenia fungujú, zatiaľ čo heuristiky a greedy riešenia nie.

INF = 1e18
div = lambda x: 1 - x / 100

def solve():
    N, X = map(int, input().split())
    C = [tuple(map(lambda s: int(s[:-1]), input().split())) for _ in range(N)]

    dp = [[1.0]]
    for ni in range(N):
        xm, xd = C[ni]
        dp.append([INF] * (len(dp[ni]) + xm))
        d = div(xd)
        for mi in range(len(dp[ni])):
            if dp[ni][mi] == INF:
                continue
            dp[ni + 1][mi] = min(dp[ni + 1][mi], dp[ni][mi] * d)
            dp[ni + 1][mi + xm] = min(dp[ni + 1][mi + xm], dp[ni][mi])

    finish = (X, -1)
    for mi, d in enumerate(dp[-1]):
        finish = min(finish, (X * d - mi, mi))

    mi = finish[1]
    ans = []
    for ni in range(N - 1, -1, -1):
        xm = C[ni][0]
        card = mi >= xm and dp[ni + 1][mi] == dp[ni][mi - xm]
        ans.append((card, ni))
        mi -= card * xm
    ans.sort()
    for card, ni in ans:
        print(ni + 1, "%g"[card])

TC = int(input())
for _ in range(TC):
    solve()

#include "fezjo.h"

void solve() {
    int N, X;
    cin >> N >> X;

    vector<pair<int, int>> C(N);
    char trash;
    for (int i = 0; i < N; i++)
        cin >> C[i].first >> trash >> C[i].second >> trash;
    
    auto [final, ans] = solve(N, X, C);
    for (auto [card, ni] : ans)
        cout << (ni + 1) << " " << "%g"[card] << '\n';
    // cerr << fixed << setprecision(10) << final << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int TC;
    cin >> TC;
    while (TC--)
        solve();
}