problema "dreptunghiuri"

[•nemesis]

nu vreau sa jignesc pe nimeni, dar mi s pare mie sau nimeni nu a luat nici macar un test la problema dreptunghiuri de la cls aX-a... mie imi da de gandit...
eu cred/sunt sigur cat de cat k sunt probleme in evaluatorul dvs la aceasta problema...
 

[•Cosmin]

Nu cred ca este nici o problema cu evaluatorul, avem vreo 5 surse diferite facute de doi oameni care dau acelasi rezultat. Primul test este cu N in jur de 14, deci daca faceati solutia cea mai simpla nu cred ca se incadra in timp si trebuiau salvate rezultatele. Vor aparea in curand solutiile pe site.

[•nemesis]

da chiar NIMENI nu a facut nici un test.... dak ai timp te rog posteaza aici un test mai simplu sa imi testez sursa plz...

[•Cosmin]

Pai un brute force poti sa iti faci si lasi sa ruleze pana obtii rezultatul pentru teste pana in jurul lui 20 si dupaia submitezi constante si o sa vezi ca iti merge un test. Dupa ce vei citi solutia probabil vei lua 100 de puncte usor.

[•nemesis]

si cam cand am placerea sa citesc solutiile? la ce ora le postati?

[•dobre]

Pai problema avea o gramada de chestii... Trebuia sa fii atent la dreptunghiurile care nu sunt paralele cu OX, OY . Aveam o idee... dar ceva nu imi iesea klumea in situatia aia... :cry:  . Si intradevar cred ca toata lumea a luat 0...

[vladut.forum]

mi-e mi s-a parut o comb. prin pd
numa ca nu mi-a iesit recurenta si nici n-am implementat numere mari

[•Cosmin]

Nu trebuiau nr mari pt ca numarul de dreptunghiuri era de ordinu n^4 sau cam pe acolo.

[vladut.forum]

aa. da... scuze

da tot nu mi-a iesit recurenta

eu facusi ceva de genu

pt [i,j] tineam v[j]=numarul de dreptunghiuri care se pot desena pe o matrice i,j fara contur (adika fara dreptunghiul [j])
si v[j]=v[j];
la fiecare pas i,j, incadram dreptrunhiul de latura [i,j-1]
in asta mare [i,j] si adaugam si numarul de incadrari (adika conturul lui i,j-1, ca in v[j-1] nu numaram si dreptunghiul de pe contur (de latura i, j-1)) si mai adaugam acum noile triunghiuri care nu sunt paralel cu Ox si Oy (in O(n))

in total iesea cred ca n^3

dar am gresit ceva p'acolo

[•Cosmin]

Eu nu am facut cu recurenta. Am vazut pentru un dreptunghi cu laturile paralele cu axele de coordonate, cate dreptunghiuri care nu au laturile paralele cu axele de coordonate se inscriu in el. Si de aici incolo daca nu ai rabdare pana apar solutiile te mai gandesti tu.

[vladut.forum]

aa...daa
ai dreptate, nu trebuia recurentza
  -aiurea