Idi na tekst

A1 - Nz

Vremensko ograničenje Memorijsko ograničenje
1000ms 512MB

Niz koji nastane kada se iz nekog niza obrišu neki elementi se zove nz. Za dati niz \(A\) i broj \(K\) naći leksikografsko najmanji nz koji se dobija brisanjem tačno \(K\) elemenata niza \(A\).

Opis ulaza

U prvoj liniji nalaze se dva cela broja. Prvi broj, \(N\), predstavlja dužinu niza \(A\), a drugi broj je broj \(K\). U narednoj liniji se nalazi \(N\) celih brojeva koji predstavljaju elemente niza \(A\).

Opis izlaza

Ispisati \(N-K\) celih brojeva koji predstavljaju traženi nz.

Primer 1

Ulaz

4 1
4 8 6 3

Izlaz

4 6 3

Objašnjenje primera

Brisanjem jednog elementa mogu se dobiti nzovi 8 6 3, 4 6 3, 4 8 3 i 4 8 6. Nz 4 6 3 je leksikografski manji od svih ostalih.

Primer 2

Ulaz

8 3
6 0 3 1 4 2 1 7

Izlaz

0 1 2 1 7

Ograničenja

  • \(0 \leq A_i \leq 10^9\)
  • \(0 \leq K \leq N-1\)

Postoji pet podzadatka:

  • Podzadatak 1 [19 poena]: \(N \leq 400\) i \(K = 1\)
  • Podzadatak 2 [24 poena]: \(N \leq 200.000\) i \(A_i \in \{0, 1\}\)
  • Podzadatak 3 [18 poena]: \(N \leq 400\)
  • Podzadatak 4 [18 poena]: \(N \leq 200.000\) i \(A_i \leq 100\)
  • Podzadatak 5 [21 poena]: \(N \leq 500.000\)

Napomena

Kažemo da je niz \(P\) leksikografski manji od niza \(Q\) iste dužine ako važi da je \(P_i < Q_i\) za najmanje \(i\) za koje je \(P_i \neq Q_i\).

Autor Tekst i test primeri Analiza rеšenja Testiranje
Marko Savić Marko Savić Nikola Jovanović Nikola Jovanović

Potproblem 1

U prvom potproblemu je potrebno obrisati tačno jedan broj. Ako krenemo kroz niz sa leva na desno, jasno je da prvi put kada važi uslov \(A[i] > A[i+1]\) treba obrisati \(A[i]\), jer se u suprotnom sigurno dobija leksikografski veći nz. Ako uslov nikada nije zadovoljen, brišemo poslednji element niza.

Potproblem 2

U drugom potproblemu u nizu su samo jedinice i nule. Ukoliko u nizu ima barem \(N-K\) nula finalni nz će biti sastavljen isključivo od njih, pa brišemo sve jedinice i višak nula.

U suprotnom, želimo da zadržimo sve nule i onoliko jedinica koliko je neophodno (neka je taj broj \(N_1\)). Optimalno je zadržati poslednjih \(N_1\) jedinica u nizu, i finalni nz možemo odrediti prolaskom kroz niz sa desna na levo. Kao što je pomenuto, svaka nula na koju naiđemo mora da bude deo nza, kao i prvih \(N_1\) jedinica na koje naiđemo (ostale jedinice brišemo).

Potproblem 3

Treći potproblem se može rešiti na dva načina.

Prvi način

Koristićemo dinamičko programiranje. Neka je \(S(l, c)\) leksikografski najmanji nz koji se može dobiti brisanjem tačno \(c\) elemenata počevši od prefiksa originalnog niza dužine \(l\). Računamo kompletnu DP tabelu koristeći rekurentnu vezu \(S(l, c) = \min(S(l-1, c-1), S(l-1, c) + a[l-1])\), i rešenje nalazimo polazeći od \(S(N, K)\) i prateći put kroz tabelu unazad.

Računanje tabele vršimo u \(\mathcal{O}(N^3)\), pošto je za leksikografsko poređenje dva podniza naivno potrebno \(\mathcal{O}(N)\). Svakako, ovo je dovoljno dobro za treći potproblem.

Drugi način

Ovaj način, za razliku od prvog, predstavlja korak ka kompletnom rešenju, i rešenja za preostala dva podzadatka će se bazirati na njemu.

Nazovimo nz tražen u zadatku kratko optimalan nz i definišimo najlevlji optimalan nz kao optimalan nz dobijem zadržavanjem elemenata na indeksima \(I = \{i_0, i_1, \dots, i_{N-K-1}\}\) takvim da ne postoji drugi optimalan nz čiji su indeksi \(J = \{j_0, j_1, \dots, j_{N-K-1}\}\) takvi da je niz \(J\) leksikografski manji od \(I\). Drugim rečima, najlevlji optimalan nz je onaj čiji su zadržani elementi \,\,što levlje'' u originalnom nizu.

Najlevlji optimalan nz možemo odrediti na sledeći način (niz indeksiramo od nule): \(i_{-1} = -1\), \(i_r =\) \(LRMQ(i_{r-1} + 1, K+r)\), gde \(LRMQ(a, b)\) predstavlja indeks najlevljeg od svih minimalnih elemenata u intervalu \([a, b]\).

Levi kraj intervala sledi iz toga da mora važiti \(i_r > i_{r-1}\), a desni iz toga da ne smemo odabrati indeks \(i_r\) takav da do kraja niza nema dovoljno brojeva da se formira ceo nz (odatle \(K+r = N - (N - K) + r\)). Korektnost ovakvog pohlepnog pristupa sledi direktno iz definicije leksikografskog poređenja.

