Domácí kolo

F: Sedmikráska

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

  • Nápad: Roman Sobkuliak
  • Příprava: Vašek Rozhoň
  • Testování: Vašek Volhejn

Nejprve si zaveďme užitečnou notaci. Je-li na pozici i číslo a_i, definujeme funkci f tak, že f(i) = i + a_i, případně f(i) = i + a_i - N, pokud i + a_i > N. Jinými slovy, funkce f nám říká, že pokud se díváme na i-tý lísteček a začneme od něj trhat, v příštím kroku se budeme dívat na lísteček f(i).

Úloha se nás vlastně ptá, zda existuje nějaké i takové, že když budeme postupně skákat kolem sedmikrásky z i do f(i), odtud do f(f(i)) atd., tak po jednom obskákání celé sedmikrásky skončíme opět přesně v i.

Lehká verze

Lehkou verzi šlo vyřešit jednoduchou simulací: pro každé i začneme aplikovat funkci f a děláme to tak dlouho, dokud jednou neobskáčeme celou sedmikrásku. Pak jen zkontrolujeme, zda jsme skončili v indexu i, či jsme jej přeskočili. Máme N různých indexů, které je třeba zkontrolovat, a čas na kontrolu jednoho indexu je \mathcal O(N). Celková časová složitost je tedy kvadratická \mathcal O(N^2).

Těžká verze

Pro těžkou verzi si nejprve rozmysleme, že problém, který řešíme, má dva aspekty. Za prvé chceme pro každý počáteční index i zjistit, zda platí, že začneme-li skákat z i pomocí f kolem sedmikrásky, dostaneme se po nějaké době zpět do i. Pokud se to stane, řekneme, že i leží na cyklu tvořeném lístečky i, f(i), f\left(f(i)\right), \dots, i. Pokud i leží na cyklu, zajímá nás dále, kolikrát tento cyklus obskákal sedmikrásku. Chceme, aby bylo potřeba obskákat sedmikrásku jen jednou.

Kdyby nám stačilo pro každý index i zjistit, zda leží na cyklu, mohli bychom to udělat následovně: začneme skákat z i kolem sedmikrásky pomocí funkce f a skáčeme tak dlouho, dokud poprvé neskončíme na lístečku, na kterém jsme již jednou byli. Jedná-li se o lísteček i, pak i leží na cyklu. Na druhou stranu, pokud se jedná o jiný lísteček j, pak je jasné, že na i se již nikdy nedostaneme, budeme se totiž točit v kruhu tvořeném lístečky j, f(j) atd. Všimni si, že teď už známe odpověď nejen pro lísteček i, ale i pro všechny ostatní lístečky, které jsme cestou navštívili. Lístečky, které jsme objevili mezi prvním a druhým navštívením j, určitě leží na cyklu j, f(j), f\left(f(j)\right), \dots, j. Lístečky navštívené mezi i a j naopak na cyklu neleží.

Nás navíc zajímá, zda cyklus, který jsme takto objevili, odpovídá pouze jednomu, nebo vícero obskákání sedmikrásky. To se dá jednoduše zjistit, jestliže si během skákání pamatujeme v pomocném poli, kolik lístečků jsme již obskákali. Máme tedy algoritmus, který začne na nějakém lístečku i a skáče tak dlouho, než nalezne nějaký cyklus, pro který zkontroluje, zda odpovídá jednomu obskákání sedmikrásky.

Tento algoritmus můžeme postupně opakovat pro všechny lístečky s tím, že jakmile během skákání narazíme na lísteček, který jsme již navštívili dříve, můžeme skončit, protože další skákání by pouze objevilo cyklus, který jsme již zkontrolovali.

Protože v našem algoritmu každý skok z i do f(i) provedeme maximálně jednou, je výsledná složitost lineární, tedy \mathcal O(N).

Kód (C++)

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int T; // počet problémů, které musíme vyřešit
  cin >> T;

  for (int t = 0; t < T; ++t) {
    int N; // počet okvětních lístků
    cin >> N;
    vector < int > a(N, 0); // pole s délkami skoků
    vector < int > navstiveno(N, -1); // v které iteraci jsme lístek navštívili
    vector < int > delka(N, -1); // kolik lístečků jsme obskákali, než jsme se dostali na danou pozici

    for (int i = 0; i < N; ++i) {
      cin >> a[i];
    }

    bool ans = false;
    for (int i = 0; i < N; ++i) { // začneme skákat z pozice i
      if (navstiveno[i] != -1) { // pokud jsme již lístek navštívili, nepokračujeme
        continue;
      }
      int p = i; // aktuální pozice
      int l = 0; // počet obskákaných lístečků

      while (navstiveno[p] == -1) { // dokud se nezacyklíme
        navstiveno[p] = i; // navštíme pozici p v iteraci i po l obskákaných lístečcích
        delka[p] = l;

        p += a[p]; // skočíme na další lístek
        p %= N;
        l += a[p];
      }

      if (navstiveno[p] == i && delka[p] + N == l) { // hledáme cyklus, který odpovídá jednomu obskákání sedmikrásky
        ans = true;
        break;
      }
    }

    if (ans == true) {
      cout << "ANO" << endl;
    } else {
      cout << "NE" << endl;
    }
  }
}

Máš na to!

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