Domácí kolo

B: Ponožky

Řešení (Zadání úlohy)

Prvním řešením, které nás u této úlohy napadne, je postupovat přesně tak, jak je popsané v zadání. Hromadu ponožek si uložíme do nějakého pole (seznamu). Následně budeme vždy porovnávat dvojice ponožek, dokud nenajdeme dvě stejně barevné, které bychom mohli odebrat. Můžeme třeba porovnávat první ponožku s každou další. Když najdeme další stejně barevnou ponožku, obě odebereme a začneme znovu porovnávat novou první ponožku v seznamu (ta byla dříve druhá) s každou další. Pokud by náhodou první ponožka byla lichá a žádnou stejnou jsme nenašli, můžeme pokračovat porovnáváním druhé ponožky s každou další atd. Časová složitost tohoto algoritmu je kvadratická, protože v nejhorším případě můžeme porovnáme každou dvojici ponožek, kterých je řádově N2.

Pojďme se nyní podívat na lepší řešení. Využijeme toho, že barev ponožek je málo. Navíc všechny ponožky stejné barvy jsou pro nás stejné, proto nám stačí znát jejich počet. Uděláme tedy to, že si vytvoříme pole velikosti K, ve kterém si budeme počítat počty ponožek každé barvy. (Pozn.: Protože ve většině programovacích jazyků se pole indexují od nuly, je v praxi jednodušší mít pole velikosti K + 1, aby v něm byl i index K) Spočtení tohoto pole nám zabere čas O(N), protože víme, že barvy nabývají pouze hodnot 1 až K, a tedy jimi můžeme přímo indexovat položky v poli. Započtení ponožky s barvou b tedy znamená zvětšení b-té hodnoty v poli o 1.

V druhém kroku algoritmu už jen spočítáme liché ponožky. Je zřejmé, že pokud máme sudý počet ponožek od jedné barvy, můžeme je snadno popárovat, a tedy žádná lichá ponožka nám nezbyde. Naopak pokud od nějaké barvy máme lichý počet ponožek, pak nejlepší, co můžeme udělat, je popárovat všechny až na jednu, a tedy nám zbyde jedna lichá. Pro každou barvu tedy snadno spočítáme počet lichých ponožek jako zbytek po dělení počtu ponožek té barvy dvěma (sudé číslo má zbytek nula, liché číslo jedna). Zbytek po dělení (operátor modulo) se ve většině programovacích jazyků zapisuje pomocí %.

Celkový výsledek získáme jako součet počtů lichých ponožek od všech barev. Druhá část algoritmu zabere čas O(K), protože máme jen K barev. Celková složitost algoritmu je tedy O(N + K), ale protože ze zadání víme, že K je řádově menší než N, můžeme říct, že celková složitost algoritmu je lineární vzhledem k počtu ponožek.

Ještě se hodí doplnit, že pokud bychom měli barvy ponožek zadané jinak (například slovy) a nebo čísly, která by nebyla takto hezky omezená, musíme algoritmus trochu upravit. Nemohli bychom totiž mít pole indexované přímo barvami. Ale úprava není těžká, stačí místo pole použít hešovací tabulku.

Ukázkový program (Python3)

def solve():
    # načteme N a K ze vstupu
    N,K = [int(i) for i in input().split()]
    # připravíme pole pro počty ponožek
    pocty_barev = [0] * (K + 1)
    # načteme barvy ze vstupu
    vstup = [int(i) for i in input().split()]
    # spočítáme počty ponožek každé barvy
    for b in vstup:
        pocty_barev[b] += 1 
    vysledek = 0
    # pro každou barvu od 1 do K
    for k in range(1, K+1):
        # spočítáme zbytek po dělení počtu ponožek
        # dvěma a přičteme ho k výsledku
        vysledek += pocty_barev[k] % 2
    # vypíšeme výsledek
    print(vysledek)

T = int(input())
for t in range(T):
    solve()

Ukázkový program (C++)

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

void solve(){
    unsigned N, K;
    cin << N;
    cin << K;
    vector<unsigned> counts(K + 1);

    for (unsigned i = 0; i < N; i++)
    {
        unsigned color;
        cin >> color;
        counts[color]++;
    }
    
    unsigned result = 0;
    for (unsigned i = 1; i <= K; i++)
    {
        result += counts[i] % 2;
    }

    cout << result << endl;
}

int main(){
    int T;
    cin >> T;
    while(T--)
        solve();
    return 0;
}

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)