3. Dohrajte hru vzorové riešenie

2
1 100
2 1 10

101 10

1
9 2 8 6 5 9 4 7 1 3

30 15

3
3 1 3 2
2 8 7
3 5 4 6

18 18

Prvá sada (jedna kôpka)

Na riešenie prvej sady, kde bola iba jedna kôpka, stačilo striedavo simulovať Baklažánove a Bujove ťahy. Takéto riešenie pobehá v lineárnom čase (neskôr ukážeme, že vieme mať dokonca konštantnú pamäť).

Riešenie pre viacero kôpok

Tu je situácia podstatne ťažšia. Je veľmi veľa možností ako vie hra prebiehať a nestíhame preskúšať každú. Prvá vec, čo si treba uvedomiť je, že sa nestačí pozerať len na prvú/poslednú kartu na kôpke. Takáto karta môže mať veľmi malú hodnotu, ale môže odkryť karty, ktoré sa veľmi oplatia zobrať.

Ďalšia vec, ktorú si vieme všimnúť je, že porebujeme rozlišovať medzi 2 typmi kôpok – párnymi a nepárnymi. Zamyslime sa nad párnymi kôpkami.

Kôpky s párnym počtom kariet

Ako tu vyzerá optimálna hra? Všimnime si, že žiaden hráč nemôže získať kartu, ktorá je vo vzdialenejšej polke kôpky. Prečo?

1. Bujovi stačí ťahať z tej istej kôpky, z ktorej bral Baklažán.
2. Baklažánova stratégia je podobná. Ak Buj potiahne kartu z inej kôpky ako on, Baklažán sa prispôsobí a zoberie z tej kôpky, čo Buj.

Čo sme týmto zistili? Predstavme si, že existuje optimálne riešenie pre jedného z hráčov, s tým, že v nejakom momente zoberie kartu zo vzdialenej polky kôpky. My sme ale dokázali, že obaja hráči vedia takémuto prípadu zabrániť. To znamená, že v optimálnom riešení Baklažán získa vrchnú polku kôpky a Buj spodnú.

Kôpky s nepárnym počtom kariet

Teraz sa pozrime na nepárne kôpky. Zjavne aj tu platí tá istá stratégia, akurát, čo s kartou v prostriedku kôpky? Keď popremýšľame, vieme ukázať, že Buj nevie zabrániť Baklažánovi získať najlepšiu strednú kartu spomedzi nepárnych kôpok. Podobne, ak Baklažán túto kartu zoberie, nevie zabrániť Bujovi zobrať druhú najdrahšiu. A toto vieme zovšeobecniť – Baklažán a Buj si postupne poberú karty v nepárnych kôpkach.

Celé riešenie dokopy

Na začiatku načítame vstup, pripočítame Baklažánovi skóre za vrchné polky kôpok, Bujovi za spodné. Potom, zoberieme prostredné karty v nepárnych kôpkach, utriedime ich a striedavo rozdelíme medzi Baklažána a Buja. Časová zložitosť takéhoto riešenia je \(O(n \cdot s + n \cdot \log(n))\), pamäťová \(O(n \cdot s)\), kde \(n\) je počet kôpok a \(s\) je maximálny počet kariet v kôpke.

Ide to aj rýchlejšie a úspornejšie

V skutočnosti si vôbec nemusíme pamätať všetky kôpky. Stačí, keď ich budeme spracuvávať jednu po druhej. Párnu rovno spracujeme a z nepárnych si uložíme prostredný prvok. Tie na konci usporiadame a rozdelíme chalanom. Týmto sme zlepšili pamäťovú zložitosť z \(O(n \cdot s)\) na \(O(n + s)\) lebo máme \(s\) kariet v kôpke a môžeme dostať \(n\) nepárnych kôp.

Časovú zložitosť vieme zlepšiť usporiadaním prostredných kariet pomocou counting sortu, keďže hodnoty jednotlivých kariet sú do \(1000\). Pretože counting sort triedi v linárnom čase od počtu triedených prvkov, teda v \(O(n)\), výsledná časová zložitosť bude \(O(n \cdot s)\). Prípadne vieme spraviť tesnejší odhad – zložitosť bude lineárna od počtu všetkých kariet na vstupe. Keďže musíme vždy prečítať celý vstup, takéto riešenie má dokonca najlepšiu možnú asymptotickú zložitosť spomedzi všetkých programov riešiacich túto úlohu.

Ešte jedna finta nakoniec. Vďaka tomu, že vieme koľko kariet má každá kôpka, kôpky si nemusíme pamatať. Vieme ich spracovať postupne po kartách a pamätať si len Bujove a Baklažánove skóre. Pamäťová zložitosť bude potom \(O(n)\).

#!/usr/bin/env python3

odd, even = [], []
player1_turn = True
player1 = player2 = 0
pile_number = int(input())

for _ in range(pile_number):
    n, *pile = tuple(map(int, input().split()))
    if n % 2 == 0:
        even.append(pile)
    else:
        odd.append(pile)

for pile in even:
    n = len(pile)
    player1 += sum(pile[:n//2])
    player2 += sum(pile[n//2:])

for pile in sorted(odd, reverse=True, key=lambda x: x[len(x)//2]):
    n = len(pile)
    top, middle, bottom = pile[:n//2], pile[n//2], pile[n//2+1:]
    player1 += sum(top)
    player2 += sum(bottom)
    if player1_turn:
        player1 += middle
        player1_turn = not player1_turn
    else:
        player2 += middle
        player1_turn = not player1_turn

print(player1, player2)