infoarena

Aici puteţi discuta despre problema Pavare (http://infoarena.ro/problema/pavare).

ce este cu problema asta de obtin tot 50 p pe ia ???
exista cazuri particulare??
ce trebuie facut pt a obtine mai mult de 50 p :?:

..pai zi cum faci..

si ce se intampla la restul testelor ? TLE sau Wrong Answer ?


..chiar.. pt cine a rezolvat problema.. am inteles ca se face back pe prima coloana si in rest PD... si eu tot nu ma prind cum se face dinamica aia.. poate sa imi dea cineva vreun indiciu ?

Nu se face back pe prima linie... se face dinamica si back pe fiecare linie.. metoda se mai numeste si "dinamica + back" :).. gasesti mai multe detalii in handbook-ul cu solutiile de la IOI 2001 , cat si in solutiile de la CEOI 2002 unde s-a dat o problema asemanatoare.

:) mersi, o sa citesc solutile.. intre timp sunt uimit ca am scos 90 de puncte doar punand patratele la intamplare timp de 1.45 secunde :D

Eu zic sa le pui la intamplare 1.49 secunde... cine stie poate scoti suta.

..si eventual sa trimit de vreo 10 ori aceasi sursa, poate prind un timer bun :D

..nu, eram doar curios cam cat scot cu ceva randomizat

mersi pt informatii acum poate o sa iasa ceva  :wink:

Eu am luat 70 p pe ea.Ii o solutie foarte simpla.Incep din coltul stanga sus si parcurg matricea.Cum gasesc spatiu liber acopar.Asa iei 50p probabil multi au facut asa.Dar mai este o chestie si poti lua 70 p.Parcurgi din toate cele 4 colturi si pastrezi solutia cea mai buna.

Voua cat va da pe

84 e bun?

mie imi da altfel da oricum nu te lua dupa mina ca io nu am facut-o de 100 de puncte [-X

93

Multumesc bogdan. Faza era ca accesam o zona de memorie care nu exista si nu primeam segmentasion fault. Tipul bool se comporta cam ciudat.

Poate imi zice si mie cineva de ce nu merge varianta care ia 50 de puncte. Eventual sa-mi dea un exemplu pe care sa nu mearga.

   Reamintesc variannta: iei fiecare elemnt din matrice de 2*2 si vezi dak e liber dak e liber il acoperi.

Parerea mea e ca pui problema gresit. Gandirea "am un greedy, demonstrati-mi ca nu merge", e proasta. O rezolvare nu merge pana cand nu ai demonstrat-o. Deci spune-ne tu noua de ce crezi ca merge.

Bafta !

Nu stiu daca am inteles prea bine solutia ta. Merge pe exemplul urmator?

* . . *
. . . .
. . . .

Aici '.' reprezinta o zona ce poate fi acoperita. Daca tu acoperi prima posibilitate, ai:
* \ \ *
. \ \ .
. . . .

Unde '\' reprezinta o zona acoperita. Iata o solutie corecta:

* . . *
/ / \ \
/ / \ \

Vezi ca am pus 2 placi de 2 * 2.

Daca vrei indicatii la problema cauta problema Bugs de la CEOI 2002 parca.

edit: am vazut ca problema s-a rezolvat si in 0.02 secunde ptr cazul maxim...

nu ne spuneti si noua muritorii de rand cum se face? sau e cu jmen si atunci e interzis?

Te referi de exemplu la mine? :)
Am ceva genu N * 2 ^ M si nu e nici un jmen. Gandeste-te :) Good luck  :thumbup:

tocmai am citit postul legat de propunerea testelor de catre concurenti.. si aici cred ca s-ar putea aplica. am vazut mai sus ca se iau 50-70 puncte cu parcurgeri simple ale matricei. totodata, cred ca ar putea fi micsorata si limita de timp pentru a pica rezolvarile random :P

numai bine.

Nu cred ca la aceasta problema se poate lua punctajul maxim cu o rezolvare incorecta... Totodata, arhiva de probleme nu este tocmai un concurs la care sa fie nevoie de o departajare, deci nu vad nici o problema daca o solutie mai simplista va lua 60-70 de puncte. Totusi, daca doriti sa rezolvati problemele, trebuie sa atingeti 100 de puncte, nu mai putin:).

