Zadanie

Alžbetka má malú sestru. Jedného dňa sa Alžbetka rozhodla vyrobiť náhrdelník z korálok. Jej malá sestra pri tom samozrejme nemohla chýbať a musela jej pomôcť. Na začiatku Alžbetka navliekla na šnúrku nejaké korálky. Podľa jej sestry to však spravila úplne zle a teda musí vymeniť túto korálku za novú, a tamtú tiež…1 Veď poznáte malé sestry.

Alžbetka by bola rada, keby ten náhrdelník vyzeral aspoň trochu dobre. Napríklad aby bol symetrický. Pri všetkom tom vymieňaní korálok by teda chcela vedieť, kedy sa tak stane.

Úloha

Jednotlivé druhy korálok budeme reprezentovať malými písmenami anglickej abecedy a-z. Na začiatku dostanete popis náhrdelníka – nejaký reťazec znakov, ktorý popisuje jednotlivé korálky v náhrdelníku. Postupne v ňom budeme vymieňať korálky za iné. Po každej takejto výmene povedzte, či je daný reťazec symetrický – tj. či sa odzadu číta rovnako ako spredu.

Formát vstupu

V prvom riadku vstupu je reťazec dĺžky \(n\) (\(1 \leq n \leq 100\,000\)) – popis pôvodného náhrdelníka. V druhom riadku je číslo \(q\) (\(1 \leq q \leq 100\,000\)) – počet zmien, ktoré nastanú. Ďalších \(q\) riadkov bude obsahovať medzerou oddelené číslo a znak – pozícia korálky, ktorú treba vymeniť (číslujeme od \(0\)) a druh (písmeno), na ktorý sa má korálka zmeniť.

Formát výstupu

Na výstup vypíšte \(q\) riadkov, pričom každý bude obsahovať buď "ano" alebo "nie" (bez úvodzoviek) podľa toho, či je reťazec po danej zmene symetrický, alebo nie.

Pozor na veľkosť vstupu a výstupu. S pomalým načítavaním/vypisovaním môžete dostať hlášku "TLE - Prekročený časový limit" aj s inak rýchlym riešením.

Príklady

Input:

abcabc
3
0 c
2 a
3 c

Output:

nie
ano
nie

Po prvej zmene bude reťazec vyzerať takto: cbcabc, čo nie je symetrické. Po druhej zmene bude vyzerať takto: cbaabc, čo symetrické je. Treťou zmenou nám to sestra pokazí a reťazec opäť nebude symetrický.

Input:

ppppp
2
2 a
3 p

Output:

ano
ano

Prvou zmenou sme zmenili znak v strede; reťazec ostane symetrický. Druhou zmenou zmeníme p na p; reťazec ostane rovnaký.

  1. Áno, správne ste uhádli. Alžbetka musí vždy vyvliecť väčšinu korálok aby sa k tej “zlej” korálke vôbec dostala. A potom ich dať zase späť. Ale to v tejto úlohe vôbec nie je podstatné.↩

Prvé a najľahšie riešenie, ktoré nám napadne, je vykonávať operácie a po každej zmene skontrolovať, či je reťazec palindróm1 alebo nie. Pri kontrole možného palindrómu nás vždy2 zaujímajú dvojice znakov - prvý a posledný, druhý a predposledný, atď. Aby bol reťazec palindrómom, musia byť všetky tieto dvojice zhodné.

Keď sa pokúsime pri každej zmene prechádzať celý reťazec, zistíme, že je to príliš pomalé. Každé skontrolovanie, či je reťazec momentálne palindróm, si totiž v najhoršiom prípade (ak palindróm je) vyžaduje \(O(n)\) porovnaní znakov. Celé to teda nášmu programu môže trvať až \(O(n \times q)\), čo nestíhame.

Čo robíme navyše? Keďže sa nám vždy mení len jeden znak, nie je vôbec potrebné kontrolovať zvyšok reťazca; ten bude presne taký ako pred danou zmenou.

Pozrime sa radšej na ten znak, ktorý meníme a na jeho náprotivok. Zaujíma nás, ako sa zmenil stav dvojice: z rovnakej na rozdielnu, z rovnakej na rovnakú, z rozdielnej na rovnakú alebo z rozdielnej na rozdielnu.

Chceme teraz zistiť, kedy nastane situácia, že každá dvojica je zhodná. Na začiatku si prejdeme celý reťazec a budeme si pamätať, koľko párov sa navzájom nezhoduje. Pri každej zmene znaku toto číslo príslušne upravíme: ak sme si nejakú dvojicu pokazili, tak počet zlých párov stúpne a ak sme si dvojicu opravili, počet zlých dvojíc klesne. Treba si dať pozor, aby sme hodnotu nemenili, ak sa zmení rozdielny na rozdielny alebo rovnaký na rovnaký! Keď máme počet nezhôd \(0\), vieme, že náš reťazec je palindróm.

Načítanie a prvotné spočítanie nezhodných dvojíc nám zaberie \(O(n)\) krokov, a každú z \(q\) otázok vyriešime a odpovieme v \(O(1)\) – časová zložitosť je teda \(O(n+q)\).

V oboch riešeniach sme si museli pamätať celý reťazec, ale otázky stačilo riešit postupne, teda sme si mohli pamätať len jednu otázku naraz. To nám udáva pamäťovú zložitosť \(O(n)\).

#include<iostream>
#include<algorithm>
#include<vector>
#include<time.h>
using namespace std;

int main () {
  long long q, nesedi = 0;
  string vstup;
  cin >> vstup >> q;
  //pociatocne pocitanie nezhodnych znakov
  for (int i = 0; i < int(vstup.size() + 1) /2; i++) {
    if (vstup[i] != vstup[vstup.size() - i - 1]) {
      nesedi ++;
    }
  }
  long long index;
  char znak;
  for (int i = 0; i < q; i++) {
    cin >> index >> znak;
    //nesediaci -> sediaci
    if (vstup[index] != vstup[vstup.size() -1 - index] &&
        vstup[vstup.size() -1 - index] == znak) {
      nesedi --;
    } else {
    //sediaci -> nesediaci
      if ((vstup[index] == vstup[vstup.size() -1 - index]) &&
          (vstup[vstup.size() -1 - index] != znak) &&
          (vstup.size() - 1 - index != index)) {
        nesedi ++;
      }
    }
    vstup[index] = znak;
    if (nesedi == 0) {
      cout << "ano\n";
    } else {
      cout << "nie\n";
    }
  }
  return 0;
}

  1. Palindróm je reťazec, čo sa číta odzadu rovnako ako spredu.↩

  2. Okrem prípadu, keď je reťazec nepárnej dĺžky.↩

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.