6. Just načas vzorové riešenie

100 5
11 300 700
12 900 300
13 500 700
17 800 0
20 600 0

2

Čo chceme zistiť

Úloha sa nás pýta, koľko najmenej sypaní Janči nestihne. To je celkom zvláštna formulácia otázky, ktorá sa ale vlastne pýta len to, koľko najviac sypaní stihne – keďže poznáme celkový počet sypaní.

Ako to zistíme

Keďže deň je naozaj dlhý, nestihneme simulovať, kde sa traktor môže nachádzať v každom možnom čase. To nám však nevadí, pretože väčšina časov je pre nás úplne nezaujímavá – jediné podstatné sú tie, v ktorých nejaký kombajnista vysype náklad.

To, či v danom čase stihneme náklad zobrať, ale záleží na tom, kde sa traktor nachádzal predtým. Dopredu pritom nevieme, či sa nám náklad oplatí zobrať, alebo ísť počas tej doby radšej niekam inam.

Na takýto typ problému sa teda hodí použiť dynamické programovanie – nebudeme sa snažiť zistiť, ktorú postupnosť sypaní je najlepšie stihnúť, ale pre každé sypanie sa pozrieme, koľko najviac sypaní by sa dalo stihnúť, ak by sme sa rozhodli stihnúť aj to aktuálne. Nakoniec sa pozrieme na celkovo najlepší výsledok zo všetkých možných sypaní.

V čom to spočíva?

Aby dynamické programovanie fungovalo, musíme si vedieť v každej časti úlohy – stave – pomôcť nejakou časťou, ktorú už sme predtým vyriešili. Keďže sa na sypania pozeráme chronologicky, vieme, že pri riešení konkrétneho sypania sme už všetky predošlé vyriešili optimálne, a tie budúce nás zatiaľ zaujímať nemusia, lebo každé z nich budeme riešiť zvlášť neskôr. Preto nám stačí zistiť, po ktorých z predošlých sypaní sa dá stihnúť to aktuálne a z nich vybrať také, kde sme predtým stihli najviac. K tomuto najlepšiemu výsledku pripočítame \(1\) (že sme stihli aj aktuálne) a uložíme si to ako najlepší výsledok pre aktuálne sypanie. Ukladať si počty stihnutých sypaní budeme do samostatného poľa, v ktorom bude pre každé sypanie výsledok na takom indexe, aký majú súradnice daného sypania v poli súradníc a časy v poli časov. Vďaka tomu sa jednoducho dostaneme ku všetkým informáciam o každom sypaní.

Ako zistiť, či je jedno sypanie stihnuteľné pred druhým? Potrebujeme, aby sa traktor vedel dostať z jedného miesta na druhé v čase najviac tak dlhom, ako je rozdiel časov sypaní. Keďže traktor sa pohybuje po štvorcovej mriežke, používame takzvanú Manhattanskú metriku – medzi každými dvoma miestami sa dá dostať tak, že najskôr ideme len horizontálne a potom len vertikálne. Takáto cesta je zároveň rovnako dobrá, ako ktorákoľvek, ktorá sa nevracia (opačným smerom, než už predtým šla), a je zároveň najlepšia možná. Vzdialenosť teda spočítame ako absolútnu hodnotu rozdielov jednej súradnice plus absolútnu hodnotu rozdielov druhej súradnice jednotlivých sypaní.

Koľko to trvá?

Celý deň. Ahá, myslíte spočítať. Pardón. Pre každé sypanie potrebujeme preskúmať všetky predošlé sypania (lebo to zatiaľ najlepšie mohlo byť veľmi dávno), pričom zistiť pre sypanie, či sa dalo stihnúť a či je lepšie, než sme našli doteraz, zvládneme v konštantnom čase, takže to dokopy trvá \(O(N^2)\). To nie je úplne zlé, ale prechádza to len na polovicu bodov!

Dá sa to zlepšiť?