Koristeći ovo, uz naivnu implementaciju \(LRMQ\) koja prolazi kroz ceo interval, možemo u ukupnoj složenosti od \(\mathcal{O}(N^2)\) odrediti optimalan nz. Ovo je dovoljno samo za treći potproblem. Za naredna dva potproblema koristimo istu ideju uz bolje načine za računanje \(LRMQ\).

Potproblem 4

U četvrtom potproblemu sve vrednosti u nizu su u intervalu \([0, 100]\). Ovo dodatno ograničenje nam omogućava da rešimo \(LRMQ\) u \(\mathcal{O}(M)\) (gde je \(M\) maksimalni element u nizu). Ovo možemo uraditi na više načina.

Jedan od načina je izgradnja prefiksnih suma koje čuvaju broj pojavljivanja svake vrednosti u \([0, M]\). Konkretno gradimo matricu \(pre\) dimenzija \(N\times M\), gde je \(pre(l, v)\) broj pojavljivanja vrednosti \(v\) u prefiksu niza dužine \(l\), i računa se kao \(pre(l, v) = pre(l-1, v) + (A[l-1] == v)\).

Sada \(LRQM\) na nekom intervalu rešavamo tako što nađemo minimalnu vrednost oduzimanjem odgovarajućih vrednosti iz matrice \(pre\), a zatim pronađemo njeno prvo pojavljivanje linearnom pretragom. Budući da u narednom pozivu \(LRMQ\) krećemo od \(i_r+1\) linearna pretraga ne utiče na složenost i ukupna složenost je \(\mathcal{O}(NM)\).

Potproblem 5 (kompletno rešenje)

Naravno, u poslednjem potproblemu ovaj pristup rešavanja \(LRMQ\) ne funkcioniše. Postoje barem tri načina da se ovo reši i u pitanju su poznate metode za \(RMQ\) problem (Range Minimum Query).

Prvi način

Možemo izgraditi segmentno stablo za minimume nad nizom, uz pažljivo tretiranje jednakih vrednosti tako da se uvek preferira levlja. Ovime dobijamo \(LRMQ\) upite u \(\mathcal{O}(\log N)\), sama izgradnja stabla je \(\mathcal{O}(N\log N)\), pa je ukupna složenost \(\mathcal{O}(N\log N)\). Ovo je dovoljno za maksimalan broj poena.

Drugi način

Kad god nema izmena niza, umesto segmentnog stabla se može koristiti sparse table Sparse table je jednostavniji za implementaciju i daje odgovore na upite u konstantnom vremenu (\(\mathcal{O}(1)\)). Kako je složenost izgradnje ista kao u slučaju segmentnog stabla i u ovom slučaju dominira (\(\mathcal{O}(N \log N)\)), korišćenje ove strukture ne dovodi do ubrzanja (na nivou složenosti), ali predstavlja alternativan način za rešavanje zadatka.

Treći način

Iako su \(\mathcal{O}(N\log N)\) rešenja dovoljno dobra za svih \(100\) poena, zadatak je moguće rešiti i linearno, u složenosti \(\mathcal{O}(n)\). Ako primetimo da intervali za koje želimo \(LRMQ\) nisu ugnježdeni, tj. da su nizovi levih i desnih granica neopadajući, možemo primeniti sliding window, tj. two pointers tehniku.

U opštem slučaju, sliding window RMQ rešavamo krećući se kroz niz sa leva na desno, pritom održavajući interval koji nas interesuje. U svakom koraku potencijalno pomeramo granice tog intervala udesno, i želimo da u svakom momentu u \(\mathcal{O}(1)\) imamo minimum na tom intervalu.

U ovu svrhu održavamo ,\,listu kandidata'' (najzgodnije implementiranu kao deque). Ključna opservacija koju koristimo je da postoje elementi koji od nekog momenta nikada ne mogu biti minimalni u intervalu (konkretno, takvi elementi \(A[i]\), da unutar intervala postoji indeks \(j\) takav da je \(i < j\) i \(A[i] > A[j]\)). Važno je da stoji znak \(>\) a ne \(\geq\) jer tražimo najlevlji minimum.

Sa ovom opservacijom listu kandidata pri dodavanju novog elementa u interval (pomeranje desne granice) ažuriramo tako što izbacujemo elemente sa kraja liste dokle god su veći od novog elementa, a zatim taj novi element dodajemo na kraj. Pri izbacivanju elemenata iz intervala (pomeranje leve granice) prosto izbacujemo adekvatan broj elemenata sa početka liste.

Rezultat ovoga je da je lista kandidata sortirana neopadajuće i da je minimalni element u trenutnom intervalu uvek na početku liste, pa mu možemo pristupiti u konstantnom vremenu, i rešiti ceo zadatak u \(\mathcal{O}(n)\).

04_nz.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

int n, k;
int a[500005];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

    cin >> n >> k;
    k = n-k;
    for (int i=0; i<n; i++)
        cin >> a[i];

    set<pair<int, int>> ms;
    set<int> zivi;

    for (int i=0; i<n; i++) {
        ms.insert({a[i], i});
        zivi.insert(i);
        if (n-i-1 < k) {
            auto it = *ms.begin();
            auto it2 = zivi.find(it.second);
            cout << it.first << ' ';
            while (1) {
                int t = *it2;
                ms.erase({a[t], t});
                if (it2 == zivi.begin()) {
                    zivi.erase(t);
                    break;
                } else {
                    auto it3 = prev(it2);
                    zivi.erase(it2);
                    it2 = it3;
                }
            }
        }
    }
    cout << '\n';
}