019 Pavare

[•Cosmin]

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.

[u-92]

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

[•pauldb]

Imi puteti spune cat va da pe testul asta?

Cod:

150 15 114
3 3
5 9
7 12
9 14
10 15
11 1
13 2
13 15
14 4
17 13
19 4
21 4
22 3
22 15
23 3
24 2
24 14
28 4
29 9
30 7
32 2
34 9
35 6
35 15
36 3
38 12
39 8
42 3
42 4
46 3
46 12
47 13
50 11
51 2
53 9
54 2
55 9
55 11
56 3
56 10
57 4
60 2
64 7
66 3
67 6
68 1
68 10
70 10
70 14
71 2
71 11
72 1
73 1
73 11
74 5
76 15
77 3
79 3
80 7
80 13
83 8
85 2
87 8
89 4
90 7
91 15
92 11
93 3
93 4
93 15
94 15
95 2
97 5
99 11
99 15
101 12
101 15
106 1
107 2
107 10
107 11
107 12
110 8
112 5
112 10
112 15
114 10
114 15
118 5
119 12
124 10
125 3
131 12
133 1
133 2
133 14
134 8
134 14
135 5
136 3
136 4
136 7
139 10
140 4
141 2
141 3
142 10
142 12
143 10
143 11
143 14
145 13
147 3
149 15

Multumesc.

[u-92]

474

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

[•pauldb]

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.

[•domino]

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).

[•adrianradulea]

imi da si mie cineva un test mai mic si cu smen l problema asta ca s m prind si yo unde gresesc.... pls 

[•varuvasi]

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

[•stef2n]

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

[•blue_phoenix]

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....

[•blue_phoenix]

474

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

Sigur pentru datele postate da 474? mie imi da 458

[•devilkind]

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.

[•blue_phoenix]

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...

[•devilkind]

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

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.

[•fireatmyself]

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
                                             

[•devilkind]

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

[•blue_phoenix]

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!

[•devilkind]

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

http://infoarena/problema/energii
http://infoarena/problema/homm
http://infoarena/problema/asmax
http://infoarena/problema/calatorie
http://infoarena/problema/subsir2
http://infoarena/problema/iepuri2

[•fireatmyself]

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

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

[...]
Functia compl1() cauta doua randuri consecutive libere (complet).
[...]

[•blue_phoenix]

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

[•freak93]

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)

[•Mishu91]

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).

[•pauldb]

Cred ca asta era ideea problemei de la inceput.

Tu ai facut in complexitate mai buna?

[•Mishu91]

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

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).

[•dushmi]

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?