Idi na tekst

5 - 01 niz

Vremensko ograničenje Memorijsko ograničenje
2000ms 256MB

\(N\) novčića poređano je u niz. Svaki novčić ima broj \(0\) napisan na jednoj strani i broj \(1\) na drugoj. Tačno jedna strana svakog novčića je vidljiva. String \(S\) predstavlja vidljive cifre novčića pročitane od početka do kraja niza. Nad ovim nizom novčića treba izvršiti \(Q\) promena, gde je \(i\)-ta promena opisana sa dva broja \(L_i\) i \(R_i\), što znači da je potrebno okrenuti sve novčiće na podnizu od \(L_i\) do \(R_i\).

Na primer ako je \(S=0101101\), \(L_1=2\) i \(R_1=6\) posle prve promene \(S=0010011\).

Posle svake promene ispisati najmanju moguću ukupnu cenu da se svi novčići okrenu tako da im je broj 0 na vidljivoj strani, ako je moguće primenjivati sledeće dve operacije prizvoljan broj puta u proizvoljnom redosledu: - Okreni jedan novčić za cenu \(1\). - Okreni sve novčiće na nekom podnizu uzastopnih novčića za cenu \(C\).

Obratite pažnju na to da se samo \(Q\) zadatih promena zapravo primenjuje na niz, dok se operacije kojima bismo okrenuli sve novčiće tako da im je \(0\) na vidljivoj strani, ne primenjuju na niz novčića, već je samo potrebno naći njihovu najmanju moguću ukupnu cenu.

Opis ulaza

U prvom redu ulaza nalaze se 3 cela broja \(N\), \(C\) i \(Q\). U sledećem redu nalazi se string \(S\). U narednih \(Q\) redova nalaze se po 2 cela broja \(L_i\) i \(R_i\).

Opis izlaza

Na izlaz ispišite \(Q\) redova, u \(i\)-tom redu traženu najmanju cenu posle \(i\)-te promene.

Ograničenja

  • \(1 \leq C \leq N \leq 2 \times 10^5\)
  • \(1 \leq Q \leq 2 \times 10^5\)
  • \(1 \leq L_i \leq R_i \leq N\)
  • \(|S|=N\)
  • String \(S\) se sastoji samo od cifara \(0\) i \(1\).

Test primeri su podeljeni u 9 disjunktnih grupa:

  • U test primerima vrednim \(2\) poena: \(N, Q \leq 4000\), \(C=N\)
  • U test primerima vrednim \(2\) poena: \(L_i=R_i\) za svako \(i\), \(C=N\)
  • U test primerima vrednim \(12\) poena: \(C=N\)
  • U test primerima vrednim \(4\) poena: \(N, Q \leq 4000\), \(C=1\)
  • U test primerima vrednim \(6\) poena: \(C=1\)
  • U test primerima vrednim \(8\) poena: \(N \leq 1000\), \(Q=1\)
  • U test primerima vrednim \(18\) poena: \(Q=1\)
  • U test primerima vrednim \(20\) poena: \(L_i=R_i\) za svako \(i\)
  • U test primerima vrednim \(28\) poena: nema dodatnih ograničenja

Primeri

Primer 1

Ulaz

7 2 3
0111011
1 2
1 2
2 6

Izlaz

4
3
2

Objašnjenje

  • Posle prve pomene \(S=1011011\) i optimalno je okrenuti ceo niz novčića za cenu \(2\) i zatim okrenuti drugi i peti novčić. Ukupna cena je \(2+1*2=4\).
  • Posle druge promene \(S=0111011\) i optimalno je okrenuti novčiće od drugog do poslednjeg za cenu \(2\) i zatim okrenuti peti novčić. Ukupna cena je \(2+1=3\).
  • Posle treće promene \(S=0000101\) i optimalno je okrenuti peti i sedmi novčić. Ukupna cena je \(1+1=2\).

Primer 2

Ulaz

16 3 5
0111001111011001
16 16
1 1
3 3
5 5
7 7

Izlaz

