Zadatak 3 – 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.
• Bacanje van granica — prefiksnе 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 before	added to ans	cnt after
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⁶).
• Inicializuj 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čunаš.

---

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.

---