Zadanie

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Jitke na jitka.mur@gmail.com

V jedno pekné popoludnie sa Timka vracala celá šťastná domov zo sústredenia Prasku. Nielenže bolo sústredenie skvelé, tešila sa aj z dvoch náramkov plných cukríkov všelijakých chutí, ktoré vyhrala v tombole.

Aby spravila radosť Romanovi, ktorý na sústredenie nemohol prísť, rozhodla sa, že mu vyrobí nový špeciálny náramok. Tento náramok by mal byť čo najdlhší a zároveň by malo platiť, že cukríky, z ktorých bude zložený, sa budú dať preusporiadať tak, aby tvorili podpostupnosť (pozri časť Úloha) jedného z pôvodných náramkov. A to nie je všetko! Ak cukríky znovu preusporiadame, vytvoria podpostupnosť druhého z pôvodných náramkov.

Timka, ešte nabudená zo sústredka, hneď vedela, z ktorých cukríkov má náramok pre Romana poskladať. Len čo prišla domov pustila sa do práce a aj zabudla, akú mala sama na cukríky chuť.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane popis náramkov, ktoré Timka vyhrala a vypíše náramok, ktorý Timka vyrobila pre Romana.

Pre jednoduchosť si budeme cukríky reprezentovať malými písmenami anglickej abecedy – rovnaké písmená predstavujú rovnaké cukríky. Náramok si teda vieme predstaviť ako reťazec písmen, napr. abac je náramok so štyrmi cukríkmi, kde sú prvý a tretí cukrík rovnaké.

Romanov náramok musí byť najdlhší možný. Navyše cukríky v ňom musíme vedieť preusporiadať tak, aby vytvorili podpostupnosť prvého náramku, a potom preusporiadať tak, aby vytvorili podpostupnosť druhého náramku.

Podpostupnosť reťazca dostaneme tak, že z neho vymažeme ľubovoľné znaky a zostávajúce písmená bez zmeny poradia spojíme dokopy. Napríklad nrm, ramo, naok sú podpostupnosti slova naramok, ale aaa ani kom nie sú.

Samozrejme, môže existovať viac možností ako vytvoriť náramok pre Romana, nás preto bude zaujímať lexikograficky najmenší. Teda ak by sme zobrali všetky možné prípustné najdlhšie náramky a zoradili by sme ich podľa abecedy, tento by bol prvý v poradí.

Formát vstupu

Na prvom riadku vstupu je reťazec reprezentujúci prvý Timkin náramok. Na druhom riadku je reťazec reprezentujúci druhý náramok.

Formát výstupu

Na výstup vypíšte do jediného riadku lexikograficky najmenší reťazec, ktorý tvorí najdlhší možný náramok pre Romana. V prípade, že takýto náramok neexistuje, vypíšte neda sa.

Hodnotenie

Číslo sady 1 2 3 4 5
maximálna dĺžka náramkov \(100\) \(1\,000\) \(2\,000\) \(100\,000\) \(500\,000\)

Príklady

Input:

prask
trojsten

Output:

rs

Náramok rs je podpostupnosťou náramku prask (cukríky na indexoch \(1\) a \(3\)) a aj podpostupnosťou náramku trojsten (cukríky na indexoch \(1\) a \(4\)).

Input:

krk
nos

Output:

neda sa

Timka nedokáže vyrobiť špeciálny náramok pre Romana.

Input:

hlava
aha

Output:

aah

Aj náramok haa by spĺňal požiadavky, čo sa týka dĺžky a podpostupností (v prvom náramku cukríky na indexoch \(0\), \(2\) a \(4\). V druhom náramku sa preusporiadanie aha zhoduje s cukríkmi na indexoch \(0\),\(1\) a \(2\)), no nebol by lexikograficky najmenší. Preto vypisujeme náramok aah.

Úlohou bolo zostrojiť náramok, ktorého cukríky sa skladajú z cukríkov prvého ale aj druhého Timkinho náramku. Ak sa zamyslíme nad možným počtom takých náramkov, tak zistíme, že ich je strašne veľa. Teda riešenie, ktoré by generovalo všetky možné Romanove náramky by bolo príliš pomalé už aj na prvú sadu. Tadiaľto cesta nepôjde, a musíme vymyslieť niečo iné.

