Zadatak „Boja“ – analiza rešenja

U zadatku Boja imamo niz x₁…xₙ i za svaki od q tipova kofica (kapaciteta yᵢ) treba da izbrojimo koliko kontinuiranih podsekvenci imaju zbir deljiv sa yᵢ.

Ideja (ključna matematička transformacija)

Neka je pref[i] prefiksna suma prvih i elemenata (sa pref[0] = 0). Suma segmenta [l+1..r] je pref[r] - pref[l]. Taj zbir je deljiv sa y tačno kada

(pref[r] - pref[l]) % y == 0 ⇔ pref[r] % y == pref[l] % y

Dakle, za fiksni y broj zadovoljnih segmenata jednak je broju pari prefiksa sa istim ostatkom modulo y.

1) Naivno (ispravno ali sporo)

Direktna provera svih parova (l, r) daje jednostavno, jasnu implementaciju, ali je O(n²) po jednoj vrednosti y:

// Naivno rešenje (pseudokod / C++)
for (int r = 1; r <= n; ++r) {
  for (int l = 0; l < r; ++l) {
    long long s = pref[r] - pref[l];
    if (s % y == 0) ans++;
  }
}

Komentar: ovo je tačno — proverava sve podsekvence — ali za n = 8000 ovo može biti prihvatljivo jednom, ali ako moraš to raditi za svaki od q tipova (npr. q = 8000), vreme postaje preveliko (O(n²·q)).

Primer rada na malom nizu

Neka je x = [4,2,3], y = 4 — naivno proverava sve 6 segmenata i nađe 1 (samo [4]).

2) Brzo i praktično rešenje — prefiks + mapa ostataka (O(n) po jednom `y`)

Koristimo ideju iz dela “Ideja” i brojimo koliko puta se do sada pojavio svaki ostatak pref[i] % y. Svaki put kada naiđemo na ostatak r, broj novih segmenta koji se završavaju u toj tački jednak je broju prethodnih prefiksa sa istim ostatkom.

Ispravan C++ kod

// Ispravno rešenje: O(n) za svaki y
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<long long> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];

    vector<int> y(q);
    for (int i = 0; i < q; ++i) cin >> y[i];

    // pref[0] = 0; pref[i] = sum prvih i elemenata
    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + x[i - 1];

    for (int t = 0; t < q; ++t) {
        int mod = y[t];
        unordered_map<int, long long> cnt;
        long long ans = 0;

        // važno: prazni prefiks (pref[0]) doprinosi — zato cnt[0] = 1
        cnt[0] = 1;

        for (int i = 1; i <= n; ++i) {
            int r = pref[i] % mod;
            if (r < 0) r += mod; // bezbednost ako koristiš negativne vrednosti (retko potrebno)
            ans += cnt[r];
            cnt[r]++;
        }
        cout << ans << '\n';
    }
    return 0;
}

Objašnjenje koda

Računamo prefiksne sume pref[0..n] (sa pref[0]=0).
Za dati mod (tj. y[t]) pravimo mapu cnt koja pamti koliko puta je do sada viđen svaki ostatak.
Inicijalizujemo cnt[0] = 1 jer segment koji počinje od prvog elementa odgovara paru (pref[0], pref[r]).
Za svaki i dodajemo u rezultat broj prethodnih prefiksa sa istim ostatkom, pa zatim uvećavamo broj za taj ostatak.

Vremenska i memorijska složenost

Vreme: O(n) po jednom y (dakle ukupno O(n·q)).
Memorija: O(n) u najgorem slučaju (kroz mapu ostataka).
Napomena: umesto unordered_map možeš koristiti vector<long long>(mod) ako je mod dovoljno mali — to često ubrzava (izbegavanje hash-a).

3) Uobičajene greške i zamke (iz prethodna dva rešenja)

Nedostatak prefiks[0] = 0 — ako ne uključiš prazni prefiks, podsekvence koje počinju od položaja 1 neće biti prebrojane.
Izlazak van granica — prefiksne petlje moraju ići do i <= n uz indeksiranje x[i-1].
Brojanje samo slučajeva l=0 — greška kad se proverava samo da li je pref[i] % mod == 0 (to broji samo segmente koji počinju u 1. poziciji).
Neinicijalizovan pristup — ako prečitaš ili koristiš vrednosti pre nego što su učitane.

4) Mali numerički primer — korak po korak

Za niz x = [4,2,3,6,8] i mod = 4:

i	pref[i]	pref[i] % 4	cnt pre	dodato u ans	cnt posle
0	0	0	--	0	cnt[0]=1
1	4	0	cnt[0]=1	+1	cnt[0]=2
2	6	2	cnt[2]=0	+0	cnt[2]=1
3	9	1	cnt[1]=0	+0	cnt[1]=1
4	15	3	cnt[3]=0	+0	cnt[3]=1
5	23	3	cnt[3]=1	+1	cnt[3]=2

Ukupno 2 validna segmenta — poklapa se sa primerom.

5) Dodatni saveti za implementaciju

Koristi long long za prefiksne sume (zbir može rasti do n·10⁶).
Inicijalizuj mapu sa cnt[0]=1 pre prolaska kroz prefikse.
Ako su većina yᵢ mala (< 10⁶ i memorija dopušta), koristi vector umesto unordered_map radi brzine.
U slučaju veoma velikog q i ponavljajućih y, keširaj rezultate za iste y umesto da ponovo računaš.

6) Zaključak

Najvažnija transformacija je prepoznavanje da je sumu segmenta moguće izraziti kao razliku prefiksnih suma i da je uslov deljivosti ekvivalentan jednakosti ostataka modula. To omogućava prelazak sa O(n²) (naivno) na O(n) po jednom y (mapa ili vektor ostataka) — praktično i efikasno za ograničenja data u zadatku.