Úlohy DomJudge

Parašutisti

4 body do 10.03.2020 10:00
2 body do 17.03.2020 10:00

4 akceptované riešenia za plný počet bodov

  • 0.07 (C#)
  • 0.42-0.51 (Java)

Hinty

  • Priamočiara simulácia pohybov by znamenala $O\left(3^T\right)$ krokov, keďže v každom okamihu sa môžeme pohnúť dvoma smermi alebo zostať na mieste, teda 3 možnosti (v okrajových prípadoch samozrejme iba 2).

  • Greedy prístup, teda chytať hneď ďalšieho nefunguje ... niekedy sa oplatí jedného nechať spadnúť, aby sme potom mohli zachrániť dvoch. Napríklad pre nižšie uvedený vstup je výhodnejšie nechať prvého spadnúť.

      4 7 2
      4 3
      5 1
      6 0
      7 1
  • Pre dynamické programovanie si potrebujeme určiť podproblém - stav v ktorom sa práve nachádzame. Stav hry je určený (viď obrázok) časom, aktuálnou pozíciou a počtom zostávajúcich životov. image.png

  • Dynamické programovanie znamená určenie vzťahu medzi jednotlivými stavmi. Nech teda $\texttt{OPT}[\texttt{cas}][\texttt{poz}][\texttt{ziv}]$ označuje maximálny počet zachránených parašutistov, ak sa v čase cas nachádzame na pozícii poz s počtom zostávajúcich životov ziv. Potom na výpočet môžeme použiť vzorec (pri DP zdola nahor, teda podľa času, pozície aj životov):

    $$ \displaystyle \texttt{OPT}[\texttt{cas}][\texttt{poz}][\texttt{ziv}] = \begin{cases} 1+\max\limits_{i=-1}^{+1}\left\{\texttt{OPT}[\texttt{cas}-1][\texttt{poz}+i][\texttt{ziv}]\right\},\\ \hspace{1cm}\text{ak v čase } \texttt{cas} \text{ pristál parašutista na pozícii } \texttt{poz} \text{ (na člne)}\\ \max\limits_{i=-1}^{+1}\left\{\texttt{OPT}[\texttt{cas}-1][\texttt{poz}+i][\texttt{ziv}+1]\right\},\\ \hspace{1cm}\text{ak pristál parašutista na inej pozícii ako } \texttt{poz} \text{ (mimo člna)}\\ \max\limits_{i=-1}^{+1}\left\{\texttt{OPT}[\texttt{cas}-1][\texttt{poz}+i][\texttt{ziv}]\right\}, \text{inak} \\ \end{cases} $$ Je to základný vzorec, ktorý platí ak v jednom čase môže pristáť iba jeden parašutista - premyslite si ako by sa dalo upraviť na všeobecné riešenie.

    Takéto riešenie by ale malo zložitosť $O(T.M.K)$, čo je stále veľa. Vieme odstrániť nejakú premennú? Alebo dokážeme zmenšiť rozsah zapamätaných hodnôt?

  • Pre nás ale nie sú zaujímavé všetky časové okamihy, ale iba tie keď dopadne nejaký parašutista ( $N << T$, teda $N$ je rádovo/oveľa menej ako $T$). Dá sa počítať iba v týchto časoch? Dá sa vypočítať, či sa dá prejsť z jednej pozície na druhú medzi dvoma zadanými časmi? Potom nám stačí ako optimum počítať $\texttt{OPT}[\texttt{par}][\texttt{ziv}]$, určujúce maximálny počet zachránených parašutistov, ak v sme práve zachránili par-tého (čo nám určuje čas aj pozíciu) a zostávajúci počet životov je ziv. To by už malo stačiť na napísanie efektívneho, riešenia akceptovaného testovacím systémom DomJudge. Pamäťová zložitosť je teda $O(N.K)$, časová je určená zložitosťou "magického" vzorca dynamického programovania ...

Hesla

4 body do 17.03.2020 10:00
2 body do 24.03.2020 10:00

Vašou úlohou je pre získaný ladiaci záznam z uvedeného programu (algoritmu Usporiadania spájaním - MergeSort) zrekonštruovať pôvodnú permutáciu n čísel.

Pre permutáciu 2 4 3 1 dá program uvedený v zadaní výstup +--+-.

Váš program teda pre vstup +--+- musí dať výstup 2 4 3 1.