002 Jocul Flip

[•warangel]

Cod:

Cod:

#include<stdio.h>
long mat[16][16];
long max =-1099999999;
int sol[16];
int n,m;
void citire()
{
	freopen("flip.in","r",stdin);
   scanf("%d",&n);
   scanf("%d",&m);
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
         scanf("%ld",&mat[i][j]);
}

long suma_col(int col)
{
	long s=0;int x;
   for(int i=1;i<=n;i++)
      {
         if(sol[i])x=-1;
         else x=1;
         s+=mat[i][col]*x;
      }
   if(s>0)return s;
   else return -s;
}

void do_max()
{
   int i;
   long max2=0;
   for(i=1;i<=m;i++)
      max2+=suma_col(i);
   if(max2>max)max=max2;
}
int add2sol()
{
   int poz=1;
   while(sol[poz]!=0)
      sol[poz++]=0;
   sol[poz]=1;
   //printf("poz: %d ; ",poz);
   return poz<=n;
}
void tip_sol()
{
   for(int i=1;i<=n;i++)printf("%d ",sol[i]);
   printf("\n");
}
int main()
{
   freopen("flip.out","w",stdout);
   citire();
   do
   {
      //tip_sol();
      do_max();
   }
   while(add2sol());
   printf("%ld",max);
   return 0;
}

Pct:

Cod:

Test  	Timp executie  	Memorie folosita  	Mesaj 	Punctaj/test
1	0ms	8kb	Ok!					10
2	0ms	8kb	Ok!					10
3	0ms	8kb	Ok!					10
4	8ms	204kb			Raspuns gresit		0
5	4ms	8kb	Ok!					10
6	56ms	208kb	Ok!					10
7	32ms	204kb	Ok!					10
8	604ms	184kb			Time limit exceeded.	0
9	0ms	8kb			Raspuns gresit		0
10	548ms	176kb			Time limit exceeded.	0
Punctaj total	60

Ideea e ca algoritmul meu are o complexitate mai mica decat cel cu backtracking dar nu reusesc sa iau decat 60pct...
L-am verificat, si reverificat, si tot asa pana m-am dat batut...
Va rog daca vedeti unde ar putea gresi sa-mi spuneti

Merci, Sorin

[•Florian]

Esti sigur ca iei in considerare toate posibilitatile? Explica-ne ideea de rezolvare, ca ia destul timp sa intelegem singuri din sursa. 

[•warangel]

Ok. Ideea algoritmului:

Iau toate posibilitatie de comutare a linilor. In loc sa folosesc un backtracking, folosesc un vector sol de n elemente (n nr de linii). Vectorul sol este initial 0,0,0... Apoi, pentru a  genera toate posibilitatile consider vectorul sol drept un numar un baza 2. Si la fiecare pas adaug 1 in sol[0] (consider ca numarul este scris invers). La fiecare solutie (adica dupa ce am adaugat 1) iau modul de suma pe fiecare coloana si o adaug la max2(suma matricei pentru sol respectiva). Iau modul pentru ca in cazul in care suma este negativa eu as avea posibilitatea sa comut acea coloana, pentru ca suma sa fie maxima. De fiecare data verific max2 cu max(suma maxima generala) si modific max(dupa caz).

Cam asta este explicatia algoritmului...

[•Florian]

Mi se pare cam dubioasa metoda de a calcula sol[]-ul. Nu garantez ca e gresita, insa acolo mi se pare putin aiurea. Ai putea sa iei fiecare numar x de la 0 la 2^nr_linii , si sa consideri sol[]-ul ca fiind reprezentarea binara a numarului x. Asa generezi cu siguranta toate posibilitatile, si e mai comod de calculat sol[]-ul. In rest, ideea e buna. Dar mai inainte de toate, declara matricea de 18*18 si trimite solutia asa cum e acum. [pt ca daca o declari de 16, o sa iti aloce memorie doar pentru pozitiile 0,1,2...15.] Spor!

[•warangel]

100. da, de la matrice era. Nu ma gandisem la asta. Merci mult.

Nu fac cu unsir de nr de la 0 la 2^n-1 pentru ca stiu de la permutari ca e mai performat cu vector deoarece faci mai putine operatii la adaugare de unitate decat la conversie in baza 2.

Am comparat timpii de la testul meu cu alte teste si la majoritatea am iesit in avantaj. Probabil daca mai lucrez la el o sa obtin timpi mai buni. dar nu are rost )

[•brainwashed20]

nu pricep de ce nu este compilatata.

[•gabor_oliviu1991]

main-ul trebuie sa returneze "int". pune int main in loc de void main si la sfarsit pune un return 0.

[•danalex97]

                            
NU IMI IESE!!!!!!!

  
NU IMI IESE!!!
HELP! 

[•sima_cotizo]

Iti inteleg supararea, dar asta nu e un motiv sa postezi asa. Nu cred ca are nimeni datoria sa iti citeasca sursa in pascal si sa-ti explice ce ai gresit. Incepe prin a citi acest topic cap-coada, poate gasesti cateva idei bune, iar apoi incearca sa faci debug pe o sursa cu o idee buna.