Prvý nástrel

Čo keby sme skúšali zostrojovať hľadaný náramok postupne? Najprv skúsime zistiť koľkokrát môžeme použiť cukrík \(a\), potom \(b\) až po posledný typ cukríka \(z\). Kedy môžeme vo výslednom náramku pouiť cukrík \(x\)? Iba vtedy, ak sa \(x\) nachádza v oboch náramkoch.

Toto pozorovanie stačí na riešenie, ktoré funguje v prvých 3 sadách. Budeme postupne prechádzať znakmi od \(a\) po \(z\), a budeme tento znak hľadať v oboch náramkoch. Ak ho v oboch nájdeme, vypíšeme ho a vymažeme ho z oboch náramkov. Ak sa aspoň v jednom z nich nenachádza, tak skúsime ďalší znak. Časová zložitosť tohto riešenia je \(O(r \times s)\), kde \(r, s\) sú dĺžky náramkov. Zistenie, či sa znak nachádza v oboch náramkoch trvá \(O(r + s)\) a hľadať ho budeme najviac \(min(r, s)\). Dokopy to je teda \(O((r + s) \times min(r, s))\). Ak si ale povieme, že \(r > s\), tak namiesto \(O(r + s)\) vieme napísať iba \(O(r)\) (lebo \(s\) sa v zložitosti schová) a namiesto \(O(min(r, s))\) dostaneme iba \(O(s)\) a teda dokopy dostávame \(O(r \times s)\). Pamäťová zložitosť je lineárna (a bude lineárna aj v nasledujúcich riešeniach).

(V riešení si vieme pomôcť a namiesto vymazávania, vieme znaky v náramku prepisovať na hodnotu zodpovadajúcu ničomu.)

#include <bits/stdc++.h>
using namespace std;

int main() {
  // tieto prikazy sposobia rychlejsie nacitavanie
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  string prvy, druhy;
  // vsimnite si, ze mozeme nacitavat aj do viac premennych naraz
  cin >> prvy >> druhy;

  string vysledok = "";
  // vsimnime si, ze znaky (typ char) mozeme priradit do typu int
  int znak = 'a';
  while (znak <= 'z') {
    // premenne, ktore budu obsahovat poziciu znaku ktory hladame
    int i, j;

    // skusime najst znak v prvom retazci
    for (i = 0; i < prvy.size(); i++) {
      if (znak == prvy[i]) break;
    }
    // skusime najst znak v druhom retazci
    for (j = 0; j < druhy.size(); j++) {
      if (znak == druhy[j]) break;
    }

    // ak sme znak nenasli v aspon 1 retazci, tak chceme hladat dalsi
    // inak chceme prepisat pozicie kde sme nasli znak, aby sme nehladali
    // donekonecna to iste
    if (i == prvy.size() || j == druhy.size()) {
      znak++;
    } else {
      vysledok += znak;
      prvy[i] = '_';
      druhy[j] = '_';
    }
  }

  if (vysledok.size() == 0) {
    cout << "neda sa" << endl;
  } else {
    cout << vysledok << endl;
  }
}

Triedenie

Tento algoritmus by sa dal vylepšiť, ak by sme si cukríky v oboch náramkoch najprv utriedili a potom tento znak vyhľadávali binárne.

Binárne vyhľadávanie funguje tak, že máme utriedenú postupnosť, v ktorej hľadáme nejaký prvok \(x\). Pozrieme sa do stredu tejto postupnosti (označme tento prvok \(y\)). Ak \(x < y\), tak \(y\) a všetky hodnoty, ktoré sú v postupnosti od neho napravo nás nezaujímajú (lebo sú ešte väčšie). Naopak, ak \(x > y\), tak \(x\) a všetky hodnoty naľavo sú príliš malé. Keď zabudneme na zlú polovicu, ostane nám utriedená podpostupnosť polovičnej dĺžky, s ktorou vieme túto úvahu zopakovať. V každom kroku zahodíme polovicu, čo je dosť dobré a má logaritmickú zložitosť.

