Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PLGCOL - Spotkania towarzyskie

Zgodnie z niepisaną tradycją Politechniki Bajtlandzkiej (PB) każdy ze studentów raz w roku powinien zorganizować Spotkanie Towarzyskie ku Uciesze Braci Studenckiej (STUBS). STUBS mają nieformalny charakter i cieszą się dużą popularnością. Organizowanie i uczestnictwo w STUBS pochłania wiele czasu i energii społeczności PB, gdyż przygotowanie udanego STUBS dla licznego grona przyjaciół i znajomych znakomicie podnosi prestiż towarzyski żaka.

Początkowo, gdy idea STUBS nie była jeszcze tak popularna, organizowano je całkowicie spontanicznie. W kolejnych latach okazało się, że konieczne są pewne uregulowania, powołano nawet Studencki Komitet Nadzoru nad STUBS (SKNS).

Obecnie SKNS przygotowuje harmonogram STUBS na kolejny rok akademicki. Nie jest to zadanie łatwe, gdyż należy wziąć pod uwagę szereg kryteriów. W tym miejscu należy się kilka słów wyjaśnienia. Otóż, każdy przedstawiciel Braci Studenckiej PB surowo przestrzega lojalności wobec swoich ezer. Nie wnikając w bliższe szczegóły rytuałów PB wystarczy powiedzieć, że jeśli student zorganizuje konkurencyjne STUBS w tym samym terminie co jej (jego) ezer, to jest to obraza i powód długotrwałych waśni (w przeszłości dochodziło nawet do zamieszek).

W fazie wstępnej planowania harmonogramu należy oszacować najmniejszą możliwą liczbę dopuszczalnych terminów aby wszystkie STUBS mogły się odbyć z poszanowaniem niepisanej tradycji. Zagadnienie zamodelowano w języku teorii grafów. Jeśli wierzchołki grafu (studenci PB) są połączone krawędzią (są swoimi ezer), to trzeba im przydzielić różne kolory (różne terminy). Liczba kolorów (im mniejsza, tym lepiej), użytych do legalnego pokolorowania grafu, da nam górne ograniczenie na minimalną liczbę terminów potrzebnych do zorganizowania wszystkich STUBS.

Jak wiadomo problem kolorowania grafów jest NP-trudny, a studentów PB jest sporo, więc prawdopodobnie nie uda się znaleźć optymalnego pokolorowania w rozsądnym czasie. W związku z tym SKNS ogłosił konkurs na najlepszy program implementujący algorytm przybliżony. Programy będą testowane na grafach odpowiadających systemowi rozgrywek stosowanemu w Lidze Fajnego Sportu Rozwojowego (narodowy sport Bajtlandii).

W tym miejscu znów należy się kilka słów wyjaśnienia. Otóż, tworzenie systemu rozgrywek LFSR jest dość skomplikowane i przebiega w dwóch etapach. W pierwszym etapie (i to jest istotne dla treści zadania) wykorzystuje się rejestr przesuwny ze sprzężeniem zwrotnym. Specjalna komisja ustala (wiążę się z tym skomplikowana procedura, której opis pominiemy) długość rejestru l, jego stan początkowy seed i wielomian charakterystyczny. Następnie wszystkim drużynom nadaje parami różne numery ze zbioru: {0, 1, ...,n-1} i wyznacza maksymalną liczbę spotkań mmax oraz dodatkowy parametr k. Kiedy wszystkie parametry zostaną ustalone, postępuje się w następujący sposób:

team1:=0;
team2:=0;
Powtarzaj  m_max razy:
  - do team1 dodaj shift(k) (modulo n); 
  - do team2 dodaj shift(k) (modulo n); 
  Jeśli team1 jest różne od  team2, to  drużyny o numerach 
  team1 i team2 mają do rozegrania mecz.

Uwagi: - shift(k) oznacza liczbę powstałą z k bitów pobranych z rejestru, przy czym młodsze bity pobierane są najpierw; - może się zdarzyć, że para drużyn ma do rozegrania kilka meczów, nie ma to jednak wpływu na konstruowany graf.

Opis wejścia

Najpierw t - liczba grafów testowych.

Następnie opisy poszczególnych grafów:
n - liczba wierzchołków.
4 <= l <= 32 - długość rejestru
seed - stan początkowy rejestru (szesnastkowo)
struktura sprzężenia:
liczba p i p numerów niezerowych współczynników wielomianu charakterystycznego (taps) oraz liczby 1<= k <= 32 i m_max.

Opis wyjścia

Dla każdego testu W jednym wierszu liczba użytych kolorów luc i w następnym kolory kolejnych wierzchołków (liczby ze zbioru {1, 2, ..., luc}).

Punktacja

Dodatnia liczba punktów przyznawana jest wyłącznie za legalne pokolorowania. Jeśli oceniany algorytm użył do pokolorowania danego grafu k kolorów, a wzorcowa implementacja algorytmu SLF k' kolorów, to za pokolorowanie grafu przyznawane jest (k'-2)/(k-2) punktów. Wynik ten uśredniany jest po wszystkich grafach w teście, a następnie sumowany z wagami po wszystkich testach.

Uwaga: może się zdarzyć, że poprawny algorytm SLF da inną liczbę kolorów, niż SLF użyty w tym zadaniu jako wzorcowy.

Przydatne odnośniki

Rejestry przesuwne ze sprzężeniem zwrotnym: LFSR w Wikipedii i inny opis LFSR.

Kolorowanie grafów: Graph Coloring Page Josepha Culbersona, Vertex Coloring w encyklopedii MathWorld i książka Marka Kubale Introduction to computational complexity and algorithmic graph coloring.

Przykład

Wejście:
1
4 6 b 2 5 6 2 5

Interpretacja: Jeden graf, mający cztery wierzchołki, budowany w oparciu o rejestr długości 6 ze stanem początkowym 001011. Do sprzężenia zwrotnego brane są dwa bity: piąty i szósty.

Kolejno łączymy następujące wierzchołki (w nawiasie podano stan rejestru po wykonaniu operacji):

3       2       (111000)
3       0       (010011)
2       0       (101001)
3       2       (110110)
1       3       (110111)

W efekcie otrzymujemy graf (reprezentacja listowa):

0: 2, 3
1: 3
2: 0, 3
3: 0, 1, 2
Wyjście:
3
3 2 2 1

Interpretacja: Użyto trzech kolorów, wierzchołki 0, 1, 2 i 3 otrzymały odpowiednio kolory 3, 2, 2 i 1. Jest to pokolorowanie legalne (żadne dwa wierzchołki połączone krawędzią nie otrzymały tego samego koloru) i możliwe do otrzymania algorytmem SLF.


Dodane przez:kuszi
Data dodania:2008-04-09
Limit czasu wykonania programu:1s-10s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Algorytmy i Struktury Danych, projekt 2008

ukryj komentarze
2014-08-04 02:06:09 Mitch Schwartz
1 <= n <= 15000
1 <= m_max <= 200000
(nie ma specjalnych ograniczeń w n*m_max)

Ostatnio edytowany: 2014-08-04 02:11:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.