002 Jocul Flip

[•Adix]

A mea ar solutiona cu succes datele alea de intrare .

O solutioneaza ?  .. daca da incearca si asta ..

Cod:

3 3
2 -3 3
4 0 -5
3 20 7

Ar trebui sa iti afiseze 35 dar raspunsul corect e 37.Daca iti da 37 incearca sa faci transpusa matricii asteia si vezi ce rezultat iti da . Daca tot 37 iti da inseamna ca exemplul meu nu e bun 

[•smith_s9]

Ufff... da... da 35. De ce, nu stiu. Oricum, am incercat sa fac pe foaie problema. Uite cum am mers:

Flip la a doua linie.

Cod:

2 -3 3
-4 0 5
3 20 7

Flip la prima coloana.

Cod:

-2 -3 3
4 0 5
-3 20 7

Flip la prima linie.

Cod:

2 3 -3
4 0 5
-3 20 7

Care da 35. Nu vad cum as putea obtine 37 ...

[•Adix]

of scuze .. greseala mea .. vroiam sa zic ca s-ar putea sa iti arate 33 si raspunsul corect e 35 nu eram atent cand am scris postul .. se pare ca nu e exemplul meu bun.. scuze de deranj

[•smith_s9]

Ufff... scuze si eu de deranj, am facut niste greseli si imi dadea 35 din greseala. Totusi erau greseli in flip.in. Da, imi da 33 si vad acum unde e greseala. Totusi, nu ma las pana nu o rezolv fara backtracking. Scuze din nou, iar am fost neatent, ca de obicei .

[•Adix]

Totusi, nu ma las pana nu o rezolv fara backtracking. .

Daca reusesti de 100 vreau si eu sursa :

[•IronWing]

M-am chinuit ceva timp sa rezolv aceasta problema. O prima idee ar fi sa generezi toate combinatiile in care poti inmulti liniile cu -1 sau 1 ( inmultirea cu 1 se face inmultind de 2 ori cu -1). Apoi, dupa fiecare combinatie generata sa verifici fiecare coloana daca suma sa negativa si daca da sa ii faci flip.
O problema ajutatoare ar fi generarea tuturor combinatiilor de 0 si 1 de lungime n.

Cod:

...

[Editat de moderator: nu mai posta cod asa explicit. Cei care stiu cum se genereaza se descurca sa implementeze singuri. Poti da indicii sau sa explici cum se genereaza daca chiar vrei]

[•razyelx]

nu am citit pe aici pre multe postu-ri numa primele.. as vrea sa stiu fara backtracking nu se poate?

[•Bluedrop_demon]

Daca permite evalutaorul marimea sursei, poti face cu precompilare. Generezi toate combinatiile de 1 si 0 de lungime 16 si apoi verifici pentru un n dat.

Dar backtracking-ul se comporta exemplar, si te-as sfatui sa nu te complici cand nu e necesar! 

[•razyelx]

eu mi-am format un algoritm pe care iau numa 30  de pct. suna cam asa... Fac suma elementele de pe coloane daca e sub 0 inmultesc coloana cu -1 la fel si cu randurile... pt exemplu merge  . smecher nu? as dori sa imi spuneti care e bugg-ul in gandirea mea? adik am eu cateva indei dar... nu sunt sigur..

[•sima_cotizo]

Ce faci tu e un greedy... O sa iti zic ce a zis si Greco in alt thread, "nu intreba ce e gresit, mai bine demonstreaza de ce e bine!"... in general greedy-ul buseste... aici din cate imi aduc aminte e un back + o dinamica : o dinamica iti face intotdeauna solutia optima (daca e corecta ) iar backul verifica toate variantele... in schimb cu greedy speculezi...

[•devilkind]

smecher nu?

