4. Školské pomôcky vzorové riešenie

2 6 20
1 16 24
1 8 11
2 12 18
1 6 7
2 13 15
2 25 15

11

2 6 12
2 8 17
1 6 10
1 9 4
2 12 5
2 11 23
1 12 5

0

Bruteforce

Najjednoduchšie riešenie tejto úlohy je vyskúšať každú kombináciu pomôcok, ktorú Peťko vie v obchode nájsť. Pre prvú sadu je to jednoduché, pretože vyskúšame každú dvojicu pomôcok typu \(1\) a \(2\), a vyberieme dvojicu, ktorá sa zmestí do rozpočtu a má najvyššiu kvalitu. Pre druhú sadu je takéto riešenie pomalé a stačiť nebude.

Pre tretiu sadu vieme použiť rovnaký princíp – vyškúšať každú kombináciu pomôcok. Bude to však ťažšie ako pri prvej sade, lebo máme rôzny počet typov. Takéto niečo vieme pomerne v pohode vyriešiť rekurzívnym DFS prehľadávaním všetkých možností. Pre štvrtú sadu je takéto riešenie pomalé.

Rýchlejšie riešenie pre dva typy

Pozrime sa na trochu lepšie riešenie, ktoré prejde cez druhú sadu. Naše riešenie bude počítať s tým, že sú iba dva typy pomôcok. Pomôcky si rozdelíme do dvoch polí podľa ich typov a tieto polia zoradíme podľa kvality. Náš program pôjde zozadu oboch polí a bude sa snažiť kupovať najkvalitnejšie pomôcky. Vezmeme najkvalitnejšiu pomôcku z jedného typu a dáme ju do páru s najlacnejšou pomôckou druhého typu, ktorá má aspoň takú kvalitu ako tá najkvalitnejšia z prvého typu.

Najlacnejšiu pomôcku s aspoň takou kvalitou vieme nájsť jednoducho. Pôjdeme zozadu poľa druhého typu cez všetky pomôcky, ktoré sú väčšie alebo rovné kvalite prvej pomôcky a zistíme, ktorá je najlacnejšia. Keď sa v poli prvého typu posunieme o jednu pomôcku doľava, nemusíme v druhom poli začínať znova od konca. Stačí pokračovať od miesta kde sme naposledy prestali (premyslite si prečo). Tento prístup sa nazýva dvaja bežci. Alternatívne, keďže sme si polia utriedili, môžeme, bez zhoršenia časovej zložitosti, pomôcky v druhom poli binárne vyhľadávať.

Ak je cena tejto dvojice pomôcok vyššia ako je rozpočet, tak musíme hľadať ďalej. Takéto riešenie má časovú zložitosť \(O(n \log(n) + n)\). Avšak, toto riešenie prejde iba cez prvé dve sady. My potrebujeme riešenie, ktoré počíta s tým, že počet typov pomôcok je variabilný.

Ak nevieme prísť na vzorové riešenie, ale chceme maximaizovať náš počet bodov. Vieme skombinovať toto riešenie a bruteforce pre \(t > 2\) a získať body za prvé tri sady. Samozrejme treba dávať pozor, ktoré riešenie používame pri akej sade.

Vzorové riešenie

Úlohu vyriešime pomocou binárneho vyhľadávania, ktoré nám pomôže nájsť najvyššiu kvalitu pomôcok za cenu, ktorú si vie Peťko dovoliť. Binárne vyhľadáme kvalitu \(k\), ktorá spĺňa naše požiadavky. Ak chceme dosiahnúť aspoň kvalitu \(k\), tak sa pre každý typ pomôcky pokúsime nájsť najlacnejšiu pomôcku, ktorá má aspoň kvalitu \(k\). Ak je súčet týchto najlacnejších pomôcok väčší ako počet peňazí, tak musíme hľadať ďalej a skúsime menšie \(k\). Ak je súčet pomôcok menší alebo rovný ako počet peňazí, tak sme našli jedno možné riešenie, ale stále chceme pokračovať ďalej a vyskúšať väčšie \(k\). Pokračujeme až kým sa nám neminú možnosti. V takom prípade sme buď našli najvyššiu kvalitu pomôcok, ktorú si vie Peťko dovoliť, alebo sme zistili, že také pomôcky neexistujú. Riešenie má časovú zložitosť \(O(n \log(n) + n)\).

Existuje ešte ďalšie riešenie, ktoré je zovšeobecnením rýchleho riešenia pre dva typy. Pomôcky si zoradíme podľa kvality. Použijeme úplne ten istý prístup ako pri dvoch typoch – pozerieme sa na pomôcku z nejakého typu a snažíme sa nájsť súčet najlacnejších pomôcok všetkých zvyšných typov, ktoré majú aspoň takú kvalitu. Avšak, toto hľadanie musíme robiť v \(O(1)\). Ak spravíme niečo ako techniku \(t\) bežcov, tak si nám stačí tento súčet aktualizovať pri posune bežca. Takéto riešenie má časovú zložitosť \(O(n \log(n))\). Ak to chceme ešte úplne vyhrotiť, tak na zoradenie polí môžeme použiť bucketsort a tak bude mať naše riešenie časovú zložitosť \(O(n)\). Detaily si môžete pozrieť v kóde.

def pc(a, v):
    best = -1
    for x in a:
        if x["v"] >= v:
            if best == -1:
                best = x["p"]
            else:
                best = min(best, x["p"])
    return best

def ok(a, k, q, money):
    sm = 0
    for t in range(k):
        price = pc(a[t], q)
        if price == -1:
            return False
        sm += price
    return sm <= money

t, n, m = map(int, input().split())
    
a = [list() for _ in range(t)]
b = 0
for i in range(n):
    it, ip, iv = map(int, input().split())
    a[it - 1].append({"p": ip, "v": iv})
    b = max(b, iv)

lo, hi = 0, b + 1
while hi - lo > 1:
    mid = (hi + lo) // 2
    if ok(a, t, mid, m):
        lo = mid
    else:
        hi = mid

print(lo)

# BUCKET sort the items by quality, then search items from the best quality
# Time complexity: O(n)

INF = 10 ** 12
n_typov, n_pomocok, vreckove = map(int, input().split())

kvalitove_pomocky = [[] for _ in range(5 * n_pomocok + 1)]
vstup = (map(int, input().split()) for _ in range(n_pomocok))
for typ, cena, kvalita in vstup:
    kvalitove_pomocky[kvalita].append((cena, typ - 1))

chyba_typov = n_typov
sucet_cien = 0
min_ceny = [INF] * n_typov
for kvalita in range(5 * n_pomocok, -1, -1):
    for cena, typ in kvalitove_pomocky[kvalita]:
        if min_ceny[typ] == INF:
            sucet_cien += cena
            min_ceny[typ] = cena
            chyba_typov -= 1
        elif cena < min_ceny[typ]:
            sucet_cien += cena - min_ceny[typ]
            min_ceny[typ] = cena
        if chyba_typov == 0 and sucet_cien <= vreckove:
            print(kvalita)
            exit()

print(0)