254 Senat

[•filipb]

Aici puteţi discuta despre problema Senat.

[•pauldb]

Anumite teste/Testele au spatii la sfarsitul liniilor?

[•filipb]

DA.

[•marin]

Un hint ... ?

[•pauldb]

Cuplaj.

[•gabor_oliviu1991]

ce e ala un cuplaj?... problema asta se poate face avand cunostinte de clasa a 10a?

[•byndrsn]

Matching http://en.wikipedia.org/wiki/Matching
Probabil ca nu (algoritmi pe grafuri se fac dintr-a 11a nu?).

[•Pepelea_Flaviu]

se poate cumva ca o comisie sa un contina nici un candidat?

LE: am gasit, ar trebui precizat totusi ca in fisierul de intrare la sfarsitul liniei se pot afla si spatii...
ia omu 40 de pcte din cauza citirii

[•gabor_oliviu1991]

cat va da pentru:

Cod:

22 
37
6 31 
22 35 
36 22 35 32 3 11 26 17 4 30 10 31 5 23 24 
14 28 13 7 4 16 32 21 12 24 31 25 
13 11 29 27 5 1 3 18 36 2 34 9 21 35 30 10 
28 8 10 6 5 30 1 36 14 9 7 35 32 12 27 3 11 25 24 
14 10 4 34 5 27 7 22 28 6 33 9 35 25 24 13 
20 27 10 22 11 33 2 1 21 26 18 5 3 35 31 32 36 23 28 13 
25 6 36 16 32 33 21 7 17 10 
1 33 30 23 14 17 12 28 26 16 20 3 36 7 4 29 25 10 5 
20 5 9 13 7 35 36 4 28 18 1 23 12 33 6 30 26 8 21 3 2 34 10 
20 11 34 22 4 36 26 19 29 12 10 21 17 25 2 16 
10 5 23 35 29 32 8 24 14 11 9 17 6 1 15 4 2 7 28 30 36 33 
28 29 18 35 34 33 30 21 2 14 31 9 
11 
6 8 11 3 33 29 5 27 16 14 30 4 18 
2 18 3 5 27 21 19 10 25 1 12 30 34 8 13 23 32 31 26 24 20 29 22 
29 8 13 31 3 25 
6 7 10 19 31 1 28 21 
11 34 3 29 13 23 1 16 20 7 10 5 17 24 19 35 15 14 30 32 
16 23 26 31 12 28 15 3 6 9 24 29 14 
22 24 1 23 25 3 29 36 4 14 6 12 19 30 15 16 28 9 21 34 13 35 

[•alexandru92]

.............cred  ca  0  dar  nu bag  mana in foc

[•gabor_oliviu1991]

si mie imi dadea 0. dar am modificat ceva, si primesc:

Cod:

6
22
3
4
1
5
7
2
10
12
8
17
9
14
11
16
13
25
19
15
23
21

ceea ce cred ca e corect. dar nu inteleg ceva. fac cuplajul, iar daka in vectorul in care imi retin nodul cu care cuplej un nod i, gasesc 0, adica nu l-am cuplat cu nimic, afisez doar "0" in fisierul de iesire, altfel afisez cuplajul. cu o astfel de abordare primesc 70 de puncte. iar daca afisez cuplajul fara a verifica daca am noduri pe care nu le-am putut cupla iau 80 de puncte. singurul test care nu are solutie (trebuie afisat doar 0) este testul 10, pe care il prind in ambele cazuri.

[•alexandru92]

pt a te convinge care solutie  e corecta, fa un back........ m-am obisnuit daca n-am alte idei de rezolvare  sau doar sa verfic ca da rezultatul corect ........fac un back(in cazurile posibile)  :d

[•gabor_oliviu1991]

cazurile de pana in maxim 7,8 camere le pot verifica si manual, dar alea de exemplu cel care l-am postat mai sus, are 22 de camere, ceea ce inseamna ca backul meu o sa ruleze o groaza de timp. totusi nu inteleg ce nu prind alea doua teste.inca nu am intalnit test care sa nu mearga. tu cum ai facut?

