Megoldás
Algoritmus
(IOI 2006, 2. nap, 1. feladat, hivatalos megoldás)
Tegyük fel, hogy az x
városból indul az útvonal. A következő állomás csak x
jobb vagy bal szomszédja lehet, minden más "él" két olyan részre vágná a
tópartot, amelyek között már csak úgy lehetne összeköttetés, ha az metszené
valamelyik korábbi élet.
A gondolatmenet hasonló módon folytatható az útvonal további városaira.
Minden új város szomszédos kell legyen az eddig összekötött
városokkal.
Tehát az útvonal felépítésekor mindig két lehetőség közül választhatunk.
(Gyüre Balázs megoldása csak ennyit használ, és az első néhány tesztesetre
a "nyers erő" algoritmus is eredményt ad.)
Vegyük észre, hogy ha néhány várost már összekötöttünk, és az útvonal
y-ban végződik, akkor a városok összekötési sorrendje nem számít.
Például ha a 2,3,4 és 5 városokat kötöttük eddig össze, és az útvonal
5-ben végződik, akkor mindegy, hogy az eddigi sorrend
(2-3-4-5), (3-2-4-5) vagy (4-3-2-5), most az 1 vagy a 6 következhet.
Ez a jelenség a dinamikus programozás módszerét
juttathatja eszünkbe. Az alább részletezett megoldás már polinomiális algoritmust ad mind
az eldöntésre, mind az útvonal meghatározására.
(Mészáros Balázs megoldása ezt a hatélonyabb algoritmust implementálja.)
Egy tetszőleges (u,v) város párra legyen bal(u,v) igaz,
ha az u-v éltől balra lévő városok összeköthetők olyan nem metsző útvonallal, amely v-ben végződik és u-t is tartalmazza.
Hasonló módon definiáljuk jobb(u,v)-t is.
Legyen minden i-re bal(i,i)=jobb(i,i)=igaz.
A következő rekurziók egyszerűen igazolhatók:
- bal(u,v)=(jobb(u,v-1) és van_él(v-1,v)) vagy
(jobb(v-1,u) és van_él(u,v))
- jobb(u,v)=(jobb(u,v+1) és van_él(v+1,v)) vagy
(bal(v+1,u) és van_él(u,v))
Akkor van megoldása a feladatnak, ha van olyan (i,j) város pár, amire
jobb(i,j)=bal(i+1,j)=igaz.
Ilyenkor a városok sorrendje a fenti rekurzió végigkövetésével megadható.
Kódok
mexico0.c (Mészáros Balázs, C) Csak az eldöntési rész.
mexico.c (Mészáros Balázs, C) A teljes megoldás.
mexico.cs (Gyüre Balázs, C#)
