002 Jocul Flip

[•Florian]

Pai ai putea sa postezi sursa... ca altfel nu ne puteam da seama... ori da`mi un mesaj provat cu Id-ul tau, si te ajut cu placere. [ pt ca nu prea e permisa postarea surselor pe forum] 

[•cos_min]

Eu nu am incercat prin backtraking.In fine solutia mea nu e foarte reusita dar nu asta ar fi problema cea mai mare.Ci  faptul ca in flip.out imi scrie de 3 ori solutia .Ex: dak solutia este 24 in flip.out imi va scrie 242424.Cine stie de ce (.Si sa nu credeti ca am scris de mai mule ori in fisier.Am o singura --fprintf(g,"%ld",.....);
In locul ... este variabila;

Poate variabila aia chiar are valoarea 242424. Incearca fprintf(g,"%ld",varialbila-242424); si vezi daca iti afiseaza 0.

[•Bogdan_tmm]

Pai gasi care era problema.Eu aveam mai multe variabile pentru mai multe sume totale ale unor matrici.Iar la sfarsit aveam mai multe if...
        if...ca sa aflu maxima dintre ele .Si dupa ce bagai "else" intre ele nu mai am problema asta.Dar de ce nu mergea doar cu "if" simplu?Oare la mine toate sumele matricelor sunt egale?(Nu cred dar se poate ( bogdan_tmm e id
       

[•cristiprg]

de exemplu, am linia 1 2 -3 -4, trebuie sa o comut, ea devenind -1,-2,3,4, si daca am de comutat prima  coloana, atuncia linia devine 1,-2,3,4?   

[•Florian]

da

[•vlad_oltean]

am... facut problema chiar daca e ora 4 noaptea/dimineata si lumea sforaie pe la mine prin casa, am avut mult de invatat la backtracking din problema asta... multumesc pentru sugestiile din posturile anterioare

[•robigi]

ash avea shi io ontrebare
deci, eu am dat solutia asta in cpp

Cod:

#include <fstream>
using namespace std;

ifstream f ("flip.in");
ofstream g ("flip.out");

long v[1000][16], n, m, sl[1000], sc[16];

void read()
{    f >> n;
     f >> m;
     for (int i=0 ; i<n; i++)
         for (int j=0; j<m; j++)
            f >> v[i][j];
}

void change()
{    int s=0;
     for (int i=0; i<n; i++)
         for (int j=0; j<m; j++)
         {   sl[i]=sl[i]+v[i][j];
             sc[j]=sc[j]+v[i][j];
         }
     for (int j=0; j<m; j++)
         while (sc[j]<0)
         {     for (int i=0; i<n; i++)
                   v[i][j]*=-1;
               sc[j]*=-1;
         }    
     for (int i=0; i<n; i++)
         while (sl[i]<0)
         {     for (int j=0; j<m; j++)
                   v[i][j]*=-1;
               sl[i]*=-1;
         }
     for (int i=0; i<n; i++)
         for (int j=0; j<m; j++)
             s=s+v[i][j];
     g << s;
}

int main()
{    read();
     change();
     f.close();
     g.close();
     return 0;
}

dar nush de ce nu imi da numai 10 puncte shi chiar nunteleg dc

numi puteti pls da ink cateva exemple sa vad ce are sau sami explicati??

ms

Editat de admin: Folosesti tagul code cand vrei sa postezi surse.

[•cos_min]

Problema se rezolva cu ajutorul backtracking-ului, nu cu greedy cum ai facut tu. Poti citi cele 5 pagini ale topicului daca nu te prinzi nicicum de rezolvare. Spor!

[•fireatmyself]

Solutia nu este corecta. Incearca sa fixezi liniile pe care le inmultesti cu -1 si apoi, pentru fiecare fixare, sa calculezi prin programare dinamica ce coloane inmultesti cu -1.

Uite cateva teste pe care programul tau nu le trece:

Cod:

3 3
-1 -1 2
-1 3 -1
1 -1 2

Raspunsul tau este 5, dar raspunsul corect este 11 (se inmulteste cu -1 linia 2 si coloana 2)

Cod:

4 3
-1 2 -1
1 -1 -1
3 -1 -2
3 1 -1

Raspunsul tau este 10, dar raspunsul corect este 14 (imultesc cu -1 lina 1, coloana 2 si coloana 3)

Cod:

5 3
-1 1 -1
2 -3 -1
-3 2 4
1 -2 3
3 2 1

Raspunsul tau este 14, dar raspunsul corect este 16 (imnultesti cu -1 linia 1, linia 3 si coloana 2)

Cod:

9 6
1 3 -14 -6 4 -3
-3 -2 3 4 5 -1
3 2 -5 -7 6 7
7 8 1 -4 12 3
-4 32 -10 3 4 5
3 1 4 5 6 -7
13 3 -14 3 2 -4
3 1 4 5 6 7
-1 -1 -13 -1 -1 -1

Raspunsul tau este 123, dar raspunsul corect este 189.

Sper sa te ajute. Spor. 

[•O_Neal]

am facut si eu un soi de backtracking si nu inteleg de ce iau numa 60. unele teste nu le prind, am citit in mare topicu` asta nu vad de ce iau eu doar 60 .. ar trebui sami acopere toate testele am luat un backtracking pt linii toate posibilitatile cu -1 respectiv 1 de inmultire la fiecare linie, si pt fiecare caz am inmultit coloanele cu -1 respectiv 1 dupa cum era mai mare suma coloanei.. idei, motive pt care nu e buna idea/ luasem numa 60?

[•wefgef]

Ideea ta e buna, probabil ca ai gresit pe undeva implementarea

[•andrici_cezar]

