Potyczki Algorytmiczne
Otwarty ogólnopolski konkurs programistyczny 2016
 
Google
partner
Atende
sponsor
Uniwerytet Warszawski
organizator
liczba uczestników
0
Tutorial

Tutorial - Dzielniki

Zacznijmy od dość prostego zadania:

Dana jest liczba całkowita dodatnia N nie większa niż 1018. Ile jest liczb całkowitych dodatnich, które dzielą ją bez reszty? Liczbę N można poznać, wywołując funkcję DajN()

Warto zwrócić na początku uwagę na sposób odczytywania danych wejściowych. We wszystkich zadaniach rozproszonych wejście jest podawane poprzez biblioteczkę.

Najprostsze rozwiązanie, które może nam przyjść do głowy, to sprawdzić wszystkie możliwe dzielniki d aż do pierwiastka z N oraz odpowiadające im N/d. Przykładowy kod w C++ poniżej:

 

int main() {
  long long N, ile_dzielnikow = 0;
  N = DajN();
  for (long long d = 1; d * d <= N; ++d) {
    if (N % d == 0) {
      ++ile_dzielnikow;
      if (N / d != d)
        ++ile_dzielnikow;
    }
  }
  cout << ile_dzielnikow << endl;
}

 

Zapewne nie jest to optymalne rozwiązanie tego problemu i można je przyspieszyć na wiele sposobów. My jednak skoncentrujemy się na tym, jak przyspieszyć je przez uruchomienie programu w wielu instancjach. Naturalnym pomysłem jest, by podzielić zbiór potencjalnych dzielników na części, i każdej instancji kazać przejrzeć jedną część, a następnie dodać otrzymane przez nie wyniki.

Podziału dokonamy w następujący sposób: instancja o numerze 0 otrzyma do sprawdzenia 1, 1 + liczba_instancji, 1 + 2 * liczba_instancji, ..., instancja o numerze 1 otrzyma do sprawdzenia, 2, 2 + liczba_instancji, 2 + 2 * liczba_instancji, ..., itd. Żeby to zrobić, wystarczy w powyższym kodzie zmodyfikować pętlę for:

 

  for (long long d = 1 + MyNodeId(); d * d  <= n; d += NumberOfNodes()) {

 

Musimy jeszcze połączyć znalezione wyniki częściowe w całość. Wybierzmy dowolną instancję (powiedzmy tę o numerze 0) jako punkt zbiorczy, i dodajmy kod, który wszystkie informacje zbierze w tej instacji:

 

  if (MyNodeId() > 0) {
    PutInt(0, ile_dzielnikow);
    Send(0);
  } else {  // MyNodeId == 0
    for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) {
      Receive(instancja);
      ile_dzielnikow += GetInt(instancja);
    }
    cout << ile_dzielnikow << endl;
  }
}

 

Gotowe! Ten kod, uruchomiony na 100 maszynach, działa około 100 razy szybciej niż nasz oryginalny program.

W archiwum dzielniki znajdziesz oba rozwiązania oraz przykładową bibliotekę i testy, na których możesz je uruchomić

Tutorial - Majoranta

Omówimy teraz nieco bardziej skomplikowane zadanie: majorantę.

Dany jest ciąg liczb całkowitych składający się z co najwyżej 1010 wyrazów. Należy stwierdzić, czy istnieje liczba równa ponad połowie wyrazów ciągu. k-ty element ciągu można uzyskać, wywołując funkcję DajElement(k), zadeklarowaną w pliku majoranta.h. Długość ciągu można poznać, wywołując LiczbaElementow().

Klasyczne (jednomaszynowe) rozwiązanie tego zadania opiera się na dwóch spostrzeżeniach. Po pierwsze, gdybyśmy mieli sprawdzić czy konkretna liczba X jest majorantą, to byłoby to bardzo proste - wystarczy zliczyć jej wystąpienia w ciągu. Po drugie, jeśli jakaś liczba Y jest majorantą, a w ciągu znajdziemy dwie różne liczby i je usuniemy, to w tak powstałym ciągu Y ciągle będzie majorantą (bo usunęliśmy najwyżej jedno wystąpienie Y).

