175 Demolish

[ditzone]

Aici puteţi discuta despre problema Demolish.

[•spatarel]

E clar ca fie testele fie enuntul sunt gresite...

Am gasit teste (9 si 10) in care exista dreptunghiuri de cost 0, iar in enunt scrie:

0 < C ≤ 200 000

Mai mult decat atat... am mai gasit ceva! Testul 6 nu respecta una din urmatoarele conditii (nu stiu exact care):

0 < DY
y1 < y2 (pentru cel putin unul dintre dreptunghiuri)

[•filipb]

Cum ai gasit asta??? Eu cred ca sunt corecte din cate imi amintesc de la generatorul de teste... O sa le verific in seara asta si o sa postez pe forum in caz ca e necesar.

                                                                              Filip b.

[•greco]

Pai e simplu sa verifci ceva in teste...

if (conditie) for ( ; ; );

Te uiti la monitor si vezi daca ai vreun TLE.

[•filipb]

Testul 6 este corect ( indeplineste ambele conditii ).
Enuntul se modifica astfel:

Cod:

0 ≤ C ≤ 200 000

in loc de

Cod:

0 < C ≤ 200 000

Nu modifica oricum cu nimic rezolvarea sau rezultatele. Sorry, este prima si ultima data

[•spatarel]

M-ati dezamagit . Nu ati modificat nimic in enuntul problemei...  

Eu am reusit sa iau in final 100 de puncte, insa initial ma obtinut doar 70 . Dupa ce am depanat ultimele buguri aveam 2 TLE (testele 9 si 10) si un RUN ERROR (testul 6).

Dupa o multime de submit-uri, am reusit sa-mi dau seama ca TLE-urile erau cauzate de dreptunghiuri cu costul 0 (si nu mi se pare normal sa am probleme din cauza unor astfel de teste, in special daca nu apar mentionate in enunt - de aceea este foarte important ca testele sa respecte restrictiile din enunt ).

In final, am corectat si testul 6 si am constatat ca sursa mea ar fi avut probleme cu dreptunghiurile cu proprietatea Y1 - DY + 1 > Y2 - 1. Oricum, eu mi-am corectat sursa, astfel incat sa functioneze si in unele conditii extreme...

Urmatoarele teste mergeau bine pe sursa mea veche:
Y1 - DY + 1 <= Y2 - 1 =>
Y1 <= Y2 + DY - 2 =>
Y2 < Y2 + DY - 1 =>
Daca 0 < DY atunci Y2 < Y2

Am gresit ceva?

Oricum, este la fel de posibil ca testul 6 sa aiba o alta proprietate ciudata, pentru care am luat aceal RUN ERROR, asa ca nu o sa mai insist. Dar, nu uitati sa modificati enuntul .

[•filipb]

Gata, s-a modificat

[u-92]

eu pentru fiecare y de la 0 la N gasesc costul minim a.i. sa am coordonata din dreapta y, iar pt acesta x`ul minim (folosesc un arbore de intervale).. totusi pe testele 2, 6 primesc run error iar pe 7 WA. am pus si long long, am marit dimensiunile vectorilor dar tot nu iau mai mult. un hint/o idee ceva, mi-ar fi de folos..

[•filipb]

Nu prea am inteles cum faci tu, dar se procedeaza cam asa: pentru o dreapta de baleiere verticala, presupui ca latura stanga a dreptunghiului tau de laturi (DX, DY) se afla pe aceasta dreapta. Acum trebuie sa afli care este cel mai convenabil segment de lungime DY pe OY, adica suma costurilor intervalelor curente care intersecteaza intervalul respectiv sa fie minim posibil. Pentru asta, ca la parcele, folosesti arbori de intervale.
Cand muti la stanga dreapta de baleiere scoti dreptunghiurile ( intervalele asociate lor de pe Oy de fapt ) care au depasit dreapta si bagi alte dreptunghiuri noi si iar calculezi cel mai bun interval pe Oy, etc.

[u-92]

ai descris exact modul in care am rezolvat-o eu

[•vladcyb1]

Trebuie folosit int64 in sursa ? Si eu pic testele 2,6,7 

[•filipb]

NU neaparat, eu nu am folosit in sursa mea.
E o coincidenta probabil, s-au luat deja multe punctaje maxime...

[•peanutz]

Imi spuneti o complexitate care ar intra, va rog? Eu m-am gandit la un O(n + f*n*lgn), dar nu asta nu cred ca intra. M-am gandit ca pentru fiecare punct pe y, sa aflu costul pentru segmentul y, y+dy, si fac asta doar cand fac update(ies sau intru intr-o ferma). Pot sa folosesc arborii de intervale ca sa aflu mai rpd segmentul de lungime dy de cost minim?

[•Marius]

O(M log N), dar daca folosesti coordonatele pe Ox ale dreptunghiurilor atunci poti scoate O(F log N). Pe Oy folosesti arbore de intervale, de unde O(log N) pe update si O(1) pe query.

[•pauldb]

Se poate face evaluatorul astfel incat sa dea mesaje diferite pentru cost gresit si pozitia fermei gresita?

[•DITzoneC]

Am modificat, dar difera doar mesajul, punctajul este acelasi.

[•margiki]

Se poate posta un test ?