Ako pri každej správnej šifre sa skúsme pozrieť, aké informácie sme ešte nepoužili. V zadaní sa píše o maximálnej ploche poľa, ktorá môže byť až \(250\,000\) hektárov. To je až \(250\,000\) štvorcov \(100\) krát \(100\) metrov. Pole je ale určite štvorcové, takže maximálny rozmer jednej jeho strany je \(500\) štvorcov. Všetky súradncice, na ktoré narazíme, tak možu mať len jednu z \(500\) rôznych hodnôt. To nám veľmi nepomôže, keďže súradnice si ukladáme ako čísla a problém s pamäťou nemáme.

Ale mohlo by nám pomôcť niečo, čo z toho vyplýva, a síce, že žiadne dva body nemajú vzdialenosť väčšiu, než \(2 \cdot 500\) štvorcov. Takže sa najneskôr za \(1000\) minút dostaneme na ľubovoľné iné miesto na poli – alebo ešte skôr, záleží na veľkosti poľa, ktorú si označme \(r\). To znamená, že keď sa pri aktuálnom sypaní pozeráme na sypania predošlé, nepotrebujeme nikdy ísť viac, než \(2r\) minút do minulosti. Teda vždy sa stačí pozerať najviac na posledných \(2r\) sypaní, keďže žiadne 2 neprebiehajú naraz.

Ako to použijeme?

Budeme si teda pamätať separátne pole zatiaľ celkovo najlepších výsledkov. Vždy, keď nájdeme najlepší výsledok pre dané sypanie, porovnáme ho s celkovo najlepším výsledkom doteraz a lepší výsledok si pridáme do tohto nového poľa. Vďaka tomu bude toto pole obsahovať neklesajúcu postupnosť čísel – takže najlepší výsledok dosiahnutý do nejakého sypania bude v tomto poli na indexe daného sypania.

Keď potom budeme pri každom aktuálnom sypaní prehľadávať sypania minulé, budeme to robiť len dovtedy, kým nenarazíme na nejaké, ktoré prebehlo od aktuálneho skôr o viac, než \(2r\) minút. V momente, keď také nájdeme, už totiž vieme, že všetky skoršie vieme dosiahnuť, a zaujíma nás len to, ktoré z nich je najlepšie. Túto hodnotu však už poznáme – je v novom poli na indexe sypania, na ktoré sme práve narazili.

Pomôže to?

Rozhodne áno. Namiesto toho, aby sme museli pre každé sypanie prejsť všetky predošlé sypania (ktorých môže byť až \(n\)), stačí prejsť najviac \(r\) predošlých sypaní. Vieme, že \(r = \sqrt{h}\). Časová zložitosť sa tak zlepší na \(O(n * r)\), teda \(O(n * \sqrt{h})\).

Pamäťová zložitosť sa nezhorší, pamätáme si len jedno pole naviac k tomu, čo sme si museli pamätať doteraz. To boli tiež len polia s časmi, súradnicami a najlepšími výsledkami pre jednotlivé sypania, takže celková pamäťová zložitosť je \(O(n)\).