6
6
7
6
7
Autor Tekst i test primeri Analiza rеšenja Testiranje
Tadija Šebez Tadija Šebez Tadija Šebez Aleksa Milisavljević

Rešenje kada je \(C=N\)

Ne isplati se okretati podnizove novčića za cenu \(C\) jer možemo pojedinačno da ih okrenemo za manju ili jednaku cenu. Rešenje se svodi na najmanji broj okretanja po jednog onovčića tako da se dobiju sve nule. Nema razloga da ikada okrenemo novčić na kom je 0, a svaki novčić na kom je 1 okrećemo po jednom, odnosno rešenje je broj jedinica u nizu. Za 2 poena možemo posle svake promene da prođemo kroz niz i prebrojimo jedinice. Vremenska složenost je \(O(QN)\). Za 4 poena treba da primetimo da se posle svake promene za koju je \(L_i=R_i\) menja tačno jedan novčić u nizu pa možemo lako da izračunamo za koliko se promenio broj jedinica posmatrajući samo taj novčić. Vremenska složenost je \(O(N+Q)\). Za 16 poena treba da izračunavamo broj jedinica pomoću segmentnog stabla sa lenjom propagacijom. Vremenska složenost je \(O(QlogN)\).

Rešenje kada je \(C=1\)

Možemo da okrećemo podnizove za istu cenu kao i pojedinačne novčiće, tako da je rešenje najmanji broj okretanja podnizova tako da dobijemo sve nule. Zamislimo da smo na početak i kraj niza dodali po jedan novčić sa nulom na vidljivoj strani. Prebrojmo sve parove susednih novčića tako da su im različiti brojevi na vidljivim stranama. Ako je ovaj broj 0 u nizu su sve nule. Okretanje podniza menja stanje tačno 2 od pomenutih parova i za svaka dva para postoji podniz koji menja njihova stanja. Zato je rešenje broj parova susednih novčića čiji su vidljivi brojevi različiti podeljen sa 2. Ako se ovo prebrojavanje radi prolaskom kroz ceo niz posle svake promene dobija se 4 poena. Vremenska složenost je \(O(QN)\). Već znamo da svaka promena menja stanje tačno dva para pa ako to iskoristimo možemo lako da nađemo za koliko se promenio broj parova koje brojimo. Ovo rešenje je vremenske složenosti \(O(N+Q)\) i nosi 10 poena.

Rešenje kada je \(Q=1\)

Ovaj slučaj možemo da rešimo dinamičkim programiranjem. Potrebna nam je sledeća opservacija. U nekom od optimalnih rešenja, obrnućemo neke disjunktne podnizove i zatim sve jedinice pojedinačno. Neka je \(dp_i\) minimalna cena za prvih \(i\) novčića. Poslednji novčić može biti obrnut za cenu \(C\) sa nekim podnizom ili ne, pa je \(dp_i = max(dp_{i-1} + S_i, max_{j=1}^i(dp_{j-1} + C + broj_nula(j,i)))\). Ovo rešenje je vremenske složenosti \(O(N^2)\) i nosi 8 poena. Za 26 poena potrebno je rešenje u boljoj vremenskoj složenosti. Neka je \(dp_{i, 0}\) rešenje za prvih \(i\) novčića ako \(i\)-ti novčić nije bio obrnut kao član podniza, a \(dp_{i, 1}\) rešenje ako jeste. Onda je \(dp_{i, 0}=max(dp_{i-1, 0}, dp_{i-1, 1})+S_i\) i \(dp_{i, 1}=max(dp_{i-1, 0}+C, dp_{i-1, 1})+(1-S_i)\). Ovo rešenje je vremenske složenosti \(O(N)\).

Rešenje kada je \(L_i=R_i\)

