|
Titlul: 175 Demolish Scris de: ditzone din Ianuarie 25, 2006, 21:58:06 Aici puteţi discuta despre problema Demolish (http://infoarena.ro/problema/demolish).
Titlul: Probleme cu testele sau enuntul Scris de: Dan-Constantin Spatarel din Februarie 12, 2006, 22:30:09 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: Citat 0 < C ≤ 200 000 Mai mult decat atat... am mai gasit ceva! Testul 6 nu respecta una din urmatoarele conditii (nu stiu exact care): Citat 0 < DY y1 < y2 (pentru cel putin unul dintre dreptunghiuri) Titlul: 175 Demolish Scris de: Filip Cristian Buruiana din Februarie 13, 2006, 10:01:16 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. Titlul: 175 Demolish Scris de: Tiberiu-Lucian Florea din Februarie 13, 2006, 11:33:17 Pai e simplu sa verifci ceva in teste...
if (conditie) for ( ; ; ); Te uiti la monitor si vezi daca ai vreun TLE. Titlul: 175 Demolish Scris de: Filip Cristian Buruiana din Februarie 13, 2006, 18:45:01 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 :P Titlul: M-ati dezamagit :(( Scris de: Dan-Constantin Spatarel din Februarie 13, 2006, 20:56:32 M-ati dezamagit :(. Nu ati modificat nimic in enuntul problemei... :thumbdown:
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 :wink:). 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 ;). Titlul: 175 Demolish Scris de: Filip Cristian Buruiana din Februarie 13, 2006, 21:38:15 Gata, s-a modificat :)
Titlul: Raspuns: 175 Demolish Scris de: u-92 din Aprilie 04, 2006, 18:07:05 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..
Titlul: Raspuns: 175 Demolish Scris de: Filip Cristian Buruiana din Aprilie 04, 2006, 18:32:13 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. Titlul: Raspuns: 175 Demolish Scris de: u-92 din Aprilie 04, 2006, 18:43:38 ai descris exact modul in care am rezolvat-o eu :)
Titlul: Raspuns: 175 Demolish Scris de: Vlad Berteanu din Iulie 24, 2006, 23:48:39 Trebuie folosit int64 in sursa ? Si eu pic testele 2,6,7 :eyebrow:
Titlul: Raspuns: 175 Demolish Scris de: Filip Cristian Buruiana din Iulie 25, 2006, 11:12:29 NU neaparat, eu nu am folosit in sursa mea.
E o coincidenta probabil, s-au luat deja multe punctaje maxime... Titlul: Răspuns: 175 Demolish Scris de: Andrei Homorodean din August 24, 2007, 06:58:55 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?
Titlul: Răspuns: 175 Demolish Scris de: Marius Stroe din August 24, 2007, 08:22:23 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.
Titlul: Răspuns: 175 Demolish Scris de: Paul-Dan Baltescu din August 31, 2007, 18:33:41 Se poate face evaluatorul astfel incat sa dea mesaje diferite pentru cost gresit si pozitia fermei gresita?
Titlul: Răspuns: 175 Demolish Scris de: Adrian Diaconu din August 31, 2007, 19:10:04 Am modificat, dar difera doar mesajul, punctajul este acelasi.
Titlul: Răspuns: 175 Demolish Scris de: Margeloiu Andrei din Februarie 28, 2016, 20:38:37 Se poate posta un test ?
|