Ak predpokladáme, že \(r > s\) tak vyhľadanie cukríku by nám trvalo namiesto \(O(r)\) iba \(O(log(r))\). Dokopy je teda zložitosť takého algoritmu \(O(r \times log(r))\), pretože treba prvky utriediť a potom v nich logaritmicky vyhľadávať. Takéto riešenie už stačí na plný bodový zisk :)

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  string prvy, druhy;
  cin >> prvy >> druhy;

  // utriedime curiky v naramkoch podla abecedy
  sort(prvy.begin(), prvy.end());
  sort(druhy.begin(), druhy.end());

  string vysledok = "";
  int znak = 'a';
  while (znak <= 'z') {
    // skusime najst znaky v oboch naramkoch. Funkcia lower_bound spravi binarne vyhladavanie
    // a v premennych i,j budu indexy na prvy prvok, ktory je rovnaky alebo vacsi ako znak, ktory
    // hladame alebo index mimo pokial su vsetky prvky mensie
    int i = lower_bound(prvy.begin(), prvy.end(), znak) - prvy.begin();
    int j = lower_bound(druhy.begin(), druhy.end(), znak) - druhy.begin();

    if (i == prvy.size() || prvy[i] != znak || j == druhy.size() || druhy[j] != znak) {
      znak++;
    } else {
      vysledok += znak;
      prvy[i] = '_';
      druhy[j] = '_';
    }
  }

  if (vysledok.size() == 0) {
    cout << "neda sa" << endl;
  } else {
    cout << vysledok << endl;
  }
}

Vzorové riešenie

Vzorové riešenie je ale efektívnejšie a aj jednoduchšie na naprogramovanie. Celá idea spočíva v tom, že nepotrebujeme znaky v náramkoch vôbec hľadať. Nás zaujímajú iba ich počty. Ak si spočítame, koľko je každého písmenka v oboch náramkoch, tak potom stačí postupne prechádzať písmenkami a vo výslednom náramku môžeme použiť písmeno \(x\) práve \(min(P1[x], P2[x])\), kde \(P1[x]\) a \(P2[x]\) sú počty písmen \(x\) v prvom a druhom náramku.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  string prvy, druhy;
  cin >> prvy >> druhy;

  // vyuzijeme, ze znaky a...z maju hodnoty 97...122
  int znakyPrvy[150], znakyDruhy[150];
  // netreba zabudnut nastavit vsetky hodnoty na 0
  for (int i = 0; i < 150; i++) znakyPrvy[i] = znakyDruhy[i] = 0;

  // spocitame pocty znakov
  for (int i = 0; i < prvy.size(); i++) znakyPrvy[prvy[i]]++;
  for (int j = 0; j < druhy.size(); j++) znakyDruhy[druhy[j]]++;

  bool vypisal = false;
  for (int znak = 'a'; znak <= 'z'; znak++) {
    int pocet = min(znakyPrvy[znak], znakyDruhy[znak]);
    if (pocet != 0) {
      // premennu znak musime pretypovat na char, lebo inak by sme
      // vypisali cislo (napr. namiesto znaku 'a' by sa vypisalo 97) 
      for (int i = 0; i < pocet; i++) cout << (char) znak;
      vypisal = true;
    }
  }

  if (!vypisal) cout << "neda sa" << endl;
  else cout << endl;
}

Riešenie v Pythone založené na rovnakej myšlienke vyžaduje znalosť funkcií ord a chr.

prvy = str(input())
druhy = str(input())

# vytvorime pole dvojic, pricom prva hodnota z dvojice bude
# pocitat pocet znakov v prvom retazci a druha v druhom
pocty_znakov = [[0] * 2 for pismeno in range(26)]
vypisal = False

# v pythone, je sa znak neda priradit do cisla a musime
# pouzit funkciu ord, ktora vrati ciselnu hodnotu pismenka
for pismeno in prvy:
  pocty_znakov[ord(pismeno) - ord('a')][0] += 1
for pismeno in druhy:
  pocty_znakov[ord(pismeno) - ord('a')][1] += 1

for index, dvojica in enumerate(pocty_znakov):
  for i in range(min(dvojica[0], dvojica[1])):
    # funkcia chr je opak funkcie ord a vrati z hodnoty znaku znak 
    print(chr(index + ord('a')), end='')
    vypisal = True

if vypisal:
  print()
else:
  print('neda sa')

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ť.