def solve():
    h, n = map(int, input().split())
    r = int(h**(1 / 2)) # Spočítame dĺžku strany poľa - r

    # events sú jednotlivé časy a súradnice sypaní,
    # best_here je najlepší počet dosiahnuteľný, ak Janči
    # skončí na danom mieste v danom čase,
    # best_anywhere je najlepší počet,
    # ktorý v danom čase vieme dosiahnuť na ľubovoľnom mieste.
    # Všade pridáme aj začiatočnú pozíciu:
    # v čase 0 na súradniciach (0, 0) s 0 stihnutými kombajnistami.
    best_here = [0 for i in range(n + 1)]
    best_anywhere = [0 for i in range(n + 1)]
    events = [(0, 0, 0)]

    # Načítame časy a súradnice.
    for i in range(1, n + 1):
        time, x, y = map(int, input().split())
        events.append((time, x // 100, y // 100))

    # Pre každé sypanie sa pozeráme postupne na predošlé,
    # dokým nie je jasné, že vieme dosiahnuť všetky,
    # potom použijeme best_anywhere.
    # Inak sa snažíme použiť predošlé best_here,
    # ak sa dá dosiahnuť a oplatí sa to.
    for i in range(1, n + 1): # i je index aktuálneho sypania,
                              # ktoré sa práve snažíme vyriešiť.
        for j in range(i - 1, -1, -1): # j je postupne index všetkých
                                       # predošlých sypaní.
            if events[i][0] - events[j][0] > 2 * r:
                # Vieme dosiahnuť všetky, nemá zmysel hľadať ďalej.
                best_here[i] = max(best_here[i], best_anywhere[j] + 1)
                break
            if best_here[j] + 1 > best_here[i]:
                # Zatiaľ najlepšia možnosť...
                if (abs(events[i][1] - events[j][1]) + 
                        abs(events[i][2] - events[j][2]) <=
                        events[i][0] - events[j][0]):
                        # ...a vieme ju dosiahnuť z aktuálnej pozície.
                    best_here[i] = best_here[j] + 1
        
        # Ak sme vedeli nejaký počet stihnúť predtým, vieme aj teraz.
        best_anywhere[i] = max(best_anywhere[i - 1], best_here[i])
    
    # Na konci nám je jedno, kde skončíme,
    # nemusíme pritom stihnúť posledné sypanie.
    print(n - best_anywhere[n])

solve()

#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace::std;

int main(){
    // times sú jednotlivé časy, coords súradnice sypaní,
    // best_here je najlepší počet dosiahnuteľný, ak Janči
    // skončí na danom mieste v danom čase,
    // best_anywhere je najlepší počet,
    // ktorý v danom čase vieme dosiahnuť na ľubovoľnom mieste.
    vector<int> times, best_here, best_anywhere;
    vector<pair<int, int>> coords;

    int h, n, x, y;
    cin >> h >> n;
    // Spočítame dĺžku strany poľa - r.
    int r = sqrt(h);

    // Všade pridáme aj začiatočnú pozíciu:
    // v čase 0 na súradniciach (0, 0) s 0 stihnutými kombajnistami.
    times = best_here = best_anywhere = vector<int>(n + 1, 0);
    coords = vector<pair<int,int>>(n + 1, 0);
    
    // Načítame časy a súradnice.
    for (int i = 1; i <= n; i++){
        cin >> times[i] >> x >> y;
        coords[i] = make_pair(x / 100, y / 100);
    }

    // Pre každé sypanie sa pozeráme postupne na predošlé,
    // dokým nie je jasné, že vieme dosiahnuť všetky,
    // potom použijeme best_anywhere.
    // Inak sa snažíme použiť predošlé best_here,
    // ak sa dá dosiahnuť a oplatí sa to.
    for (int i = 1; i <= n; i++){ // i je index aktuálneho sypania,
                                  // ktoré sa práve snažíme vyriešiť.
        for (int j = i - 1; j >= 0; j--){ // j je postupne index všetkých
                                          // predošlých sypaní.
            if (times[i] - times[j] > 2 * r){
                // Vieme dosiahnuť všetky, nemá zmysel hľadať ďalej.
                best_here[i] = max(best_here[i], best_anywhere[j] + 1);
                break;
            }
            if (best_here[j] + 1 > best_here[i]) // Zatiaľ najlepšia možnosť...
                if (abs(coords[i].first - coords[j].first) +
                    abs(coords[i].second - coords[j].second) <=
                    times[i] - times[j]) { // ...a vieme ju dosiahnuť z aktuálnej pozície.
                        best_here[i] = best_here[j] + 1;
                    }
        }
        // Ak sme vedeli nejaký počet stihnúť predtým, vieme aj teraz.
        best_anywhere[i] = max(best_anywhere[i - 1], best_here[i]);
    }
    // Na konci nám je jedno, kde skončíme, nemusíme pritom stihnúť posledné sypanie.
    cout << n - best_anywhere[n] << endl;
}