Finále

E: Tání ledovců

Řešení (Zadání úlohy)

Lehká verze

Nabízí se situaci odsimulovat nejpřímočařejším způsobem. Náš algoritmus si bude pamatovat, která políčka jsou potopená a která ne. Půjde od dne 1 do dne R a každý den:

  • Projde všechna políčka a pomocí prohledávání do šířky (BFS) najde komponenty souvislosti, tedy kusy ledovce oddělené vodou.
  • Pokud existuje víc než jeden kus, najdeme ten nejmenší a o všech ostatních řekneme, že se potopily.
  • Spočítáme zbývající iglú a jejich počet přičteme k výsledku.
Protože v každém z R dní procházíme všechna políčka, bude algoritmus trvat O(RN2). To na lehkou verzi stačí.

Těžká verze

Obecně je často jednodušší nějaké struktury spojovat než rozdělovat; na spojování například existuje jednoduchá datová struktura zvaná DFU nebo DSU. My se zde obejdeme bez ní, ale myšlenku spojování využijeme. Půjdeme totiž proti směru času a představíme si, že se objevují nová políčka, která kusy ledovce slučují.

Chtěli bychom tedy začít tím, že spočítáme, kolik iglú se nepotopilo na konci dne R. Spočítáme si, jak vypadá ledovec, když roztají všechna políčka od dne 1 do R, ale nebudeme potápět kusy ledovce v případě, že se rozdělí. Máme tedy nějaký potenciálně větší počet kusů ledovce a zajímá nás, který z nich je ten, který se jako jediný ještě nepotopil po R dnech. Nahlédneme, že to nutně musí být ten nejmenší kus, a že je jednoznačný. To je zaručené kombinací těchto podmínek ze zadání:

  • Pokud se tak ledovec rozdělil na více částí, které se nedotýkají, tak se všechny části kromě nejmenší potopí.
  • Vždy, když se ledovec rozdělí na víc částí, bude existovat jednoznačná nejmenší část.
  • Nikdy neroztaje políčko, které už předtím roztálo nebo se potopilo.

Umíme tak spočítat iglú na konci dne R. Co takhle o den dříve? Podíváme se na políčko, které roztálo v den R. Podle zadání toto políčko musí sousedit s kusem, který neroztál po dni R. Může a nemusí sousedit i s dalšími kusy. Pokud sousedí, znamená to, že tyto dva kusy byly na konci dne R-1 stále jeden (nepotopený) kus. K momentálnímu počtu iglú tedy přičteme počet iglú na sousedících kusech. Tento postup pak můžeme opakovat pro všechny dny, dokud se nedostaneme k počátečnímu stavu. Nasčítáme počty iglú v jednotlivých dnech a máme výsledek.

Z hlediska implementace bude algoritmus fungovat tak, že každému políčku ledovce po dni R (opět ignorujeme potápění kusů; bereme v úvahu jen to, že políčka tají) přiřadíme číslo kusu, na kterém se nachází; najdeme tedy komponenty souvislosti, podobně jako v lehké verzi. Spočítáme pro každý kus velikost a počet iglú. Budeme si udržovat množinu M čísel kusů, které jsou nepotopené v momentálním dni. Na začátku v této množině bude pouze nejmenší kus. Pamatujeme si taky počet iglú g. Pak půjdeme od dne R po den 1. Řekněme, že roztálo políčko p. Chceme zjistit stav před tím, než p roztálo. Podíváme se na sousedy p. Pro každého souseda p, který není v M, ho tam přidáme a přičteme ke g jeho počet iglú.

Tento algoritmus zabere O(N2 + R); určování kusů trvá O(N2) a procházení po dnech O(R).

Ukázkový program (C++)

#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

int n, k, r;
int velikost_kusu[555 * 555];
int iglu_kusu[555 * 555];
int d[8][2] = {{ -1, -1}, { -1, 0}, { -1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

bool validniSouradnice(int x, int y) {
    return !(x < 0 || x >= n || y < 0 || y >= n);
}

void solve() {
    set<pair<int, int>> iglu;
    vector<pair<int, int>> dny;
    scanf("%d%d%d", &n, &k, &r);
    vector<vector<int>> kus(n, vector<int>(n, 0));
    for (int i = 0; i < k; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        iglu.insert({x, y});
    }
    for (int i = 0; i < r; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        dny.push_back({x, y});
        kus[x][y] = -1;
    }
    // Faze 1: hledani kusu
    int c = 1;
    int c_pocatecni = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (kus[i][j] != 0) {
                continue; // Toto policko uz jsme prohledali
            }
            velikost_kusu[c] = iglu_kusu[c] = 0;
            // Najdi zbytek kusu pomoci BFS (DFS jde take)
            queue<pair<int, int>> q;
            q.push({i, j});
            while (!q.empty()) {
                pair<int, int> coords = q.front();
                q.pop();
                kus[coords.first][coords.second] = c;
                iglu_kusu[c] += iglu.count(coords);
                velikost_kusu[c]++;
                // Prohledej sousedy
                for (int l = 0; l < 8; l++) {
                    int nx = coords.first + d[l][0], ny = coords.second + d[l][1];
                    if (!validniSouradnice(nx, ny) || kus[nx][ny] != 0) {
                        continue;
                    }
                    kus[nx][ny] = c;
                    q.push({nx, ny});
                }
            }
            if (velikost_kusu[c] < velikost_kusu[c_pocatecni]) {
                c_pocatecni = c; // Chceme zacit v nejmensim kusu
            }
            c++;
        }
    }
    // Faze 2: slucovani kusu
    int pocet_iglu = iglu_kusu[c_pocatecni];
    ll vysledek = 0;
    set<int> M = {c_pocatecni}; // Kusy, ktere nejsou potopene
    for (int i = r - 1; i >= 0; i--) {
        vysledek += pocet_iglu;
        int x = dny[i].first, y = dny[i].second;
        if (iglu.count(dny[i])) {
            pocet_iglu++; // Iglu stalo na policku, ktere roztalo
        }
        for (int l = 0; l < 8; l++) {
            int nx = x + d[l][0], ny = y + d[l][1];
            if (!validniSouradnice(nx, ny)) {
                continue;
            }
            int c_kusu = kus[nx][ny];
            if (c_kusu > 0 && !M.count(c_kusu)) { // c_kusu > 0 znamena, ze policko neroztalo
                // Nasli jsme novy kus
                M.insert(c_kusu);
                pocet_iglu += iglu_kusu[c_kusu];
            }
        }
    }
    printf("%lld\n", vysledek);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
}

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)