[•alexandru92]

  initial .........m-am gandit la back  dar dupa ce am vazut limitile ....... verific daca graful e bipartit , in caz afirmativ afisez solutia altfel 0

[•gabor_oliviu1991]

Hmmm... interesant. Eu citeam prima oara M si dupa N, si totusi scoteam 80 de puncte cu o astfel de citire. Mi se pare ca la o astfel de greseala programul sa nu scoata niciun punct, nicidecum 80. Si in testul postat mai sus de mine, inversati 22 cu 37, raspunsul e bun oricum.

[•alexandru92]

separe ca renunt..la ideaa cu bipartit ......... desi nu prea inteleg de ce n-ar merge ?? ........hm vreo idee ca eu am ramas fara

[•gabor_oliviu1991]

Descrie putin ideea. ceea ce ai zis mai sus e prea vag. Intradevar, problema se face cu ajutorul cuplajului (care se aplica unui graf bipartit).

[•alexandru92]

pai eu am .........citit graful si am creat un fel de matrice de adicanta  adica........
is pe linia i  si citestc  numerele   j,k,l,m,n  (ci j,k,l,m,n!=i)  si pun  a[ i ][j]=1,a[ i ][k]=1.....a[ i ][n]=1; Si apoi pur si simplu incerc sa impart  nodurile grafurilor in 2 multimi........daca am reusit afisez o multime altfel afisez 0

[•pauldb]

Nu mi se pare corect ce incerci sa faci. Poate ar trebui sa citesti mai mult despre cuplaj.

[•alexandru92]

Stiu ca  poate cer ceva imposibil, dar stie cineva un  articol sau ceva de genu care exmplica  cuplajul intr-un graf  pe limba orcui si o implmentare  a  problemei  cuplaj  maxim in graf bipartit, explicat   va rog   
[later]  Am  modificat, mai bine?

[•wefgef]

@Alexandru: Un sfat prietenesc: ar fi o idee buna daca ai folosi caracterul "." doar o singura data. Ma dor ochii atunci cand iti citesc posturile, si nu cred ca sunt singurul. Ar fi un pas inainte daca ai scrie corect, in limba romana.

[•freak93]

Imi poate spune cineva cu ce gresesc la acest algoritm. Pun un nod sursa->0,senatorii ii pun nodurile in 1->n, comisiile in nodurile de la n+1->n+m si un nod destinatie in in n+m+1. Daca un senator x faca parte dintr-o comisie y pun costul muchiei C[ x ][ y ]=1.
Pe deasupra mai pun si costul muchiilor de la sursa la fiecare senator ca fiind 1 si costul muchiilor de la comisie la destinatie ca fiind tot 1.
Fac flux maxim de la sursa la destinatie si verific daca este egal cu m(in caz afirmativ caut pentru fiecare comisie cu ce senator e unita,altfel afisez 0)
Algoritmul si ideea mi se par perfecte si totusi nu iau decat 10 puncte WA pe testele 1-8 si 10(corect pe 9).
Putin ajutor va rog?

[Later Edit]Am luat 100. Era de la citire

[•DraStiK]

Problema asta da mari bătăi de cap. Iau 90p, și din câte am citit din posturile anterioare, testul 10 (cel care il pic eu) e cel fără soluție.

Practic când nu este soluție, cuplajul maxim e mai mic decât M. Nu am dreptate?

Va rog puțin ajutor

[•Florian]

Nu. Daca exista vreun nod necuplat ( dreapta[ i ] == 0) inseamna ca nu exista solutie. Altfel, exista.

[•DraStiK]

Exact asta verific. Uite mai exact:

Cod:

    for (i=1; i<=m; ++i)
        if (r[i]==0)
        {
            printf ("0");
            return ;
        }
    for (i=1; i<=m; ++i)
        printf ("%d\n",r[i]);

Am verificat sa fac bine cuplaju de nenumărate ori. Chiar nu știu ce ar putea fi.