O problema din GInfo

[•CezarMocan]

Am gasit o problema intr-un numar mai vechi din GInfo... pare interesanta, dar nu am nicio idee (polinomiala) la ea... dati-va si voi cu parerea... Primul care o scoate are o bere (sau un suc, in functie de preferinte) de la mine . Succes!


P039808: Trupa de comando

Se consideră o hartă pe care sunt desenate n ţări. Suprafaţa fiecărei ţări este colorată într-o singură culoare.

O trupă de comando porneşte dintr-o ţară dată x şi trebuie să ajungă într-o altă ţară dată y. Pe parcursul traversării oricărei ţări, membrii trupei trebuie să se îmbrace în echipament de camuflaj având culoarea de pe hartă a ţării traversate. Determinaţi drumul trupei de comando astfel încât ei să aibe nevoie de un număr minim de echipamente.

Date de intrare:

Fişierul de intrare INPUT.TXT are următoarea structură:

- pe prima linie se află un număr întreg n (2<=n<=100), reprezentând numărul de ţări de pe hartă;

- fiecare dintre următoarele n linii conţine un string care are structura:

numei culoarei vecin1 vecin2 ... vecink

unde:

- numei reprezintă numele unei ţări (string);

- culoarei reprezintă culoarea (string) ataşată ţării având numele numei;

- vecin1 vecin2 ... vecink (0<=k<=n) reprezintă numele ţărilor vecine cu ţara numei;

- şirurile de caractere corespunzătoare numelor, respectiv culorii sunt separate prin câte un spaţiu;

- pe următoarea linie sunt date două nume (stringuri): ţara din care porneşte expediţia şi ţara în care trebuie să ajungă.

Se presupune că datele sunt corecte.

Date de ieÅŸire:

Fişierul de ieşire OUTPUT.TXT are următoarea structură:

- pe prima linie se va scrie un număr întreg m (1<=m<=n) reprezentând numărul de echipamente necesare trupei pentru a realiza expediţia respectând cerinţele problemei;

- pe următoarele m linii se va descrie drumul trupei, specificând pe fiecare linie numele unei ţări prin care va trece trupa.

În cazul în care există mai multe soluţii, se va specifica cea care trece printr-un număr minim de ţări.

Exemplu:

INPUT.TXT:

6

Romania rosu Bulgaria Ungaria Yugoslavia

Bulgaria verde Romania Yugoslavia

Ungaria galben Romania Yugoslavia Croatia

Yugoslavia alb Romania Ungaria Croatia

Croatia rosu Ungaria Yugoslavia Italia

Italia galben Croatia

Romania Italia

OUPUT.TXT:

2

Romania

Ungaria

Croatia

Italia

[•byndrsn]

Esti sigur ca nu e NP-hard? Eu am interpretat enuntul astfel: avem un graf in care fiecare nod are o culoare si vrem sa gasim un drum de la x la y cu un numar minim de culori. Din enunt graful pare planar, ceea ce poate schimba dificultatea problemei (although I'm skeptical about that). Daca graful e general, reducere de la Set Cover pare plauzibila: elementele (from the set cover instances) sunt noduri in graf si seturile sunt culorile. Mai precis, in afara de cele doua noduri speciale x si y, pentru fiecare element a_i si fiecare set S_j care contine elementul a_i, avem un nod v_{i, j} de culoare j. Nodul v_{i, j} (2 <= i <=  n - 1) este conectat cu v_{i - 1, k} for all k, nodul x este conectat cu nodurile v_{1, k}, si y este conectat cu nodurile v_{n, k}. Ceva de genul acesta pare sa mearga, I did not check it myself though.

[•CezarMocan]

  S-ar putea sa fie asa cum zici... dar ma gandeam ca din vreme ce a fost propusa asa exista o rezolvare corecta care nu e exponentiala.

[•Cosmin]

Clara Ionescu a propus-o demult si la un moment dat m-a intrebat pe mine daca stiu vreo solutie eficienta.

Mai demult se dadeau probleme pe la loturi la care nu se stia rezolvarea . De atunci au evoluat olimpiadele.