am o intrebare.... se pot schimba mai multe linii si mai multe coloane?
  si zicetimi si mie ce am gresit ca mor

[•amadaeus]

Da, pot fi schimbate oricate linii si oricate coloane. Incearca o rezolvare care sa ia in vedere toate cazurile.

[•venom4u31]

Poate cineva sa ma ajute sa vad ce este gresit in teoria mea?

Cod:

   1. #include <fstream.h>  
   2. int main ()  
   3. {long double a[30][30][2];//declararea contine o matrice tridimensionala pentru a stoca sumele fiecarei linii/coloane  
   4. int i,n,m,j,x,k;  
   5. ifstream f("flip.in");  
   6. ofstream g("flip.out");  
   7. f>>n>>m;  
   8. for (i=1;i<=n;i++)  
   9.     for (j=1;j<=m;j++)  
  10.         f>>a[i][j][0];//cea de-a treia dimensiune este 0 pentru numerele introduse de la tastatura  
  11.   
  12. for (i=1;i<=n;i++)  
  13.     {a[i][1][1]=0;//cea de-a treia dimensiune este 1 pentru a stoca suma liniilor i in ea  
  14.     for (j=1;j<=m;j++)  
  15.         a[i][1][1]=a[i][1][1]+a[i][j][0];  
  16.     if (a[i][1][1]<0) //daca suma era negativa atunci urmeaza comutarea liniei astfel:  
  17.         for (k=1;k<=m;k++)  
  18.             a[i][k][0]=0-1*a[i][k][0];  
  19.     }  
  20.   
  21. for (j=1;j<=m;j++)  //aceeasi procedura a fost urmata ulterior la coloane  
  22.     {a[j][1][1]=0;  
  23.     for (i=1;i<=n;i++)  
  24.         a[j][1][1]=a[j][1][1]+a[i][j][0];  
  25.     if (a[j][1][1]<0)  
  26.         for (k=1;k<=n;k++)  
  27.             a[k][j][0]=0-1*a[k][j][0];  
  28.     }  
  29.   
  30. x=0; // x este suma numerelor din noua matrice  
  31. for (i=1;i<=n;i++)  
  32.     for (j=1;j<=m;j++)  
  33.          x=x+a[i][j][0];  
  34. g<<x;  
  35. // problema este ca nu stiu unde as putea gresi; nu am gasit niciun exemplu in care teoria sa nu fie confirmata si totusi, aparent ele exista;  
  36. } 

***Daca am infaptuit ceva ilegal postand acest cod, pe care-l dau de buna voie, va rog editati, cine poate mesajul... ***

[•devilkind]

Nu ai facut nimic ilegal postand acest cod, deoarece el nu merge. Algoritmul din radacina nu e bine gandit, nu stiu sa iti dau exemple concrete pe care sa nu iti mearga deoarece codul e mult prea lung pentru a il putea urmari insa pot sa te asigur ca nu e bine. Citeste ce s-a mai discutat aici, vei gasi hinturi destul de multe cu referire la rezolvarea corecta si destul de multe teste care sa pice solutii gresite.

[•venom4u31]

Doream sa stiu doar daca ideea este buna; greseli de programare poate sunt, insa ma intreb daca o metoda de rezolvare este cea de a verifica daca suma pe fiecare linie este pozitiva, in caz contrar, ea urmand a fi schimbata. Apoi se repeta procedura pe fiecare coloana si pe urma se face suma...

[•Florian]

Citeste tot topicul, si o sa vezi de ce nu e buna metoda asta. Rezolvarea consta in generarea tuturor posibilitatilor, lucru pe care il poti face prin backtracking. Succes! 

[•venom4u31]

Inteleg rezolvarea enuntata pe topic... doresc insa sa gasesc ceva original;

[•devilkind]

succes :d

[•Florian]

Inteleg rezolvarea enuntata pe topic... doresc insa sa gasesc ceva original;

Puteai face ceva "original", fara a trage cu ochiul pe forum.  Daca gasesti alta rezolvare, spune-ne si noua, ca suntem tare curiosi.

[•venom4u31]

Din ce am inteles de pe forum, trebuie sa iau in considerare toate cazurile posibile. Nu m-am uitat prea mult si nici pe toate paginile, deoarece ar fi fost mai bine sa iau rezolvarea de la altcineva (doar se pot lua rezolvari de la problema asta, nu?) Daca rezolvarea propusa de mine este si ea inclusa pe forum, atunci imi cer scuze; nu va pot dovedi ca m-am gandit de unul singur la ea;

[•devilkind]

e o singura solutie discutata pe forum si acceptata ca fiind corecta.

[•razyelx]

Am revenit la aceasta problema, pentru ca cica se apropie perioada tezelor si tre sa invatz ceva backtrack(glumesc). Am rezolvat-o cu back.
Dar din pacate i-au doar 40 pct pt ca imi iese din timp. Ma gandesc ca greseala e la calcularea sumei.

Algoritmul de back e varianta aia cu stiva de m+n in care generez toate aranjamentele cu repetitie dintre -1, 1. Deci inainte de a ceda tentatiei si a ma uita in sursa, dati-mi si mie o mana de ajutor cu calcularea sumei.

[•devilkind]

tu faci 2^(N+M), iar solutia oficiala e 2^N * M. Nu trebuie sa faci o stiva de N+M, trebuie sa faci o stiva de doar N elemente, adik incerci toate posibilitatile de a comuta liniile si apoi coloanele incerci sa le comuti inteligent

[•razyelx]

Ms mult. Am rezolvat-o si eu. Numai ca am facut-o in O(2^m * n). Oricum e acelasi lucru, dar mi s-a parut mai bine sa merg pe coloane, cu permutarile.