Pe langa asta in concurs nu ai vreme sa incerci toate variantele dubioase si sa vezi care ia mai mult deci e sansa mica sa prinzi 70 de puncte.

Desi .. daca nu ai altceva mai bun de facut .. :)

in ultimele 15-20 minute nu am avut altceva mai bun de facut  :D
testele 1,2,3,4,6,7,9 ar trebui modificate.. daca cineva e interesat sa-mi dea un pm..

acum nici chiar sa elimini toate testele mici. asa, vreo 40 de puncte ar merge cu bulaneli.

Mai u ... poate ca si pe testele tale, dupa vreo jumatate de an se gaseste cineva sa ia punctaj maxim cu 2 foruri pentru ca asa se intampla pe online judgeuri, nu poti sa faci tot timpul teste foarte dure pentru toate rezolvarile posibile si imposibile.

probabil ca asa este.. si daca tot nu se ia maxim cu o solutie gresita..

Imi puteti spune cat va da pe testul asta?


Multumesc.

474

ps: a stat o gramada sa-l rezolve pe calculatorul meu  :-k

Mersi. :) Atata imi dadea si mie. Aveam un bug [uitasem sa reinitializez ceva 0], dar l-am gasit.

Apropo de timpul de executie: si mie imi merge groaznic pe teste "rare", cum e cel postat mai sus. Imi ia 2-3 secunde pe putin. :|

Solutia oficiala este O(N*M*2^M) .. totusi s-a luat 100 si cu solutii mai putin eficiente.. in loc sa faci dinamica pe stari linie cu linie, mai bine se face element cu element (vezi solutia de la CEOI 2002 - Bugs).

imi da si mie cineva un test mai mic si cu smen l problema asta ca s m prind si yo unde gresesc.... ](*,) pls  :D

De ce nu intra O(N*M*2^M) in timp pe ultimul test?  ???
S-a redus complexitatea solutiei oficiale?

Nu cred. Tocmai am retrimis sursa si intra fara probleme: http://infoarena.ro/job_detail/169619. Incearca sa faci eficient operatiile alea pe biti.

Salut!...am "rezolvat" problema de ceva vreme, si pt datele de test pe care le dau eu, rezultatul pare bun...totusi iau 40p, pic la testele 3  5 7 8 9 10; daca puteti posta macar una dintre teste (si solutia),poate ma prind ce nu merge.... ](*,)

Sigur pentru datele postate da 474? mie imi da 458 :?

Testele oficiale nu o sa le primesti (face parte din politica Infoarena).

Da raspunsul la testele de pe forum este corect. Explica-ne cum ne faci si poate te vom putea ajuta.

Am doua functii principale: compl1() si compl2();
Am declarat un vector [151]; pe locul i se afla 0 daca randul i din matrice are cel putin un element; 1 daca e complet liber;
Functia compl1() cauta doua randuri consecutive libere (complet).
Daca numarul de linii al matricii e par, patratul de 2/2 nu poate avea coltul stanga sus pe o linie impara (e doar o observatie: daca se strica la un momendat ordinea in matrice, se creeaza spatii libere ce nu vor mai putea fi umplute==> nu mai gasesc solutia optima); daca numarul de linii e impar, patratul poate fi asezat oricum (oricum vor ramane spatii libere).
Functia compl2(), parcurge matricea si completeaza oriunde gaseste un spatiu de 2/2 liber;
Aplic acelas principiu si de jos in sus(completez cu compl2()si ijn oridinea de jos in sus);
Afisez numarul mai mare dintre cele doua solutii posibile(cel rezultat din prima parcurgere, si resp cel rez din cea de-a doua)
 :? Cam asta e rezolvarea mea...

Pai ce pot sa zic.. nu prea e bine :D.

Problema se rezolva cu dinamica pe stari (una din coordonate e mai mica decat 15 park). Citeste ce s-a mai scris pe acest topic, o sa gasesti mai multe sfaturi.

daca am inteles bine ce face comp1(), atunci ar trebui sa pice testul (patratele marcate cu 1 sunt patratele blocate):
0000            22222
0000    =>    22222
1100            1122
1100            1122

oricum, daca pe ala nu pica prima functie, sigur pe testul asta pica comp2(), deci iti pica tot programul:

10001              10221
00001              22221
00001     =>     22111
00001              00221
10001              10221
                                             

