Az előző posztomhoz kiegészítésként egy példával illusztrálnám a markáns különbséget a magyar olimpiai válogatóverseny és a nemzetközi programozóversenyek színvonala között. Ahogy azt már ott is leírtam, a legnagyobb problémám a hazai hozzáállással az, hogy a kreatív problémamegoldást nem teszteli: gondolkodni csak minimálisan kell, eredeti ötletet igénylő feladat pedig lényegében nem fordul elő. Ehelyett azt teszteli, hogy a rutin algoritmusokat felismeri-e, és le tudja-e programozni a diák, ha azok praktikusan nincsenek álcázva.
Az alábbiakban a gráfban elvágó pontot (illetve kétszeresen összefüggő komponenseket) kereső algoritmus köré szerkesztett feladatokat mutatok, kettőt. (Ez az eljárás egyébként közismert, bármely algoritmusoskönyvben benne van, még az angol wikipédián is megtalálható, és az olimpiákon is elvárják a diákoktól az ismeretét.) Az egyik feladat a válogatón szerepelhetne, a másik pedig valamelyik regionális ACM-fordulón szerepelt.. talán többön is. Azt is pontokba fogom szedni, hogy szerintem hogy jön rá az ember a feladatok megoldására, bár a másodikra nekem sajnos nem volt lehetőségem, mert hamarabb hallottam az ötletet, mintsem rájöhettem volna. Emiatt azok kedvéért, akik nem szeretnék, hogy lelőjem a poént, a feladatokat külön mondom ki, és jól láthatóan, ún. vonallal elválasztom a megoldásos szekciótól. (Én meg ezt a feature-t is kipróbálhatom, háhá.)
Nézzük tehát, hogy mit kap a diák a válogatóversenyen:
Eufrozina az adott gráf 1-es sorszámú csúcsában lakik. Szeret sétálni a gráf élein, de csak úgy, ha egy kör mentén halad (ti. nem szereti az olyan unalmas dolgokat, mint egy séta során kétszer megnézni ugyanazt a csúcsot, de azért valahogy haza is szeretne jutni). Melyik csúcsokba juthat így el?
És mit kap a diák ACM-en:
Kunigunda szintén kör mentén szeret sétálni, ő azonban – hajléktalan lévén – nincs az 1-es, vagy bármely más csúcshoz kötve. Viszont van neki egy szeszélye: csak páratlan (legalább 3 hosszú) körön hajlandó végigsétálni. Vajon merre sétálhat ő? (Kunigunda elsajátította a teleportálás művészetét, így szerencsére azzal nem kell foglalkoznunk, hogy az egyik sétája után hogy kerül a másik útvonalra.)
Mindkét feladatra lineáris idejű algoritmus adható. Azt hiszem, aki még gondolkodik egy kicsit a feladatokon, az is érzékelni fogja a különbséget. Mindenesetre következzék a várva-várt vonal.
Nézzük tehát a megoldásokat. Az első feladatra nehéz mit mondani:
- Mik vannak az 1-es csúccsal közös körben? Hát a blokkok, amelyek őt tartalmazzák.
Legalábbis ez kéne, hogy legyen egy versenyző első gondolata. Persze ha nem ismeri ezt a tulajdonságot az ember, akkor lehet megsejteni, hogy elvágóponton keresztül nem megy kör, azaz minden kör egy blokkon belül van, de Menger-tételt nem fog bizonyítani a gimnazista versenyen. Ha viszont nem is tudjuk, mi az az elvágó pont, vagy hogy van rá hatékony algoritmus, akkor a feladat esélytelen. Úgyhogy inkább tudjuk.
Térjünk inkább a másik feladatra:
- Hát ha páros a gráf, akkor még én is tudom.
- Hmm.. kör. Az blokkon belül megy.. elég csak a blokkokat nézni
- Na melyik csúcson megy páratlan kör kétszeresen öf. gráfban? ha páros a gráf, akkor egyiken sem..
- Na de ha van egy páratlan kör a blokkban.. dejszen az kétszeresen összefüggő.. akkor bármely csúcson át van páratlan kör
És innen már csak le kell programozni, hogy megkeressük a blokkokat, és eldöntjük, hogy páros gráf-e. Ez utóbbi megoldásban három észrevétel volt: hogy elég blokkokat nézni, hogy a páros blokkok rosszak, és hogy a nem páros blokkok jók. Ez utóbbi észrevétel talán valamivel nehezebb a másik kettőnél. Ehhez képest az első feladathoz jóindulattal egy, de inkább annyi észrevétel sem kellett. Egyszerűen ránézésre tudja az ember, hogy az elvágópontokon túl nincs semmi érdekes.
És akkor most egy relatíve nehéz válogatópéldáról volt szó. Az algoritmus nem nagyon egyszerű, de rutin kéne, hogy legyen. Átlagosan a diákok harmada tudja leprogramozni az ilyet. Valamit kezdeni kéne ezzel, de egyedül kevés vagyok hozzá. A szakkörömről meg továbbra is majd később :p
