Гужва
Аутор: Алекса Милисављевић и Младен Пузић
Текст и тест примери: Алекса Милисављевић
Тестирање: Драган Урошевић
Анализа решења: Младен Пузић
Даље у решењима ћемо рећи да се крећемо на доле уколико се померамо са поља (i, j) на поље (i+1, j), у супротном се крећемо удесно.
Решење када N = 2
На тачно једној позицији ћемо се померити на доле, сви остали потези биће удесно. Означимо са d_i број навијача које сретнемо уколико се у колони i померимо на доле. Овај низ можемо израчунати користећи префиксни збир над горњим редом и суфиксни збир над доњим редом.
Уколико је блокирано неко поље у првом реду, нпр. (1, i), онда се морамо померити на доле пре i-те колоне, па је решење \min(d_1, d_2, \ldots d_{i-1}). Уколико је блокирано неко поље у другом реду, нпр. (2, j), онда се морамо померити на доле после i-те колоне, па је решење \min(d_{i+1}, d_{i+2}, d_M).
Временска сложеност је O(M+Q), а меморијска O(M).
Решење када Q \leq 100, N, M \leq 7
Решење можемо добити brute force методом, односно испробавањем свих могућих путева од првог до последњег поља, за свако блокирано поље. Таквих путева постоји {N+M-2 \choose N-1} (имамо укупно N+M-2 корака, од којих бирамо N-1 да буду усмерени на доле). Све путеве можемо проверити рекурзијом.
Временска сложеност је O(Q\cdot{N+M-2 \choose N-1}), а меморијска O(NM).
Решење када Q \leq 2000, N \cdot M \leq 2000
За свако блокирано поље, користићемо динамичко програмирање - израчунаћемо dp_{i, j}, најмањи број навијача које морамо да сретнемо на путу од (1, 1) до (i, j), ако не посетимо тренутно блокирано поље. Јасно је да важи dp_{1, 1} = a_{1, 1} и dp_{i, j} = dp_{i-1, j} + dp_{i, j-1}, с тим што приликом рачунања увек прескачемо поља која су ван матрице и тренутно блокирано поље. Решење се онда налази у dp_{N, M}.
Временска сложеност је O(QNM), а меморијска O(NM).
Решење када Q \leq 10^4
Као у претходном решењу, израчунајмо низ A_{i, j} - најмањи број навијача које морамо да сретнемо на путу од (1, 1) до (i, j), и слично B_{i, j} - најмањи број навијача које морамо да сретнемо на путу од (i, j) до (N, M).
Рецимо да блокирамо поље (x, y). Посматрајмо сва поља (x', y') за која важи x+y = x' + y'. Можемо видети да се заправо сва ова поља налазе на истој дијагонали, као и да на сваком путу од (1, 1) до (N, M) пролазимо кроз тачно једно од ових поља.
Ово нам говори да, како бисмо гарантовали да не пролазимо кроз поље (x, y), довољно је да гарантујемо да пролазимо кроз неко друго поље на овој дијагонали. Можемо наћи пут са најмање навијача који пролази кроз поље (i, j) са A_{i, j} + B_{i, j} - a_{i, j}.
Можемо, дакле, проћи кроз сва поља на дијагонали блокираног поља и видети за које добијамо најмањи пут. Битно је приметити да је број поља на тој дијагонали највише \min(N, M), што је мање од \sqrt{NM}.
Временска сложеност је O(Q\cdot \sqrt{N M} + NM), а меморијска O(NM).
Главно решење
Урадимо све исто као у претходном решењу, сем што ћемо ефикасније наћи минимум на дијагонали без једног поља. То ћемо урадити тако што ћемо чувати префиксни и суфиксни минимум за сваку дијагоналу. За блокирано (x, y) узећемо минимум од префикса до (x-1, y+1) и суфикса од (x+1, y-1).
Временска сложеност је O(Q + NM), а меморијска O(NM).