Ako bismo \(Q\) puta iskoristili rešenje za \(Q=1\) dobili bismo rešenje u vremenskoj složenosti \(O(NQ)\) što je previše sporo za ovaj podzadatak. Ipak treba da primetimo da veliki deo niza ostaje isti i da to treba nekako da iskoristimo. Možemo da napravimo segmentno stablno nad nizom novčića i da u svakom čvoru čuvamo neke \(dp\) vrednosti. Za svaki segment čuvamo 4 rešenja \(dp_{l,r}\), gde je \(l=1\) ako je prvi novčić bio obrnut kao član podniza i \(r=1\) ako je poslednji novčić bio obrnut kao član podniza. Sa ovim informacijama možemo da spojimo \(dp\) vrednosti za dva podniza i rešenje zadatka će biti u korenu segmentnog stabla. Vremenska složenost ovog rešenja je \(O(QlogN)\).

Rešenje za 100 poena

Za svih 100 poena potrebno je da na segmentnom stablu primenomo lazy propagation tehniku. Za svaki čvor čuvaćemo \(dp\) vrednosti za segment i \(dp\) vrednosti za segment ako bismo obrnuli sve novčiće na njemu. Kada treba da obrnemo podniz, zamenićemo ove \(dp\) vrednosti za neke segmente i obrnuti njihove lazy tagove. Vremenska složenost ostaje \(O(QlogN)\).

05_01_niz.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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

const int N=200050;
const int M=2*N;
const int inf=1e9+7;

int ls[M],rs[M],tsz,root;
int dp[M][2][2][2],lzy[M];

char s[N];
int C;
void init(int c){for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)dp[c][i][j][k]=inf;}
void pull(int c){
    for(int t=0;t<2;t++){
        for(int l=0;l<2;l++){
            for(int r=0;r<2;r++){
                dp[c][t][l][r]=inf;
                for(int a=0;a<2;a++){
                    for(int b=0;b<2;b++){
                        dp[c][t][l][r]=min(dp[c][t][l][r],dp[ls[c]][t][l][a]+dp[rs[c]][t][b][r]+(a==1&&b==1?-C:0));
                    }
                }
            }
        }
    }
}

void Flip(int c){
    for(int i=0;i<2;i++)for(int j=0;j<2;j++)swap(dp[c][0][i][j],dp[c][1][i][j]);
    lzy[c]^=1;
}

void push(int c){
    if(lzy[c]){
        Flip(ls[c]);
        Flip(rs[c]);
        lzy[c]=0;
    }
}

void Build(int&c,int ss,int se){
    c=++tsz;init(c);
    if(ss==se){
        if(s[ss]=='1'){
            dp[c][0][0][0]=1;
            dp[c][0][1][1]=C;
            dp[c][1][0][0]=0;
            dp[c][1][1][1]=C+1;
        }else{
            dp[c][0][0][0]=0;
            dp[c][0][1][1]=C+1;
            dp[c][1][0][0]=1;
            dp[c][1][1][1]=C;
        }
        return;
    }
    int mid=ss+se>>1;
    Build(ls[c],ss,mid);
    Build(rs[c],mid+1,se);
    pull(c);
}

void Flip(int c,int ss,int se,int qs,int qe){
    if(qs>qe||qs>se||ss>qe)return;
    if(qs<=ss&&qe>=se){Flip(c);return;}
    int mid=ss+se>>1;
    push(c);
    Flip(ls[c],ss,mid,qs,qe);
    Flip(rs[c],mid+1,se,qs,qe);
    pull(c);
}

int Ans(){return min({dp[root][0][0][0],dp[root][0][0][1],dp[root][0][1][0],dp[root][0][1][1]});}

int main(){
    int n,q;
    scanf("%i %i %i",&n,&C,&q);
    assert(1<=n && n<=200000);
    assert(1<=C && C<=200000);
    assert(1<=q && q<=200000);

    scanf("%s",s+1);
    assert(strlen(s+1)==n);
    for(int i=1;i<=n;i++)assert(s[i]=='0' || s[i]=='1');

    Build(root,1,n);

    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%i %i",&l,&r);
        assert(1<=l && l<=r && r<=n);
        Flip(root,1,n,l,r);
        printf("%i\n",Ans());
    }
    return 0;
}