[•Necro]

Sal...ajutati-ma si pe mine va rog,ce pun in backtrack ?? ce specific? generez posibilitati.........
de ex la linii incerc sa le iau 1,(1 si 2),(1 si 2 si 3) , (1 si 3) , (2 si 3) , (2 ,3) si la coloane la fel....generez posibilitati de inmultire cu unu de felu asta?

[•Florian]

Topicul acesta are 6 pagini. Iti garantez ca vei gasi explicatia solutiei in toate cele 6 pagini. Succes! 

[•lsorin_94]

este pe aici cineva ce lucreaza in pascal??

[•gabitzish1]

Gasesti solutii prea superficiale !
De ce nu explici mai mult cum scoti -urile, dar prima data rezolva si tu problema sa vezi daca merge 

[•wefgef]

Ce tare ma amuza utilizatorii cu 3 posturi si 2 probleme rezolvate care ne explica intr-un mod agresiv cum se fac unele probleme la care ei nu au sursa, ca sunt gresite testele, ca nu sunt bune compilatoarele, ca rata impunge, etc.

[•marcelcodrea]

cum adica "in mod agresiv"?

Sa iti explic. Atunci cand comentezi pe un forum de specialisti hardware iti permiti sa folosesti orice fel de limbaj. Insa noi suntem o comunitate de oameni pasionati de software. Suntem mai gingasi, mai inteligenti si nu ne place sa distrugi corola de minuni infoarena.

Revenind la tonul serios :

Aici se pregatesc cei mai buni din tara pentru olimpiada de informatica. Oamenii astia au participat pe la loturi, pe la competitii internationale, stiu probabil mai mult despre algoritmi decat stii tu despre propriul tau corp(nu ma numar printre ei). Atunci cand un incepator le explica faptul ca gasesc solutii prea complicate la probleme elementare pentru nivelul lor, folosind  , nu le prea convine.

[•rusu_radu]

Este neceasara implementarea pe numere mari?  sau rezultatele incap pe long long int

[•Florian]

E suficient int.

[•rusu_radu]

Okay msm:D

[•oneway]

of...cred ca am citit o serie de aberatii...Este relativ usor..se calculeaza suma fiecarei coloane, respectiv linie. Coloanei/liniei cu suma minima i se va aplica flip. Trebuie sa aveti insa grija pentru ca atunci cand aplici flip la o coloana j elementele de pe linia i se vor modifica deci veti avea de testat 2 cazuri. Prima data cand testezi coloana pentru inceput, si cazul 2 cand testezi linia la inceput. Rezultatul final va fi maximul dintre cele 2 cazuri.

[•Florian]

of...cred ca am citit o serie de aberatii...

Eu tocmai am mai citit una :

Este relativ usor..se calculeaza suma fiecarei coloane, respectiv linie. Coloanei/liniei cu suma minima i se va aplica flip. Trebuie sa aveti insa grija pentru ca atunci cand aplici flip la o coloana j elementele de pe linia i se vor modifica deci veti avea de testat 2 cazuri. Prima data cand testezi coloana pentru inceput, si cazul 2 cand testezi linia la inceput. Rezultatul final va fi maximul dintre cele 2 cazuri.

[•adib]

cred ca imi scapa ceva simplu ...
am incercat toate testele care au fost puse pe forum .... si imi dau ok ....
daca poate cineva sa se uite peste sursa mea as fi recunoscator.
merci anticipat.

[•anna_bozianu]

@adib : Sper sa fi citit cu suficienta atentie sursa ta si sa nu gresesc in ceea ce spun.
           Efectul final al functiei reactsume ar fi urmatorul -> se schimba semnul pe o anumita linie si apoi
           se calculeaza suma fiecarei coloane in matricea modificata in vectorul x.
           Apeland apoi functia back este adevarat ca iei in calcul toate modurile in care s-ar putea schimba
           semnele pe coloane.
           Concluzia este simpla. Realizezi toate posibilele Flip-uri pe coloana dar corespunzator unui singur Flip pe linie.
           Probabil ca testele pe care obtii punctele sunt obtinute exact pe astfel de situatii particulare.
           Sper ca ai inteles ce am vrut sa spun. Oricum ideea de a lucra cu back mi s-a parut interesanta si poate fi
           un inceput pentru o rezolvare putin diferita de solutia oficiala a problemei.
         

[•adib]

done ... 1 nu calculam sumele cand trebuia
2 nu era buna ideea ... nu ii deajuns sa faci flip doar pe o linie odata ...

[•Bit_Master]

Nu conteaza daca faci flip pe o linie sau o coloana mai mult de o data. Gandeste-te la o valoare din matrice. Daca-i schimbi de 2 ori comutatorul pt linie, e ca si cum nu l-ai schimbat deloc.
Sa comuti linia i, pe urma coloana j, si pe urma din nou linia i, e ca si cum ai comuta doar linia j.

[•dornescuvlad]

cum se face backtracking ?imi scrieti si mie algoritmul in limbaj c++ va rog?