Rozwiązanie (jednomaszynowe) składa się zatem z dwóch faz. W pierwszej przeglądamy ciąg i trzymamy w ręku pewną liczbę wystąpień jednej liczby. Gdy napotykamy inną liczbę, usuwamy jedno z pamiętanych wystąpień. W przeciwnym razie, dodajemy jedno wystąpienie pamiętanej liczby. Na końcu zostanie nam tylko jedna liczba (być może występująca wiele razy). Zauważmy, że jeśli ciąg w ogóle ma majorantę, to jest nim ta właśnie liczba, na mocy drugiego z naszych spostrzeżeń - wobec tego druga faza to po prostu przejrzenie całego ciągu, zliczenie wystąpień tej liczby i sprawdzenie, czy jest majorantą. Przykładowy kod w C++ poniżej:

 

int main() {
  long long N = LiczbaElementow();
  // Faza pierwsza.
  long long obecna_liczba, ile_wystapien;
  obecna_liczba = 0;
  ile_wystapien = 0;
  for (long long i = 0; i < N; ++i) {
    long long kolejna = DajElement(i);
    if (kolejna == obecna_liczba) {
      ile_wystapien += 1;
    } else {
      if (ile_wystapien > 0) {
        ile_wystapien -= 1;
      } else {
        obecna_liczba = kolejna;
        ile_wystapien = 1;
      }
    }
  }
  // Faza druga
  ile_wystapien = 0;
  for (long long i = 0; i < N; ++i) {
    if (DajElement(i) == obecna_liczba) ile_wystapien++;
  }
  if (ile_wystapien * 2 > N) {
    cout << obecna_liczba << endl;
  } else {
    cout << "Nie ma majoranty" << endl;
  }
  return 0;
}

 

Powyższy kod dla 1010 elementów będzie działał niestety zbyt wolno jak na warunki konkursowe. Przyspieszymy go zatem, uruchamiając go na wielu instancjach. Ponownie, każda instancja będzie odpowiadała tylko za fragment wejścia:

 

  ...
  long long poczatek = (MyNodeId() * N) / NumberOfNodes();
  long long koniec = ((MyNodeId() + 1) * N) / NumberOfNodes();
  for (long long i = poczatek; i < koniec; ++i) {
  ...

 

W fazie pierwszej każda instancja policzyła kandydata w swoim zbiorze. Trzeba teraz wyznaczyć wspólnego kandydata poprzez sklejenie powstałych na każdej instancji kandydatów. A zatem, na zakończenie pierwszej fazy piszemy:

 

  ...
  if (MyNodeId() > 0) {
    PutLL(0, obecna_liczba);
    PutLL(0, ile_wystapien);
    Send(0);
  } else {
    for (int i = 1; i < NumberOfNodes(); ++i) {
      int instancja = Receive(-1);
      long long otrzymana_liczba = GetLL(instancja);
      long long otrzymane_wystapienia = GetLL(instancja);
      if (otrzymana_liczba == obecna_liczba) {
        ile_wystapien += otrzymane_wystapienia;
      } else {
        if (ile_wystapien > otrzymane_wystapienia) {
          ile_wystapien -= otrzymane_wystapienia;
        } else {
          obecna_liczba = otrzymana_liczba;
          ile_wystapien = otrzymane_wystapienia - ile_wystapien;
        }
      }
    }
  }
  ...

Teraz instancja o numerze 0 zna już wytypowanego kandydata. Trzeba przekazać go wszystkim innym, zliczyć wystąpienia i zsumować je (powiedzmy, że znowu na instancji 0). Zatem faza druga przybiera postać:

  ...
  if (MyNodeId() == 0) {
    for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) {
      PutLL(instancja, obecna_liczba);
      Send(instancja);
    }
  } else {
    Receive(0);
    obecna_liczba = GetLL(0);
  }
  ile_wystapien = 0;
  for (long long i = poczatek; i < koniec; ++i) {
    if (DajElement(i) == obecna_liczba) ile_wystapien++;
  }
  if (MyNodeId() > 0) {
    PutLL(0, ile_wystapien);
    Send(0);
  } else {
    for (int i = 1; i < NumberOfNodes(); ++i) {
      int instancja = Receive(-1);
      ile_wystapien += GetLL(instancja);
    }
    if (ile_wystapien * 2 > N) {
      cout << obecna_liczba << endl;
    } else {
      cout << "Nie ma majoranty" << endl;
    }
  }
  return 0;
}

 

I już - to rozwiązanie faktycznie działa w czasie O(N / NumberOfNodes()), czyli NumberOfNodes() razy szybciej niż oryginalne rozwiązanie na pojedynczej instancji.

W archiwum majoranta znajdziesz oba rozwiązania oraz przykładową bibliotekę i testy, na których możesz je uruchomić.

Załączniki