Nu e nimik smcher in ce ai gandit tu ). Daca te uitai pe posturile anterioare ai fi vazut ca s-au mai gandit mai multi la ideea asta si au trebuit sa renunte ptr ca NU este o solutie corecta. Ce faci u e 100% greedy, si cum a zis si sima cotizo acesta nu este corect. Daca postezi pe forum o demonstratie matematica corecta la greedyu tau eu promit ca iti voi gasi bugul in asa fel incat as iei 100

[•Omega91]

eu mi-am format un algoritm pe care iau numa 30  de pct. suna cam asa... Fac suma elementele de pe coloane daca e sub 0 inmultesc coloana cu -1 la fel si cu randurile.

Recunosc, asta este prima rezolvare care mi-a venit in minte. Dar am 2 exemple care nu merg cu metoda asta:

  5   -1    5  5 5
  5   -1    5  5 5
-1  100 -1  -1 -1
  5   -1    5  5  5
  5   -1    5  5  5
se comuta linia 3 si coloana 2.

-1 10 10 10
-1 10 10 10
100 -1 -1 -1
-1 10 10 10
200 -1 -1 -1
-1 10 10 10
aici sunt liniile 3 si 5 si coloana 1.

ma rog, in exemplele astea, toate elementele devin in final pozitive, dar nu-i obligatoriu.

[•C11H17NO3]

OK, dupa ceva incercari 30, 70, 90, 100.
Nu am facut cu backtracking, desi e clar ca asa ar fi cel mai bine.
Am facut un soi de greedy cu perturbari random - deci un algoritm probabilist.
Adica, incerc sa maresc maximal suma pe principiile de bun-simt, pe linie si coloana - cand chestia se poate, flip. In caz ca nu se poate mari suma, atunci coafez matricea pseudoaleator de cateva ori si continui cautarea.
Cea mai interesanta chestie la solutia mea cred ca este faptul ca merge . Tehnic vorbind, cred ca este asemanatoare cu random-restart steepest ascent hill-climbing: http://en.wikipedia.org/wiki/Hill_climbing doar ca nu face random-restart, ci random-sidestepping, random-jiggle, sau cam asa ceva. Oricum, traiasca si-nmulteasca(-se) random seed-ul de pe masina de evaluare .

O sa incerc acum si cu backtracking si... mai am o idee .

Alin

[•wefgef]

Nu este deloc greu sa implementezi un back la problema asta .

Pana atunci, long live ciucuielile!

[•C11H17NO3]

Tocmai, nu e deloc greu cu back De aia ma gandeam la ceva mai interesant, in masura in care se va putea.

Alin

[•c_sebi]

am o intrebare, desi e offtopic...

am facut declaratia

Cod:

long long  int SMax=-32000000000;

si la compilare obtin eroarea

Cod:

user.cpp:4: error: integer constant is too large for 'long' type

 

ma poate lamuri cineva pls?

[•crawler]

ai putea sa incerci

Cod:

long long  int SMax=-3200000*10000;

[•cos_min]

Incearca :
long long  int SMax=-32000000000LL;

[•c_sebi]

au mers ambele varinate pe care mi le-ai recomandat... ms de ajutor... 
dar poate imi explica cineva care era problema...

[•Florian]

Problema era ca nu poti atribui direct unei variabile un numar mai mare de 32 biti 

[•DITzoneC]

Daca nu pui LL la sfarsit compilatorul presupune ca este int dar -32000000000 nu se incadreaza in timpul int.
LL la sfarsit semnifica faptul ca este vorba de o constanta long long.

[•frEak-]

O((2^m) * n)

ce inseamna O ala ? ;D
sa nu mor prost nu de alta 

(nu e offtopic ca a montionat cineva chestia asta acu vreo 70 de posturi xD)

[•devilkind]

Constanta . acel 2^m*n reprezinta un numar de operatii destul de orientativ.

[•stef2n]

Constanta? Notatia O este pentru o functie ce exprima dependenta ordinului de crestere al timpului/memoriei in raport cu variabilele date.

[•Bogdan_tmm]

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;