002 Jocul Flip

[•fluffy]

Aici puteţi discuta despre problema Jocul Flip.

[•itrocan]

N-ar strica sa dati mai multe exemple...

[•silviug]

Problema lui Mircea e buna.. desi e simpla.. trebuie sa fie si probleme de astea pe site pentru cei mai slabi care nu pot face chestii avansate.. poate nu-ti place tie dintr-un mod pur personal, nu stiu.. Sincer eu nu agreez problemele de formule si nu ca nu m-as prinde... ci pentru ca nu consider aceste probleme de 'informatica'.. tot ce trebuie sa faci e sa gasesti formula si apoi sa bagi repede numerele mari (eventual).. total inutil .. sincer eu nu as da la un baraj pentru IOI o asa problema.. decat daca e se rezolva cu dinamica (vezi gardx a lui Andreica de la loturile din 2002, x=4 sau 5).. sa-mi spuneti si mie cand vedeti la IOI o problema de formula, la americani sau mai stiu eu pe unde.. as spune ca e spefic romaneasca faza cu formulele...

[•itrocan]

Cum putem propune probleme? As avea cateva sugestii...

Intr-adevar, sunt prea multe probleme cu formule. Anul trecut, la clasa a VIII-a, prima problema cred ca a fost facuta mai degraba plecand de la formula...

[•Figure09]

chiaaaaaaaaar... cum putem propune probleme...  

[•DreamWorks]

Asta-i o problema cu formula ? Eu am facut-o prin comparatii intre suma nr negative si suma nr pozitive dintr-o coloana respectiv linie. Impropriu spus "am facut-o" pentru ca evaluatorul nu mi-a dat decat 40 pcte ! Insa chiar nu vad unde-i greseala in rationament ! Este pur si simplu logic ! Si totusi evaluatorul pare sa aiba o problema cu rezolvarea asta. De-asta am apelat la acest forum...
Eu tot fac flip pana cand suma numerelor negative (in valoare absoluta) devine mai mica decat suma nr pozitive de pe orice coloana si linie...]

Any other ideas where I've been missing out ?  

[•wickedman]

Eu tot fac flip pana cand suma numerelor negative (in valoare absoluta) devine mai mica decat suma nr pozitive de pe orice coloana si linie...]

pai nu trebuie sa fie doar mai mica ci cat mai mica intrucat iti cere suma totala maxima

nu stiu exact ce si cum faci dar poate te ajuta sa-ti spun ca problema se face cu backtracking in complexitate O(2^N). succes!

[•ciprycus]

ce se pune in stiva?

[•SergiuH]

O linie sau o coloana se poate inmulti o singura data cu -1?  Sau putem sa le inmultim de cate ori ne taie capu?

[•domino]

O linie sau o coloana se poate inmulti o singura data cu -1?  Sau putem sa le inmultim de cate ori ne taie capu?

De cate ori vrei, dar are vreun sens sa faci de mai multe ori?  

[•adi_nm]

Fac flip pe coloane de suma negativa si obtin o suma imbunatatita.
Fac flip pe linii de suma negativa si obtin o suma imbunatatita.

Daca ma opresc aici, evaluatorul imi da 20 de puncte.

Daca reiau procesul de calcul, pana cand nu mai am sume negative pe linii sau pe coloane evaluatorul imi da 30 de puncte.

Si ma asteptam matematic ca problema sa mearga.

Unde poate fi problema?

[VladS]

Pentru a lua 100 trebuie optimizata operatia de calcul al sumei?
Cam ce complexitate e recomandata (pentru aceasta operatie)?  :lol:

[•mcbrood]

a zis cineva ceva de o formula...sunt curios de o idee asupra formulei dc exista. o sa implementez un back sa vad cate puncte ia si mai postez aici rezultatele.

[•silviug]

Nu e nici o formula la mijloc. Se foloseste tehnica backtracking.. totusi backtracking-ul direct nu va lua prea multe puncte. El se poate optimiza daca observi un lucru destul de simplu. Mai posteaza daca ai nevoie de ajutor .

[•llucky]

