035 Party

[•fluffy]

Aici puteţi discuta despre problema Party.

[•Matrix]

...

in text scrie ca se va afisa nr de invitati la petrecere si acestia
dar nu scrie nicaieri ca trebuie sa fie un nr maxim de invitati
nu ar trebui specificata mai clar cerinta
   

[•domino]

...

in text scrie ca se va afisa nr de invitati la petrecere si acestia
dar nu scrie nicaieri ca trebuie sa fie un nr maxim de invitati
nu ar trebui specificata mai clar cerinta
   

Nu trebuie sa fie numar maxim de invitati. Trebuie sa fiu un numar de invitati a.i. sa satisfaca toate conditiile. Citeste mai atent enuntul!

[•teplesnescdenutevezi]

"x y 0 are semnificatia ca x sau y trebuie sa participle la petrecere " , pot participa si amandoi ? dar nici unul ?

[•Cosmin]

Problema de fapt este cea a satisfacerii unei expresii logice. Faptul ca un individ participa sau nu la petrecere este o variabila booleana si peoblema cere atribuiri de valori acestor expresii booleene pentru ca toate constrangerile din enunt sa fie adevarate. In literatura problemei ii zice 2SAT, 3SAT este problema NP-completa, dar 2SAT e rezolvabila polinomial. Aceasta problema a fost data la CEOI in 2001 sau 2002 nu mai stiu exact dar cu date mai mari, rezolvarea problemei de pe site poate fi mult mai simpla folosind un algoritm probabilist care se poate demonstra ca ajunge usor la solutie.

[VladS]

Am gasit pe net o rezolvare polinomiala probabilistica dar nu cred ca este corecta deoarece iau WA pe 4 teste.  
Acolo scria ca intr-o expresie de genul E1 & E2 & E3 ... gasesc o expresie E care este falsa si schimb (in mod aleator) valoarea unei variabile din ea.
Sii fac asta pana cand expresia mare devine adevarata. As vrea sa stiu daca e corect algoritmul sau mai trebuie sa mai caut.

[•Cosmin]

Parca asa era si solutia mea ... nu mai tin minte exact, poti sa posezi linkul pentru algoritmul probabilist? Aceeiasi problema s-a dat la CEOI nu mai tin minte exact in ce an, dar acolo erau mai multe expresii logice ce trebuiau satisfacute si trebuia conceput un algoritm eficient care avea la baza descoperirea componentelor tari conexe dintr-un graf in timp O(n + m).

[VladS]

www.fas.harvard.edu/~libcs124/CS/lec15.pdf

[•Cosmin]

Mda, cred ca aia era sursa mea de inspiratie

[VladS]

Gata, am rezolvat. Faza era ca uneori imi afisa ca o solutie este sa nu participe nimeni la petrecere.
Merci Cosmin.

[•devilkind]

eu am gasit alta solutie, bazata pe parcurgerea unui graf. Iau un graf avand ca noduri i si !i (1<=i<=n), si am muchie de la x la y daca exista propozitia (!xvy). Si apoi agati arborele intrun nod i (atentie sa nu fie !i), il fac adevarat si apoi parcurg grafu si ii fac pe toti adevarat.

Pare bine si totusi nu iau decat 20 de pct.

[•Cosmin]

De unde ati scos expresia asta cu agat arborele intr-un nod ca am tot auzit-o si mi se pare aiurea ... Cat despre modul de rezolvare, daca ai citit articolul despre probleme 2sat din Ginfo o sa vezi acolo 3 rezolvari diferite, printre care si asta a ta care cred ca presupune o valoare de adevar si vede apoi daca variabilele care sunt fortate ajung sa se contrazica.

[•devilkind]

de fapt ii dau voie cuiva sa vina la petrecere si apoi impiedic toate restrictiile acestuia. Cam la asta se rezuma rezolvarea mea. Banuiesc ca nu exista teste in care sa fie imposibil.

[•cypry]

  ok... am ales urmatoarea varianta de rezolvare: cand citesc conditiile le pun intr-o matrice. Daca e x y 0, pun a [ x ] [ y ] =4 si a [ y ] [ x ] =4(ca sa nu fie 0), la fel pentru 3, iar daca e 1 pun a [ y ] [ x ] =1 si pt 2 a [ x ] [ y ] =1. Dupa aceea, iau invitatii pe rand, si considerand ca invitatul k participa, pun celorlalti restrictii, ghidandu-ma dupa linia k din matrice. Am tratat si cazul cand pentru aceeasi invitati se pot pune mai multe conditii, dar tot 30 de puncte iau, pe celelalte WA. What did I do wrong?

[•peanutz]

cerintele nu au prioritati? gen cerinta 0 < cerinta 1 < cerinta 2 < cerinta 3?

adica daca 1 si 3 participa si:

1 2 1
3 4 1
2 4 3
ce se-ntampla? sau nu se poate ...

si, de fapt, x y 1 = y x 2 ?

Eu m-am gandit la un random ciobanesc, chiar sunt curios sa vad cat iau, si am motive sa cred ca ar putea fi aproape de 100

[•stef2n]

La primul exemplu din enunt, fisierul party.out contine

Cod:

1
3

in loc de

Cod:

2
1
3

Probabil s-a gresit cand s-a trecut la infoarena2.

[•filipb]

solved.

[•stef2n]

Se pare ca evaluatorul la problema asta are niste scapari. Se iau 20 de puncte cu o sursa goala: job #85254

[•gabitzish1]

Greseala in enuntul problemei :

O cerinta de genul x y 0 are semnificatia ca x sau y trebuie sa participle

[•vlad_D]

Cred ca testele sunt slabe (o singura componenta sc sau o singura componenta si restu sunt ne-invitati = 70pct).

[•proflaurian]

Este posibil ca numarul de invitati sa fie 0? Mie mi se pare ca daca in teste nu apare nicio conditie x y 0 atunci o solutie banala ar fi sa nu fie invitat nimeni la petrecere . Am dreptate?

[•RaduGabriel2012]

Evaluatorul da "Eroare in configurarea problemei"