Zadanie z zeszłorocznej ligi SPOJ'a (HS10RMSY)

Witam! Jestem w I kl. liceum i pan od TI dowiedziawszy się, że trochę umiem to i tamto dał mi zadanie do rozwiązania. Jest to zadanie "Check Ramsey [HS10RMSY]". Z samym kodem to sobie powinienem jakoś poradzić, ale nie rozumiem kompletnie problemu. Problem mam przetłumaczony na polski, ale i tak kicha :D Chodzi o jakieś grafy i podgrafy - tego jeszcze nie mieliśmy (w I kl. chyba nie będzie), a z tego co wiem to jest z matematyki. Jeżeli był by ktoś na tyle miły pomóc i wytłumaczyć o co chodzi z tym problemem (z kodem pomęczę się sam). Treść po polsku: http://wklej.org/id/599689/

No tak na 'szybko' to ci chyba nikt nie wytłumaczy czym są grafy, to jest bardzo rozległy temat... Polecam wykłady z algorytmiki stosowanej z UW - http://was.zaa.mimuw.edu.pl/
ale do nich to raczej trzeba mieć jakieś podstawy. Poczytaj sobie więc na wikipedii, polecam też stronę http://www.astagor.net/putinf/data/algorytmy/

No to jeżeli to tak szybko w miarę pojąć się nie da to raczej nie będę się nad tym nie wiadomo ile męczył. Dziwne, że nauczyciel mi to dał, no cóż... Poczytam trochę może jednak coś skumam. Dzięki za linki, jak by ktoś jeszcze coś ciekawego chciał dodać proszę o posty.

W sumie to jeszcze go spytam, bo on wszystko wie to i to może mi wytłumaczy.

Kod to przy zadaniach ze spoja mniejszy problem - zawsze kluczem jest dobry (albo i jakikolwiek :D) algorytm.
Niestety, trzeba pogodzić się z tym, że większość zadań na wyższym poziomie wymaga od piszącego znajomości (co najmniej) podstaw matematyki dyskretnej - zwłaszcza teorii grafów. W szkole średniej tego nie wobaczysz na normalnych lekcjach, ani na podstawie, ani na rozszerzeniu z matmy - po prostu nie obejmuje tego program nauczania.
Jeśli chcesz się zajmować tego typu rzeczami, to nie objedzie się bez zaznajomienia z grafami oraz zapoznania się z różnymi algorytmami na nich operującymi. Niestety "trochę umieć to i tamto", to za mało, żeby od razu skakać na głęboką wodę, jak proponuje Twój nauczyciel.
Musisz dowiedzieć się czym jest graf, czym jest podgraf, na czym polega kolorowanie grafu, co to są te liczby Ramsleya - i wtedy myśleć nad rozwiązaniem.

Na początek możesz poczytać - http://www.mini.pw.edu.pl/MiNIwyklady/grafy/grafy.html

narysuj sobie na kartce N kółek i ponumeruj je od 0 do (N-1). Połącz je liniami każda z każdą: jeśli na wejściu pojawiło się np połączenie 0 1 (połączeń jest e), to narysuj czerwoną linię między tymi kółeczkami, a dla reszty połączeń narysuj linię niebieską.

Co to jest graf?
To twój rysunek.

Co to jest wierzchołek grafu?
To kółeczko.

Co to jest krawędź grafu?
Połączenie między kółeczkami.

Co to jest graf pełny?
Połączenie kółeczek każda z każdą.

Co to jest podgraf?
Graf który jest częścią twojego dużego grafu, ale zawiera tylko część wierzchołków - a skoro części wierzchołków nie ma to połączeń również.

Pytania które musisz sobie zadać:

• Ile da się utworzyć różnych podgrafów pełnych, takich w których skład wchodzi k/l wierzchołków i krawędzie tych grafów są niebieskie/czerwone?

Weź sobie drugi przykład. Po narysowaniu wyjdzie Ci czerwony sześciokąt i niebieska gwiazdka w środku tego sześciokąta. Ponieważ graf pełny dla k=l=3 wierzchołków to trójkąt, to czerwonych trójkątów na rysunku nie ma wcale, a niebieska gwiazdka składa się z dwóch trójkątów. Odpowiedź zatem dla tego przykładu to 0 i 2

