3. Inotaj vzorové riešenie

3 2
k
sp
s

3

3 3
kms
ksp
fks

0

Veľmi pomalé riešenie

Na začiatok je dobré si uvedomiť, že inotaj je množina slov, čiže na poradí slov v inotaji nezáleží. Prvý spôsob riešenia, ktorý mnohým z vás mohol napadnúť je vyskúšať všetky možnosti. Postupovali by sme postupne zhora dole, čiže najprv by sme prešli riešenie zahŕňajúce všetkých \(n\) slov, potom všetky \(n-1\) slovné riešenia, \(n-2\) slovné riešenia atď. Prvé riešenie, ktoré by v aspoň jednom znaku prešlo kontrolou (t. j. súčet výskytov jedného zo znakov je aspoň polovica všetkých znakov) by bol náš inotaj a vypísali by sme počet slov ktoré obsahuje.

Toto riešenie má ale veľmi pomalú časovú zložitosť: \(O(nk2^n)\). To je zapríčinené tým, že počet všetkých podmnožín \(n\)-prvkovej množiny je \(2^n\), a pre každú takúto množinu musíme prejsť najviac \(n\) slov, každé dĺžky najviac \(k\). Pamäťová zložitosť tohto programu je \(O(nk)\).

Na čo sme prišli

Zaujímavé pozorovanie, ktoré nám s úlohou pomôže je nasledovné: niektoré slová nám “kazia” kontroly a niektoré nie. Vlastne, pre konkrétny znak \(x\), nám kontrolu, či znak \(x\) tvorí aspoň polovicu znakov inotaja, kazia slová v ktorých \(x\) tvorí menej než polovicu znakov. Mohli by sme sa teda pozrieť na jednotlivé písmená samostatne, a roztriediť si slová, podľa toho či nám kontrolu kazia, alebo nie (pre každé písmeno osobitne). Najskôr si nejako kvantifikujme “kazenie.”

Ako správne vyriešiť

Naše úvahy nás doniesli do momentu, kde sme si uvedomili, že je veľmi dôležitý pomer súčtu výskytu písmena v slove ku súčtu všetkých znakov slove. Pomer nám však dáva len zlomok, percentuálne vyjadrenie. Keby že porovnávame slová podľa toho ako veľmi sa nám oplatí ich zobrať, dlhšie slovo s pomerom pod 50% nám pokazí kontrolu viac ako kratšie slovo s rovnakým, niekedy aj horším pomerom.

Radšej si preto vypočítame, koľko výskytov písmena \(x\) je v slove nad polovicou celkového súčtu jeho znakov. Ak je pod polovicou, tento koeficient (\(c\)) bude záporný. Potom vieme písmeno po písmene pažravo brať slová s najlepšími hodnotami \(c\) čo sme si vypočítali. To sa dá implementovať pomocou funkcie sort; pre každé písmeno si zoradíme slová podľa \(c_{1}, ... c_{k}\) od najlepšieho po najhorší. Následne postupne berieme slová, kým súčet \(c_{1}, ... c_{i}\) nie je menší ako 0. Toto aplikujeme pre každé písmeno. Na výstup vypíšeme maximum slov, ktoré sme zobrali, čiže hodnotu \(i\).

Prečo to funguje

Ukážme si teraz, že ak existuje inotaj dĺžky \(L\) kde má písmeno \(x\) nadpolovičnú väčšinu výskytov, tak náš algoritmus určite nájde aspoň taký dlhý inotaj, kde bude mať písmeno \(x\) tatiež nadpolovičnú väčšinu výskytov. Predstavme si, že náš algoritmus nájde najdlhší inotaj s nadpolovičným výskytom \(x\) dĺžky \(L'\) pozostávajúci zo slov \(a_{1}, a_{2}, ... , a_{L'}\), pričom slová sme si zoradili podľa koeficientu, tak že \(a_{L}\) má najnižší koeficient (vzhľadom na písmeno \(x\)).

Predstavme si, že by existoval nejaký inotaj dĺžky \(L > L'\) pre toto písmeno, a povedzme že \(b_{1}, b_{2}, ... , b_{L'}, ... , b_{L}\) je taký inotaj, ktorý má navyše najväčší prienik¹ ako inotaj náš algoritmus našiel (slová sme zoradili podľa koeficientu tak ako predtým).

Najskôr uvažujme, čo by sa stalo ak existuje slovo \(a_i\) v nájdemom inotaji, ktoré zároveň nie je v dlhšom inotaji. Potom, keďže algoritmus berie slová od najväčšieho koeficientu kým môže, musí existovať medzi slovami dlhšieho inotaju slovo s menších koeficientom, \(b_j\). Všimnite si, že keď vymeníme slovo \(b_j\) za \(a_j\), dostaneme stále inotaj! Ale to je v rozpore s tým, ako sme dlhší inotaj vybrali. Tento prípad teda nemôže nastať.

Teda musí platiť, že všetky slová v nájdenom inotaji boli aj tomto dlhšom inotaji. Potom zoberme si prvé slovo ktoré už algoritmus nezobral do inotaju. Kvôli tomu, že sme si slová vzali pažravo, toto slovo má aspoň taký koeficient ako \(b_L\), takže jedno pridaním by sme stále získali inotaj. Ale toto je v rozpore s tým, že si už algoritmus toto slovo nezobral.

Takže ani jeden s týchto prípadov nemôže nastať, a náš algoritmus vždy nájde nejaký najdlhší inotaj.

Zložitosti

Vypočítanie koeficientov pre každé slovo pre každé písmeno trvá \(O(5nk) = O(nk)\). Utriedenie koeficientov pre každé písmeno trvá \(O(5n\log(n)) = O(n\log(n))\). Pažravé branie v usporiadaných poliach trvá \(O(5n) = O(n)\). Toto riešenie má teda celkovú časovú zložitosť \(O(nk) + O(n\log(n)) + O(n) = O(nk + n\log n)\). Ak na triedenie použijeme counting sort, časová zložitosť sa zníži na \(O(nk)\).

Pamäťová zložitosť tohto programu je \(O(nk)\).

n, k = [int(x) for x in input().split()]
v = [input() for _ in range(n)]

letters = "fkmsp"
ans = 0
for c in letters:
    benefits = [0] * n
    for i in range(n):
        benefits[i] = 2 * v[i].count(c) - len(v[i])
    benefits.sort(reverse=True)
    iter_ans, iter_sm = 0, 0
    for i in range(n):
        iter_sm += benefits[i]
        if iter_sm >= 0:
            iter_ans += 1
    ans = max(ans, iter_ans)
print(ans)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n,k;
    cin >> n >> k;
    char pismena[5] = {'f', 'k', 's', 'm', 'p'};
    int out = 0;

    vector<vector<int>> pocet
    {
        {},
        {},
        {},
        {},
        {},
    };

    string u;

    for (int w = 0; w < n; w++)
    {
        cin >> u;
        for (int i = 0; i < 5; i++)
        {
            pocet[i].push_back(0);
            for (int j = 0; j < u.size(); j++)
            {
                if (u[j]==pismena[i]) pocet[i][w]++;
                else pocet[i][w]--;
            }
        }
    }

    for (int i = 0; i < 5; i++)
    {
        sort(pocet[i].begin(),pocet[i].end());
        reverse(pocet[i].begin(),pocet[i].end());
        int h = 0, g = 0, f = 0;
        for (int j = 0; j < n; j++)
        {
            h += pocet[i][j];
            if(h<0) {
                g=1;
                f=j;
                break;
            }
        }
        if (g==0) f=n;
        out = max(out, f);
    }

    cout << out << endl;

    return 0;
}