A

Kubo chce odpovedať na otázky typu “koľko ľudí nastúpilo od prvej po niekoľkú zastávku za prvých niekoľko dní”. Čo keby si teda všetky odpovede (pre každú zastávku a deň) vypočítal dopredu a potom ich iba čítal z tabuľky?

Ak máme $n$ zastávok a $m$ dní, potom potrebuje mať napísaných $n\cdot m$ čísel, ale na každú otázku už vie odpovedať hneď.

Takejto tabuľke sa hovorí aj _dvojrozmerné prefixové súčty. Myšlienka je vlastne podobná ako pri tých jednorozmerných (z minulého kola), akurát tu chceme rýchlo vedieť zistiť súčet nielen úseku, ale aj ľubovoľného obdĺžniku v tabuľke.

B

Takže ako takéto niečo vypočítame? Rovnako ako pri obyčajných prefixových súčtoch, budeme ich počítať postupne po riadkoch a využijeme to, čo sme už predtým spočítali. Dajme tomu, že chceme zistiť súčet pre nejaké políčko, tak to je súčet čísla na tom políčku a zvyšku toho obdĺžniku. Ako zistíme súčet v zvyšku obdĺžniku? Mohli by sme skúsiť zobrať prefixový súčet nad naším políčkom – teda súčet v obdĺžniku ktorý chceme, ale bez posledného riadku. Tak si napríklad môžeme pamätať, aký máme zatiaľ súčet v riadku, a to ešte pripočítať, a tým dostaneme súčet, ktorý hľadáme.

Pre jednoduchosť budeme ďalej predpokladať, že v tabuľke máme navyše ľavý stĺpec a horný riadok núl, aby sme nemuseli špeciálne riešiť, čo sa deje na kraji tabuľky.

def dvojrozmerne_prefixove_sucty(tabulka):
    sucty = [[0] * len(tabulka[0])] # prvy riadok s nulami
    for riadok in tabulka:
        sucet_v_riadku = 0
        sucty.append([0]) # nula na zaciatku riadku
        for i in range(len(riadok)):
            sucty[-1].append(riadok[i] + tabulka[-2][i] + sucet_v_riadku)
    return sucty

C

Zatiaľ vieme z tabuľky rýchlo zistiť súčty obdĺžnikov, ktoré majú ľavý horný roh v ľavom hornom rohu tabuľky. Teraz by sme chceli vedieť zistiť súčet hocijakého obdĺžniku.

Spravíme to podobne ako v úlohe z minulého kola: zoberieme políčko v tabuľke v pravom dolnom rohu obdĺžniku, ktorý chceme. Takto zarátame do súčtu všetky políčka, ktoré chceme, ale aj nejaké navyše, tie by sme teda chceli odčítať.

Môžeme teda odčítať obdĺžnik hore od toho čo chceme.

Stále ale máme niečo naľavo, tak odčítajme aj obdĺžnik naľavo.

Lenže obdĺžnik vľavo hore sme teraz už odpočítali dvakrát. Tak ho tam zase pripočítajme.

A takto dostaneme presne súčet v obdĺžniku, ktorý sme chceli. Stačili nám na to $4$ sčítania.

def sucet_v_obdlzniku(riadok_zac, stlpec_zac, riadok_kon, stlpec_kon):
    return prefixove_sucty[riadok_kon + 1][stlpec_kon + 1] \
         - prefixove_sucty[riadok_kon + 1][stlpec_zac] \
         - prefixove_sucty[riadok_zac][stlpec_kon + 1] \
         + prefixove_sucty[riadok_zac][stlpec_zac]

D

Tak a teraz keď už vieme, ako to spočítať, poďme to na niečo využiť.

Hľadáme v tabuľke obdĺžnik s najväčším súčtom. Mohli by sme sa pozrieť na všetky obdĺžniky a zistiť, ktorý má najväčší súčet. Obdĺžnikov je približne $n^2\cdot m^2$ (pre každú dvojicu riadkov a stĺpcov máme jeden[^1]), takže potrebujeme približne toľko sčítaní.

Toto riešenie ale vieme zlepšiť tak, že ich bude stačiť iba približne $m\cdot n^2$ (alebo $n\cdot m^2$ podľa toho, čo je lepšie, jednoducho otočíme tabuľku).

Pozrime sa na všetky tie obdĺžniky, ktoré začínajú a končia v nejakej konkrétnej dvojici riadkov. Na to, aby sme si z nich vybrali nejaký jeden, ešte potrebujeme určiť začiatočný a konečný stĺpec.

Čo nám to pripomína? No predsa hľadanie najväčšieho súčtu na nejakom úseku, čo bola úloha v minulom kole! Môžeme si to predstaviť tak, že keď si vyberieme nejaký začiatočný aj konečný riadok, to je vlastne taký veľký obdĺžnik od ľavého kraja tabuľky po pravý. A v ňom chceme nájsť taký obdĺžnik, ktorý má čo najväčší súčet, ale je od horný až po dolný okraj.

Teda z veľkého obdĺžniku budeme vždy brať len celé stĺpce a rozhodujeme sa, ktorý úsek stĺpcov zoberieme.

Čiže nám stačí si z prefixových súčtov vypočítať súčty jednotlivých stĺpcov, a potom medzi nimi nájsť úsek s čo najväčším súčtom tak, ako v minulom kole.

Takže si to zopakujeme: pre každú dvojicu riadkov si zoberieme obdĺžnik medzi týmito dvomi riadkami a v ňom si spočítame súčty v stĺpcoch. Medzi týmito súčtami stĺpcov nájdeme úsek s najväčším súčtom (podľa úlohy z minulého kola), čím dostaneme obdĺžnik s najväčším súčtom spomedzi tých, ktoré začínajú a končia v našich vybratých riadkoch. No a toto skúsime pre každú dvojicu riadkov, čím dostaneme odpoveď.

def obdlznik_s_najvacsim_suctom(n, m):
    odpoved = 0  # tvarime sa, ze sucet bude aspon 0
    for riadok_zac in range(n):
        for riadok_kon in range(riadok_zac, n):
            # spocitame sucty v stlpcoch
            sucty_v_stlpcoch = []
            for stlpec in range(m):
                sucty_v_stlpcoch.append(
                    sucet_v_obdlzniku(riadok_zac, stlpec, riadok_kon, stlpec)
                )
            # pouzijeme z minuleho kola
            najvacsi_sucet = najvacsi_sucet_na_useku(sucty_v_stlpcoch)
            odpoved = max(odpoved, najvacsi_sucet)
    return odpoved

[^1] V skutočnosti je to $nm(n-1)(m-1)/2$, ale taký rozdiel nás veľmi netrápi. Keď potom nájdeme lepšie riešenie, uvidíme že nám to spraví oveľa väčší rozdiel.