deci... am incercat sa o rezolv fara backtracking si nu inteleg unde gresesc.... eu am gandit in felul urmator... fac o parcugere pe coloane, si daca pe vreo coloana suma elementelor este mai mica decat zero ... o intorc.... dupa care fac o parcurgere pe linii si la fel daca gasesc vreo suma mai mica ca 0 o intorc si reiau parcurgerea matricii pe coloane...... si totusi am obtinut 0 puncte... nu vad cum sar putea face cu back... mati putea lumina va rog?

[later edit]
sau ati putea macar sami mai dati niste teste? sa vad unde gresesc cu logica mea? multumesc

[•silviug]

Nu am timp sa creez un test pe care "logica ta" sa pice. Ai incredere in mine si crede-ma pe cuvant ca nu este corecta. Dar cum aschia nu sare departe de trunchi, extinzand un pic ideea ta, ce-ar fi daca ai genera toate posibilitatile de a inmulti cu 1/-1 pe coloane si apoi sa faci ceva pentru linii ? Te ajuta cu ceva sugestia mea ?

[•llucky]

am sa incerc... nu imi trebuie neaparat sa creezi un test... macar cele de la evaluator pt ca acelea lea picat... oricum.. o sa vad ce pot face... sper sa imi iasa

[later edit]
poate is mai incet eu de minte... deci sa bag un backtracking in care in stiva sa retin care coloana am inmultito cu -1 si apoi sa mai bag unu pt linii? asta nu ar depasi timpul de executie?  

[•Figure09]

am sa incerc... nu imi trebuie neaparat sa creezi un test... macar cele de la evaluator pt ca acelea lea picat... oricum.. o sa vad ce pot face... sper sa imi iasa

[later edit]
poate is mai incet eu de minte... deci sa bag un backtracking in care in stiva sa retin care coloana am inmultito cu -1 si apoi sa mai bag unu pt linii? asta nu ar depasi timpul de executie?  

ideea e ca tu faci back doar pe linii, in 2^N (n<=16) si verifici ceva pe coloane, shi ai complexitate totala O(N*2^N) care itzi intra lejer in timp.

[•calinux]

Eu am incercat pana acum un back destul de simplu in care tineam o stiva (m+n), deci si pt. linii si pt. coloane. Drept urmare nu am luat decat 40 de puncte. Dar citind posturile mi-am dat seama ca nu am abordarea corecta. Dar totusi, nu prea imi dau seama cum as putea face. Deci pt. fiecare coloana fac un back pe linii si verific ceva pe coloane? Dar totusi ce? Am incercat sa iau fiecare coloana si sa ii fac flip si sa fac back pe coloane pt. ea iar apoi sa iau suma maxima, dar nici asa nu a mers. Poate ati putea sa-mi dati un sfat.

[•pirosl]

Deci pt. fiecare coloana fac un back pe linii si verific ceva pe coloane? Dar totusi ce?

Poti sa verifici daca suma pe coloane nu e mai mica decat 0 ?!;)

[VladS]

Ai putea citi solutiile problemelor de la ONI 2002 clasa a IX-a. Poate te ajuta.
Succes.

[•calinux]

Gata ... am reusit si eu .... Multumesc tuturor care mi-au raspuns la post..... Sunteti cei mai tari!  

             

[•hitmann]

Eu am incercat pana acum un back destul de simplu in care tineam o stiva (m+n), deci si pt. linii si pt. coloane. Drept urmare nu am luat decat 40 de puncte. Dar citind posturile mi-am dat seama ca nu am abordarea corecta. Dar totusi, nu prea imi dau seama cum as putea face. Deci pt. fiecare coloana fac un back pe linii si verific ceva pe coloane? Dar totusi ce? Am incercat sa iau fiecare coloana si sa ii fac flip si sa fac back pe coloane pt. ea iar apoi sa iau suma maxima, dar nici asa nu a mers. Poate ati putea sa-mi dati un sfat.

M+N sau m*n ? explica te rog putin raspunsul

[•filipb]

Complexitatea optima e O((2^m) * n). De aici e destul de evident cum se face...

[Later edit]: calinux se referea ca tine o stiva de lungime (m+n) adica genera toate posibilitatile de a face flip la linii si coloane intr-o matrice MxN ( genera toate submultimile linii si coloane )

[•Crusher]

Imi explica cineva ce ii cu RUN ERROR - SIGKILL ca tot asta o primesc la fiecare test!