|
Titlul: 267 TreiD Scris de: Bogdan-Cristian Tataroiu din August 11, 2006, 19:10:51 Aici puteţi discuta despre problema TreiD (http://infoarena.ro/problema/treid).
Titlul: Raspuns: 267 TreiD Scris de: Savin Tiberiu din August 11, 2006, 20:18:45 nu inteleg fac brut pe linii, si dinamica pe coloane si totusi iau 0 puncte, toate testele mele merg.
ce ar putea fi gresit?? iata cum fac: fixez 2 linii, si apoi retin in v[ i ] - suma elementelor de pe coloana i, care se incadreaza intre cele 2 linii, v[ i ] il calculez in o(1) folosind sume partiale, iar apoi aplic algoritmu de suma maxima in o(n). dupa ce am aflat primu dreptunghi, initializez toate elementele acestuia cu -40000000 ptr a fi sigur ca nici un element de-al acestuia nu va fi gasit in urmatoarea suma maxima pe care o calculez. Titlul: Re: 267 TreiD Scris de: Sima Mihai Cotizo -vechi din August 11, 2006, 20:18:57 aici mi-a dat o eroare ciudata:
Cod: long i, j, rez=-INF, ; Titlul: Re: 267 TreiD Scris de: Bogdan-Cristian Tataroiu din August 11, 2006, 20:34:34 devilkind: ce-ai facut tu e greedy... iei tot timpu dreptunghiul de suma maxima.. asta nu-ti garanteaza faptul ca la final vei avea suma maxima a celor 3... gandeste-te mai mult la rezolvare
Titlul: Raspuns: 267 TreiD Scris de: Savin Tiberiu din August 12, 2006, 14:11:19 pai sa vedem eu trei dreptunghiuri de suma X,Y,Z dak as alege alte 3 numere X1, Y1, Z1, atunci x1<=x; y1<=y; z1<=z si deci x1+y1+z1<=x+y+z;
akum ca ti-am demonstrat greedyu meu (cel putin am incercat) v-as ruga sa imi ziceti de nu ar merge. Titlul: Raspuns: 267 TreiD Scris de: Andrei Grigorean din August 12, 2006, 14:14:03 4 4
50 50 50 50 -1 -1 -1 -1 50 50 50 50 -1 -1 -1 -1 50 50 50 50 Titlul: Raspuns: 267 TreiD Scris de: Savin Tiberiu din August 12, 2006, 14:26:40 aha akuma am reusit sa inteleg. mersi
Titlul: Răspuns: 267 TreiD Scris de: Paul-Dan Baltescu din Iulie 02, 2007, 10:52:30 In exemplu ar trebui N=6.
Titlul: Răspuns: 267 TreiD Scris de: Adrian Diaconu din Iulie 02, 2007, 13:50:40 Am sters o linie, ca sa se potriveasa cu explicatia.
Titlul: Răspuns: 267 TreiD Scris de: Savin Tiberiu din Iulie 29, 2007, 15:20:20 testele 3,12 si 17 au ceva particular in comun? iau WA pe ele
Titlul: Răspuns: 267 TreiD Scris de: Cosmin Negruseri din Iulie 30, 2007, 00:45:23 Poate ai scapat o configuratie relativa a celor trei dreptunghiuri.
Titlul: Răspuns: 267 TreiD Scris de: Andrei Homorodean din August 20, 2007, 19:13:11 Tiberiu, cum se comporta algoritmul tau cand trebuie sa determini submatricea maxima a unui dreptunghi cu o singura coloana? Eu luam wa pe timus la o problema in genu asta. Am pus max = s[1], si a mers.
Titlul: Răspuns: 267 TreiD Scris de: Visan Radu din Decembrie 06, 2012, 21:45:18 Limita de timp cred ca e cam mica. Am O(N ^ 3), ce-i drept, cu o constanta maricica, dar ia TLE pe multe teste. Am vazut ca in afara de 2 surse, celelalte care au 100 au in jur de 400-500 ms pe ultimele teste. Cu o solutie incompleta iau 75, iar pe ultimele teste intra la limita, cu o solutie completa iau TLE la greu.
Titlul: Răspuns: 267 TreiD Scris de: Andrei Grigorean din Decembrie 07, 2012, 01:36:15 Am marit limita la 0.3 secunde.
Titlul: Răspuns: 267 TreiD Scris de: Visan Radu din Decembrie 07, 2012, 14:44:11 Mersi mult! :banana:
Are ceva special testul 8 de iau incorect doar pe el? :aha: LE: 100 Titlul: Răspuns: 267 TreiD Scris de: Radu-Andrei Szasz din Decembrie 13, 2012, 15:53:33 Salut!
Mi-ati putea da niste teste cu cazuri mai speciale? Toate testele care mi le-am dat(si au fost destul de multe) le-am luat, dar iau 80 cu WA. Mersi anticipat! |