002 Jocul Flip

[•filipb]

De obicei eu primeam SIGKILL cand declaram prea multa memorie ( adica mai mult de 64 MB ). Sau sa nu depasesti memoria stivei daca faci recursiv ( 1 MB ) - asta e cel mai probabil.

[•Crusher]

Merci dar tot nu primesc mai mult de 10 pc. nu stiu ce sa fac. la toate exemplele formaulate de mine imi da corect(verificat pe hartie).

[•Marius]

Merci dar tot nu primesc mai mult de 10 pc. nu stiu ce sa fac. la toate exemplele formaulate de mine imi da corect(verificat pe hartie).

E clar ca nu ai o solutie corecta! Daca ai N linii poti sa folosesti bitii de 1 din reprezentarea binara a numerelor din [0, 2^N-1] pentru un flip   , fara backtracking si stive!

[•Crusher]

imi poate spune cineva la exemplul
3 3
10 -2 -3
1 3 4
5 -1 -1
cat este suma maxima?

[•bogdan2412]

imi poate spune cineva la exemplul
3 3
10 -2 -3
1 3 4
5 -1 -1
cat este suma maxima?

28

[•Crusher]

merci. Asa imi da si mie! Inseamna ca ce face programul e bine. Dar tot nu-mi dau seama de ce nu primeste numai 10 pc. O sa incerc sa dau si numere mai mari sa vad daca acolo nu o da in bara.

[•alberte]

Am facut problema si am luat 80 de puncte, doua teste imi ies din timp, se poate sa fie din cauza ca folosesc pascal si nu c++? Ce ar trebui sa fac?

[•wefgef]

intra si in pascal lejer. incearca sa fac ce a zis marius mai sus: sa te folosesti de reprezentarea binara a numerelor din [0, 2^N-1].

[•drigish]

Imi da bine si la testul anterior, si la cel din problema. Dar totusi iau WA la toate.
La testul asta suma e 79 ?
7 3
10 -2 -3
1 3 4
5 -1 -1
5 6 -9
7 15 -8
-5 9 13
5 6 7

[•cos_min]

mie imi da 67. [cu sursa de 100]

[•Programmer01]

Imi da bine si la testul anterior, si la cel din problema. Dar totusi iau WA la toate.
La testul asta suma e 79 ?
7 3
10 -2 -3
1 3 4
5 -1 -1
5 6 -9
7 15 -8
-5 9 13
5 6 7

Conform algoritmului meu (pentru care am obtinut 100 p.) raspunsul este tot 79, dar vazand ce timp ai obtinut pentru fiecare test (0.01s) am ceva dubii in legatura cu algoritmul tau.

[•drigish]

Totusi cat da 67 sau 79 ?
Algoritmul meu verifica fiecare coloana, apoi fiecare rand, si daca suma pe vreun rand sau coloana e mai mica sau egala cu 0 inmulteste cu -1. Cand suma pe fiecare rand, respectiv pe fiecare coloana e mai mare ca 0 se opreste. Probabil e ceva gresit la el, dar momentan nu-mi dau seama ce .

[•Programmer01]

Din moment ce 79>67 si in contextul problemei ne trebuie o suma cat mai mare, teoretic 79 este corect.
Vezi cat iti da petru
3 3
12 -4 -5
2 5 7
7 -2 -2
si apoi posteaza aici.
Dupa algoritmul tau cred ca da 22, dar corect este 42.
Citeste toate posturile de mai sus. O sa gasesti multe indicii.
 

[•drigish]

42 imi da... daca vrei iti dau un pm cu sursa

[•hitmann]

42 imi da... daca vrei iti dau un pm cu sursa

Trebuie sa intelegi ca nu poti ajunge la o solutie maxima (optima) printr-o astfel de metoda, e adevarat poti prinde cateva teste dar asta doar din noroc. Ai nevoie de o tehnica care sa te conduca catre o solutie optima, in cazul de fata backtracking e cel mai la indemana din cauza restrictiilor lejere. Rezolva problema prin backtracking nu te mai chinui cu greedy, deoarece tehnica greedy nu ofera o solutie optima doar cand poti demonstra matematic acest lucru

[•drigish]

Momentan am luat 30 pe sursa si ma multumesc cu atat pana mai invat ceva informatica. Ms pt ajutor.

[•Marius]

Momentan am luat 30 pe sursa si ma multumesc cu atat pana mai invat ceva informatica. Ms pt ajutor.

Nu te multumi cu putin! 

[•andy_89]

ma fratilor!!!! problema e foarte simpla!! s-a dat acum cateva zile la dan barbilian. ca sa rezolvi problema trebuie sa verifici pe fiecare linie, respectiv coloana, daca suma elementelor negative in modul este mai mare ca suma elementelor pozitive. daca e asa inmultesti toata linia cu -1.(acelasi lucru si pt coloane)       
PS: nu e vorba de nici o formula, cum zic altii!!!!

[•filipb]

Nu e asta solutia corecta intotdeauna. Trimite in arhiva de probleme sa vezi cate puncte obtii cu solutia asta.

[•RavenX86]

Backtracking 100% 

[•portocala]

Daca faci cu back ajunge la 4294967296 cazuri..maxim...nu garantez ca iti intra in timp...

[•devilkind]

backu nu e 100% ci doar 50% si intra in timp.

[•BlackElf]

I. M-am gandit, cum s-a mai zis, sa fac suma de negative si suma de pozitive si daca e mai mare atunci FLIP. La fel, s-a mai spus ca asta nu e solutie (cand faci FLIP strici alte sume care ar putea fi abordate mai "eficient" - dai FLIP la alea, o "sacrifici" pe asta... ma rog, intelegi ideea)

II. Backtracking - asta pare a fi cel mai logic... dar totusi... de ce sa te complici? Asa ca ajungi la III.

III. Dai FLIP doar la o coloana si o linie nu? Atunci de ce sa nu iei doua for-uri si pentru fiecare linie si fiecare coloana sa dai FLIP, calculezi suma si voila.

PS: Totusi, nu am incercat deci... poate vorbesc in dodii.

[•devilkind]

[Dai FLIP doar la o coloana si o linie nu?]

NU. poti sa dai flip la oricate linii si la oricate coloane.

[•BlackElf]

Ah, atunci cade III. Clar Backtracking Era mai interesant fara