Dobra mniej więcej rozumiem, ale co to jest to k i l? Na razie wiem tyle, że są to liczby naturalne i są to liczby wierzchołków podgrafów. Są one podane na wejściu i co dalej z nimi?

e to liczba czerwonych i tyle jest par wierzchołków, które się łączą. Do czego mi potrzebne k i l?

Mając te k i l musisz obliczyć ile jest takich podgrafów, które mają wielkość k/l (składają się z k/l wierzchołków), są koloru niebieskiego/czerwonego i są grafami pełnymi i to wypisać na wyjście.

Czyli wczytuję n - liczba wierzchołków (na razie na kartce), rysuję sobie taki graf o n wierzchołkach, potem wczytuję k i l (do pamięci), dalej wczytuję e i potem e par połączonych na czerwono. Teraz k to jest k*** co to jest?? Nie mogę pojąć do czego mi te k i l potrzebne...

Nie.

• Wczytujesz ilość przypadków testowych d.
  jeśli d jest większe od 0 to: (1)

1. wczytujesz n,k,l,e.
2. wczytujesz e par (dwie liczby), które oznaczają czerwone krawędzie// To jak to przechowasz to zupełna dowolność.
3. Teraz obliczasz ile jest takich podgrafów, które mają wielkość k/l (składają się z k/l wierzchołków), są koloru niebieskiego/czerwonego i są grafami pełnymi
4. wypisujesz wynik
5. zmniejszasz d o 1 i idziesz do (1)

• koniec

Dobra skumałem, ale na kartce :D Teraz tylko kod... :/

A mógłby ktoś wskazać gdzie są te 2 pełne grafy, bo w przykładzie w teście 2 wychodzą 2 niebieskie, które to?

Czyli ma 3 wierzchołki i są 2 takie.

Właśnie dziś w szkole się nudziłem i to rozkminiłem, które to. Dzięki. Teraz zabieram się do obmyślania algorytmu, potem kod.. :/

Znalezienie wzoru na ilość przekątnych wielokąta może być pomocne :P

Oj tam wzór to nic, ale reszta szukanie i w ogóle, o zobaczymy może jednak tak trudno nie będzie.

biorąc pod uwagę wielkość danych wejściowych to nawet najgorszy algorytm przejdzie, więc zrób byle co ale żeby działało ;)

Tu nie chodzi zbytnio czy przejdzie czy nie, bo to przecież oddaje nauczycielowi, więc wypada żeby to miało ręce i nogi :D. Wymyśliłem takie coś, ale nie wiem czy jest dobre:
Szukam połączeń między wierzchołkami (dla k = 3) i jeżeli są takie 3 połączenia, gdzie żadne nie jest czerwonym to niebieskie++.
Czekajcie a jak z czerwonymi będzie? Te co już na wejściu są czerwone (krawędzie) to też mogą się liczyć jako jedna z krawędzi tego mojego podgrafu??

Fu**... Z kodem też nie łatwo, jakoś nie mam głowy algorytmicznej. Potrzebuję przeszukać każdą krawędź i jeżeli jest niebieska to szukać następnego połączenia aż do k takich połączeń, ale dupa, nie mogę nic wymyślić jaką metodą to zrobić. Być może potrzebne są mi inne algorytmy? Podpowiedziałby ktoś jak to można zrobić?

ja bym Ci proponował rysować sobie różne przypadki na kartce i szukać rozwiązań ręcznie, szukać zależności między rozwiązaniami. Jak zauważysz jakieś zależności to implementujesz je i sprawdzasz sprawdzarką, jeśli nie znajdziesz żadnych to robisz bruta.

Właśnie próbuję, ale na kartce niby fajnie wychodzi szukanie tego, a w kodzie nie wiem jak to zapisać. Udało mi się tylko metodą głupiego na konkretny przykład napisać kod. A jak próbuję to napisać dla wszystkich przypadków to null, nic z tego. Jeszcze trochę popróbuję i jak nic się nie uda to się poddam, bo nie ma co ślęczeć nad tym nie wiadomo ile.. :/