varule, ca sa ii pice tot programul trebuie sa ii pice ambele functii. Din ce am inteles eu a aplicat 2 greedyuri si ia solutia cea mai convenabila dintre cele 2. O abordare destul de buna uneori :-' poate chiar mai bine decat sa bagi solutia oficiala si sa o busesti :D

Ar fi mai bine sa incerc sa imbunatatesc (eventual sa refac) algoritmul pe aceeas idee, sau sa incerc metoda cu backtracking si programare dinamica?(back stiu, programare dinamica, nu)...puteti sa-mi spuneti cateva probleme mai usoare la care se foloseste cam aceeas idee? Multumesc! :D

Daca nu stii programare dinamica te sfatuiesc sa lasi ptr moment problema asta. Poti sa incerci urmatoarele probleme

http://infoarena/problema/energii (http://infoarena.ro/problema/energii)
http://infoarena/problema/homm (http://infoarena.ro/problema/homm)
http://infoarena/problema/asmax (http://infoarena.ro/problema/asmax)
http://infoarena/problema/calatorie (http://infoarena.ro/problema/calatorie)
http://infoarena/problema/subsir2 (http://infoarena.ro/problema/subsir2)
http://infoarena/problema/iepuri2 (http://infoarena.ro/problema/iepuri2)

adevarat varule, dar pe al doilea test nu intra in comp1().

Pe "energii" o stiu deja, am mai incercat-o...Multumesc pentru sfaturi! :D

Se pare ca problema asta se poate rezolva si in O(n*m*fibonnaci(m)) pt cei care cauta alte moduri de a o optimiza(numai fibbonaci(m) cazuri merita calculate din 2^m)

Cred că ar fi binevenit un test cu dimensiuni maxime si foarte putine bucăți bune, întrucât se poate lua 100 si cu complexitatea teoretică de O(4^M*N).

Cred ca asta era ideea problemei de la inceput. :)

Tu ai facut in complexitate mai buna?

Am făcut în O(2^M*N*M), și din ce văd pe forum, cam asta se cere :)

aveti cumva vreo idee daca O(N * M * 2 ^M) mai intra in timp? Ca eu tot incerc sa optimizez si nu prea imi iese...

Legat de solutia O(N * M * Fibonacci (M))  stiti cumva vreun articol / ceva de genul?

Testele nu au fost schimbate. Si tin minte ca am rezolvat problema cu o solutie avand complexitatea O(N*M*2^2M) (supraestimat).

Cred ca mai mult ca sigur o solutie avand complexitatea O(N*M*2^M) s-ar incadra in timp. Esti sigur insa ca asta e complexitatea solutiei tale?

Sunt destul de sigur.. adica am dinamica a[ i ][ j ][ k ] = pozitia i,j cu configuratia k ( 0 <= k <= (2^m - 1) ). Si pentru fiecare triplet (i, j, k) vad in o(1) in ce alte triplete  pot sa ma duc( sunt maxim 2 triplete in care pot ajunge).

Mie imi da bine pe mabele teste postate inainte dar tot iau 0 imi mai poate propune cineva niste teste.Multumesc anticipat.

Nu imi mai trebuie am luat 100 :yahoo: nu am luat in calcul ca pot sa existe linii intregi pe care nu poti sa pui nici un bloc
de ex

****
****
|*|*
*|*|
****
****
cu | am marcat zona stricata

Un test micut imi puteti da si mie, va rog?

Am intampinat o problema la evaluare. Cand trimit problema primesc pe borderou urmatorul mesaj:
Contactează autorul problemei: Evaluatorul nu a returnat un număr la stdout pe testul 1 (se ignoră spaţii, newline, etc)

Poate fi din cauza sursei mele sau este o problema cu testele?

Ar trebuie o solutie in O(4^M*N) sa mearga? Eu am facut o dinamica cu back pe fiecare linie, si tineam starea liniei anterioare. Ce-i drept, am facut-o intr-un mod mai "destept", facand dinamica "inainte", un fel de parcurgere BFS. A trecut cu 24 de ms pe ultimul test, cu mult mai repede decat solutiile in O(2^N*N*M). Totusi ma intreb care e logica solutiei oficiale optime?

Edit: Dupa o analiza mai atenta, am observat ca complexitatea algoritmului e mai apropiata de O(2^M*fib(M)*N).

Ar merge marita putin limita de timp. O solutie cu O(2^M * N * M) ia TLE daca nu e optimizata.