2. Organizácia Kapustnice vzorové riešenie

5
VTVTT

VTVTVT

6
TVVVTT

VTVTVVTT

Ľubovoľné správne riešenie

Pozrime sa najskôr na prípad, že nám netreba minimalizovať počet pridaných tort a vedúcich, ale stačí nám ľubovoľné správne riešenie. Všimnime si, že nezáleží, ako ďaleko sa vedúci pohne, aby získal tortu, ale stačí, aby nejakú získal. Taktiež, všetky torty sú rovnaké, takže nezáleží na tom, ktorú tortu zje ktorý vedúci.

Jednoduché riešenie je napríklad nasledovné: ku každému vedúcemu dáme tortu a ku každej torte dáme vedúceho (bez ohľadu na to, či by tá torta mohla byť zjedená v originálnom rozostavení, resp. či by ten vedúci nejakú tortu mohol v originálnom rozostavení zjesť). Toto riešenie vieme naprogramovať v čase \(O(n)\) s konštantnou pamäťou (stačí si nám pamätať, či je práve na rade vedúci alebo torta).

Všetky takéto riešenia budú mať tvar VTVTVT... – môžeme vidieť, že každý vedúci zje presne jednu tortu a každá torta bude zjedená.

Vzorové riešenie

Predchádzajúce riešenie je jednoduché, ale vždy pridáva \(n\) nových tort a vedúcich, a to aj vtedy, keď to netreba. Ako to zlepšiť?

Základná myšlienka je dať pred tortu vedúceho len vtedy, ak by táto torta ostala nezjedená, a dať vedúcemu tortu len vtedy, ak by žiadnu v originálnom rozostavení nedostal.

Skúsme nasimulovať, čo by sa stalo pri originálnom rozostavení vedúcich a tort. Predstavme si, že postupne prechádzame stôl zľava doprava a udržiavame si premenné \(dv\) – “doterajší počet vedúcich” a \(dt\) – “doterajší počet tort”.

Ako prvé si všimnime, že ak \(dv>=dt\), potom každá torta je zjedená. Hodnota \(dv-dt\) udáva počet ešte nenajedených vedúcich (do danej pozície na stole) (vždy, keď príde torta, počet nenajedených vedúcich sa zníži, vždy, keď príde vedúci, počet nenajedených vedúcich sa zvýši).

Podobne, ak máme také rozostavenie tort a vedúcich, že každá torta bude zjedená, tak vždy bude platiť \(dv>=dt\) (ak máme pred nejakou pozíciou viac tort ako vedúcich, všetky torty pochopiteľne nemôžu byť zjedené).

Poďme najskôr pridať vedúcich. Všimnime si, že ak pridáme \(v\) vedúcich na začiatok, potom sa počet nenajedených vedúcich (na každej pozícii) zvýši o \(v\).

Počet nezjedených tort na nejakej pozícii vieme vyrátať ako \(dt-dv\). Nech najväčšia hodnota, ktorú \(dt-dv\) v nejakom bode nadobudne, je \(nt\). To znamená, že musíme pridať určite aspoň \(nt\) vedúcich, aby nám nikdy neostali nezjedené torty. Vieme ich všetkých napríklad pridať na začiatok. Potom bude počet nezjedených tort všade zmenšený o \(nt\) a teda nikdy nám neostanú nezjedené torty. Ak by sme pridali menej než \(nt\) vedúcich, v nejakom bode by nám ostali nezjedené torty, preto toto je najlepšie, čo vieme spraviť.

Čo s tortami? Všimnime si, že ak nám nikdy neostanú nezjedené torty, hodnota \(dv-dt\) po prejdení celého vstupu je presne počet vedúcich, ktorí nedostali tortu. Nazvime túto hodnotu \(nv\). Tá nám vlastne hovorí, o koľko je pri stole viac vedúcich ako tort. Očividne musíme pridať aspoň \(nv\) tort – ak by sme pridali menej, potom by pri stole bolo menej tort ako vedúcich, takže určite nebudú všetci vedúci najedení. Taktiež si všimnime, že nám stačí pridať všetkých \(nv\) tort na koniec stola. Takto sa k nim všetci zostávajúci nenajedení vedúci určite dostanú.

Takže si to zhrňme: prejdeme postupne stôl a počítame si, koľko vedúcich a tort sme zatiaľ videli. Zapamätáme si, akú najväčší počet nezjedených toriet (\(dt-dv\)) sme videli. Ak je tento počet kladný, pridáme taký počet vedúcich na začiatok. Následne sa pozrieme, koľko nenajedených vedúcich (\(dv-dt\)) nám na konci ostalo, a pridáme k tomu počet pridaných vedúcich (\(nt\)). Toto číslo nám povie, koľko tort treba pridať na koniec. Časová aj pamäťová zložitosť je \(O(n)\), keďže raz prejdeme vstupom, a potrebujeme si ho pamätať, aby sme mohli vypísať výstup.

#!/usr/bin/env python3
n=int(input())
s=input()
z=0
o=0
for x in s:
    if x=='V':
        o+=1
    elif o:
        o-=1
    else:
        z+=1
print('V'*z+s+'T'*o)

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define FOB(i,n)	for(int i=n;i>=1;i--)
#define MP(x,y)	make_pair((x),(y))
#define ii pair<int, int>
#define lli long long int
#define ld long double
#define ulli unsigned long long int
#define lili pair<lli, lli>
#ifdef EBUG
#define DBG	if(1)
#else
#define DBG	if(0)
#endif
#define SIZE(x) int(x.size())
const int infinity = 2000000999 / 2;
const long long int inff = 4000000000000000999;

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    
    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  FOR(i, v.size()){
    if(i) out << " ";
    out << v[i];
  }
  out << endl;
  return out;
}

bool ccw(point p, point a, point b) {
  if((conj(a - p) * (b - p)).imag() <= 0) return false;
  else return true;
}

int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    
    int n = get<int>();
    string s = get<string>();
    
    int pridatL = 0;
    int act = 0;
    
    FOR(i, n) {
        if (s[i] == 'T') {
            if (act) act --;
            else pridatL ++;
        }
        else act ++;
    }
    
    FOR(i, pridatL) cout << "V";
    cout << s;
    FOR(i, act) cout << "T";
    cout << endl;
}