1. Kopa kopania vzorové riešenie

Zadanie

Cisár Vespazián poveril staviteľa Oryctolaga veľkou úlohou: postaviť najväčší amfiteáter na svete.

Na veľkom amfiteátri je veľa roboty. Na začiatok treba, napríklad, pripraviť veľkú, rovnú stavebnú plochu. Ako na potvoru je však jediná veľká voľná plocha v okolí nerovná. Preto neostáva nič iné, ako ju umelo vyrovnať.

Na stavebnej ploche sú dva druhy nerovností, kopce a jamy, všetky rovnako veľké. Ak je teda nejaký kopec vedľa jamy, dá sa ich oboch veľmi jednoducho zbaviť – hlinou z kopca zasypeme jamu. Nie pri každom kopci je však jama, preto sa Oryctolagus bojí, že mu na konci nejaké nerovnosti zostanú.

Oryctolagus bude, samozrejme, jamy zasypávať najlepším možným spôsobom (teda tak, aby mu na konci zostalo čo najmenej nerovností). Zaujímalo by ho, koľko nerovností mu na konci zostane. Keďže sa mu to nechce počítať, zveril túto robotu svojej pravej ruke, Angelice. Tá to zasa zverila vám. A vy, ak budete šikovní, to môžete zveriť svojmu počítaču.

Úloha

Pre jednoduchosť budeme v tejto úlohe predpokladať, že svet je dvojrozmerný (má iba výšku a šírku) a stavebný pozemok má pôdorys v tvare úsečky. Pozdĺž tejto úsečky je niekoľko nerovností (jám a kopcov). Počet týchto nerovností aj ich poradie dostanete na vstupe. Máme povolené robiť nasledovnú operáciu:

• Ak medzi nejakou jamou a kopcom nie je žiadna iná nerovnosť (jama ani kopec), môžeme dať zasypať jamu hlinou z kopca. Daná jama aj kopec pri tom zaniknú.

Zistite, koľko nerovností nám ostane, ak pomocou tejto operácie odstránime najviac jám a kopcov, ako sa dá.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) (\(1 \leq n \leq 200\,000\)) – počet nerovností.

Na druhom riadku sa nachádza reťazec núl a jednotiek dlhý \(n\). Tento reťazec popisuje nerovnosti v poradí od začiatku po koniec pozemku: nuly znamenajú jamy a jednotky znamenajú kopce.

Formát výstupu

Na jediný riadok výstupu vypíšte najmenší možný počet nerovností, ktoré na konci zostanú.

Príklady

Input:

4
1100

Output:

0

Najprv zasypeme ľavú jamu hlinou z pravého kopca. To nám otvorí cestu, aby sme zasypali druhú jamu hlinou zo zostávajúceho kopca.

Input:

5
01010

Output:

1

Jedným z možných postupov je:

Input:

6
111111

Output:

6

V tomto prípade sa nedá vyrovnať nič.

Na začiatok si uvedomme nasledovnú myšlienku: Kým bude na stavebnej ploche aspoň jedna jama a zároveň aspoň jeden kopec, určite budeme vedieť niečo ešte zarovnať.

Inými slovami, ak je na pozemku aspoň jedna jama a aspoň jeden kopec, tak je tam aj taká jama a taký kopec, medzi ktorými nie je žiadna iná nerovnosť.

Aj keď sa takéto tvrdenie môže zdať zrejmé, skúsme ho poriadne dokázať. Predpokladajme teda, že na pozemku je ešte aspoň jedna jama a aspoň jeden kopec. Zoberme si najľavejší kopec. Ak je bezprostredne naľavo od neho jama, tak sme práve našli hľadanú dvojicu. Ak naľavo od neho nie je jama, tak to znamená, že tento kopec je prvá nerovnosť na pozemku (lebo je to najľavejší kopec). Ak teraz budeme prechádzať postupne po pozemku smerom doprava, stretávame najprv kopce (možno len ten jeden najľavejší, možno aj ďalšie), až kým nestretneme jamu (na pozemku sa aspoň jedna musí nachádzať). Táto jama je však vedľa posledného kopca, ktorý sme videli, teda aj v tomto prípade sme našli susediacu dvojicu kopec-jama.

Zistili sme, že stavebnú plochu budeme vedieť zarovnávať, až kým nám neostanú samé kopce alebo samé jamy (prípadne ani jedno). Zároveň vieme, že pri každom zarovnaní zmizne jedna jama a jeden kopec. Počet nerovností, ktorý ostane na konci, bude preto rovný rozdielu medzi počtom kopcov a počtom jám na začiatku.

Lepší výsledok sa zjavne dosiahnuť nedá – ak máme priveľa jám, môžeme ich zasypať iba toľko, koľko máme kopcov. Podobne, ak máme priveľa kopcov, môžeme sa zbaviť iba toľkých, koľko máme jám.

Na vyriešenie úlohy nám teda stačí spočítať, koľko je na pozemku jám a koľko kopcov (koľko je vo vstupnom reťazci núl a koľko jednotiek), odčítať od väčšieho čísla menšie a výsledok vypísať.

Priamočiara implementácia popísaného algoritmu v Pythone:

n = int(input())
retazec = input()

# rozdiel poctu kopcov a jam
rozdiel = 0

for i in range(n):
    # za kazdu jamu jednotku odpocitame
    if retazec[i] == '0':
        rozdiel -= 1
    # za kazdy kopec jednotku pripocitame
    else:
        rozdiel += 1

# ak bolo viac jam ako kopcov, bude rozdiel zaporny,
# preto vypiseme jeho absolutnu hodnotu
print(abs(rozdiel))

Už na načítanie vstupu je potrebná časová zložitosť \(O(n)\) a v našom riešení len v jednom cykle prejdeme pole so vstupom, preto aj celé riešenie má zložitosť \(O(n)\). Pamäťová zložitosť je, naopak, niečo, s čím pohnúť vieme. Ak načítame celý reťazec naraz, naša pamäťová zložitosť bude \(O(n)\). Reťazec si ale nepotrebujeme pamätať celý naraz. Ak budeme vstup načítavať po jednom znaku, zlepšíme pamäťovú zložitosť na \(O(1)\).

Tu uvádzame riešenie v jazyku C++ s konštantnou pamäťovou zložitosťou:

#include <iostream>
#include <cmath> // na absolutnu hodnotu

using namespace std;

int main() {
  // dlzka retazca a rozdiel poctu kopcov a jam
  int n, rozdiel = 0;
  cin >> n;

  for (int i = 0; i < n; i++) {
    char znak;
    cin >> znak;
    if (znak == '0') {
        // za kazdu jamu jednotku odpocitame
        rozdiel -= 1;
    } else {
        // za kazdy kopec jednotku pripocitame
        rozdiel += 1;
    }
  }
  // ak bolo viac jam ako kopcov, bude rozdiel zaporny,
  // preto vypiseme jeho absolutnu hodnotu
  cout << abs(rozdiel) << endl;
}