|
Titlul: 198 Custi Scris de: Mircea Pasoi din Martie 18, 2006, 12:50:28 Aici puteţi discuta despre problema Custi (http://infoarena.ro/problema/custi).
Titlul: 198 Custi Scris de: Adrian Vladu din Martie 18, 2006, 13:53:30 As avea de obiectat in ceea ce priveste aspectul enuntului si erorile gramaticale care nu fac, din pacate, decat sa degradeze imaginea celui care a propus-o. Propunatorii sunt rugati ca de acum incolo sa aiba putina grija la asta.
In rest, keep up the good work! :thumbup: Titlul: 198 Custi Scris de: vladut.forum din Martie 18, 2006, 14:47:52 :P dap, adevarat.... my bad
o sa am grija pe viitor!!! 8) Titlul: 198 Custi Scris de: cristi8 din Martie 18, 2006, 18:01:18 cum ati facut problema de obtineti timpii asa mici ? (sub 0.3 sec)
eu nu imi dau seama cum as mai putea imbunatatii sursa mea si ajung peste 0.3 secunde (am trimis de 2 ori, nu e din cauza "timpilor orientativi") eu fac asa: citesc element cu element, nu-l retin intr-o matrice, ci intr-o variabila locala, fac O(1) calcule sa obtin o valoare care o pun intr-o matrice. dupa aia fac N operatii, dupa care afisez solutia Titlul: 198 Custi Scris de: Gogu Marian din Martie 18, 2006, 18:11:22 La o complexitate O(input) factorul dominant tot timpul e citire datelor. Ca sa citesti N*N numere iti ia mult mai mult decat sa faci ceva cu ele in RAM.
Fa o citire cu fread si cred ca o sa ai timpi mult mai mici. Titlul: 198 Custi Scris de: Marius Stroe din Martie 18, 2006, 18:40:20 Citat din mesajul lui: gogu La o complexitate O(input) factorul dominant tot timpul e citire datelor. Ca sa citesti N*N numere iti ia mult mai mult decat sa faci ceva cu ele in RAM. Fa o citire cu fread si cred ca o sa ai timpi mult mai mici. Ce vrei sa zici cu citirea fread ? Scuze. :-s Titlul: 198 Custi Scris de: Gogu Marian din Martie 18, 2006, 19:00:10 fread e o functie C asemanatoare cu blockread in pascal care citeste in bucati mari din fisiere. Citesti intr-un buffer si trebuie sa parcurgi buffer-ul ca si cand citesti caracter cu caracter numerele.
Merge mult mai repede decat o citire standard dar e mai incomod de folosit. Titlul: 198 Custi Scris de: cristi8 din Martie 18, 2006, 22:00:29 eh, nu vreau sa fie tras de par timpul cu chestii de-astea.. vreau daca stiti alta idee de rezolvare, sau un smen sau ceva.. pentru ca am vazut ca ceilalti care au trimis aproximativ odata cu mine (m-am uitat la vreo 2 solutii de 100 la Monitorul de evaluare) au avut timpi cam egali ei si sub 0.3 secunde.. si nu cred ca au stat sa citeasca mai mult odata din fisier si dupa aia sa parseze.
Titlul: 198 Custi Scris de: Andrei Grigorean din Martie 19, 2006, 19:33:39 pai mai bine de n^2 nu ai cum sa scoti.
Titlul: 198 Custi Scris de: spx4 din Martie 19, 2006, 21:23:00 aici as vrea sa dau doar o posibila idee...nu m-am gandit la consecinte
sau la o generalizare...insa aceste submatrice se numesc si minori(la mate). (desi minorii sunt o notiune mai larga decat aceste "submatrici") o idee interesanta ar fi aceea ca daca exista o submatrice de ordin i atunci automat in acesta exista 4 de ordin i-1. daca exista 2 astfel de submatrici disjuncte(adica nu au in comun mai mult de i-2 coloane sau linii) atunci in ele vor exista 2*4 minori de ordin i-1. deasemeni ar mai fi de remarcat ca pentru un exemplu de forma 11111 11111 11011 11111 11111 acel 0 de la mijloc provoaca disparitia oricarei submatrici de ordin 4. mai precis ordinul maxim al submatricelor poate fi marginit in functie de pozitia acelui 0. poate ceva cu principiu includerii si excluderii... sper sa am timp sa ma gandesc mai mult la problema...o sa postez ceva mai detaliat peste vreo zi doua Titlul: 198 Custi Scris de: u-92 din Martie 19, 2006, 21:27:29 te complici prea mult cu includere sau minori.. chiar si n*n*logn mi-a intrat mie in timp :P
Titlul: 198 Custi Scris de: Filip Cristian Buruiana din Martie 19, 2006, 21:54:35 Citat sper sa am timp sa ma gandesc mai mult la problema...o sa postez ceva mai detaliat peste vreo zi doua Pai daca chiar e ceva interesant, poti sa faci si un articol pe info.devnet.ro decat sa postezi mesaj cu mesaj pe forum. Titlul: 198 Custi Scris de: vladut.forum din Martie 20, 2006, 10:58:37 eu am obtinut urmatorii timpi
TEST 1 ...[0.02s]... OK! TEST 2 ...[0.01s]... OK! TEST 3 ...[0.01s]... OK! TEST 4 ...[0.01s]... OK! TEST 5 ...[0.05s]... OK! TEST 6 ...[0.04s]... OK! TEST 7 ...[0.04s]... OK! TEST 8 ...[0.03s]... OK! TEST 9 ...[0.04s]... OK! TEST 10 ...[0.04s]... OK! 8) Titlul: 198 Custi Scris de: Savin Tiberiu din Martie 20, 2006, 16:48:12 Stau, ma uit ... shi nu inteleg.
Cum v-a intrat voua in timp chiar n*n*log n cand eu cu n^2 nu iau decat 60 de pct shi nu am decat 2 atribuiri shi o comparatie pe O(n^2) ](*,) ](*,) ](*,) ](*,) ](*,) Titlul: 198 Custi Scris de: vladut.forum din Martie 20, 2006, 16:58:31 sincer: teoretic un n^2 intra fara probleme, practic nu stiu ce ai in codul tau...
ar trebuii sa te uiti mai atent prin cod, sigur ai bushit ceva! Titlul: 198 Custi Scris de: u-92 din Martie 20, 2006, 17:04:52 daca citesti cu stream`uri e explicabil, incearca sa folosesti printf/scanf
Titlul: 198 Custi Scris de: cristi8 din Martie 20, 2006, 18:41:47 Citat din mesajul lui: vladut.forum eu am obtinut urmatorii timpi TEST 1 ...[0.02s]... OK! TEST 2 ...[0.01s]... OK! TEST 3 ...[0.01s]... OK! TEST 4 ...[0.01s]... OK! TEST 5 ...[0.05s]... OK! TEST 6 ...[0.04s]... OK! TEST 7 ...[0.04s]... OK! TEST 8 ...[0.03s]... OK! TEST 9 ...[0.04s]... OK! TEST 10 ...[0.04s]... OK! 8) m-ai provocat.. :D eu am luat: Cod: TEST 1 ...[0.01s]... OK! :-({|= Titlul: 198 Custi Scris de: Gogu Marian din Martie 20, 2006, 18:49:25 Cred ca e nevoie de un top dupa timpii solutilor de 100 la fiecare problema. Poate se straduieste lumea sa optimizeze mai mult.
Titlul: 198 Custi Scris de: Tiberiu-Lucian Florea din Martie 20, 2006, 18:52:16 Si ce formula propui ? Cel mai mic timp maxim ? Suma timpilor minima ?
Titlul: 198 Custi Scris de: Gogu Marian din Martie 20, 2006, 18:57:14 Cred ca dupa suma timpilor e cel mai bine. Sau se pot face 2 topuri, dupa ambele criterii. :)
Titlul: 198 Custi Scris de: vladut.forum din Martie 20, 2006, 19:30:49 o formula complicata... ca pe tc... :D
eu am vazut pe un site: era facuta suma timpilor 8) Titlul: 198 Custi Scris de: Filip Cristian Buruiana din Martie 20, 2006, 20:09:40 Cum ati scos voi timpp aia? Ati citit cu fgets si ati parsat voi? Sau cum?
Titlul: 198 Custi Scris de: Bogdan-Alexandru Stoica din Martie 21, 2006, 10:29:42 da. cu fgets merge mai repede :-({|=
Titlul: 198 Custi Scris de: Savin Tiberiu din Martie 21, 2006, 13:39:06 nu mai folosesc streamuri, folosesc fscanf shi fprintf. Doar ca akuma mi-am dat seama ca e n^3 nu n^2, gresheala mea, scuze.
Titlul: Răspuns: 198 Custi Scris de: Farcasanu Alexandru Ciprian din August 20, 2008, 22:03:40 vreo sugestie pt rezolvarea in O(N^2) ?
E: Never mind, am rezolvat Titlul: Răspuns: 198 Custi Scris de: Cristescu Adelina din Septembrie 20, 2010, 19:35:30 Am mare nevoie de un hint la prbl asta,am rezolvat-o in (N*N*logN), dar am vazut ca exista cateva surse cu timpi sub 0.05 :oops:. Multumesc anticipat!
Titlul: Răspuns: 198 Custi Scris de: Mircea Dima din Septembrie 20, 2010, 19:58:21 Am mare nevoie de un hint la prbl asta,am rezolvat-o in (N*N*logN), dar am vazut ca exista cateva surse cu timpi sub 0.05 :oops:. Multumesc anticipat! Pai rezolvi cu dinamica in O(N^2): dp[ i ][ j ] = lungimea celei mai mari submatrice patratice plina de 1 ce are coltul din dreapta jos in pozitia (i, j). dp[ i ][ j ] se calculeaza in O(1) Te las pe tine sa-ti dai seama cum calculezi numarul de submatrice plina de 1. Titlul: Răspuns: 198 Custi Scris de: Cristescu Adelina din Septembrie 21, 2010, 20:24:35 gata :yahoo: ms moolt pt ajutor :ok: , mare diferenta intre O(1) si O(logN) vreo 200-300 ms :))) , totusi nu inteleg cum au scos unii sub 0.05. :weightlift:
Titlul: Răspuns: 198 Custi Scris de: Mihai Calancea din Septembrie 21, 2010, 21:03:54 Au parsat citirea. Adica au citit inputul ca string si l-au convertit apoi manual in numere. Merge mult mai repede, mai ales pentru 10 ^ 6 numere.
Titlul: Răspuns: 198 Custi Scris de: Nicu B. din Iulie 19, 2012, 18:19:40 Salut, am luat TLE pe 3 teste [desi nu stiu de la ce].
Am facut o dinamica in O(N^2) si actualizez datele la fiecare pas al dinamicii, dar nu stiu care-i faza. Parsarea citirii poate face diferenta intre 70 si 100? Titlul: Răspuns: 198 Custi Scris de: Petenchea Alexandru din Octombrie 06, 2012, 21:57:43 O(n^2) cred ca intra in timp cu functiile din <cstdio> doar daca parsezi citirea . Cum nu cred ca asta era scopul problemei, poate mariti putin limita de timp daca sunteti de aceeasi parere cu mine :P
Titlul: Răspuns: 198 Custi Scris de: Guianu Leon din Octombrie 23, 2012, 17:36:26 De ce e asa comunista problema asta? Am trimis doar citirea cu scanf() + O SINGURA atribuire si imi da TLE la cateva teste. Am incercat si cu citire parsata si la fel face. Nici o diferenta. ](*,)
Titlul: Răspuns: 198 Custi Scris de: Andrei Grigorean din Octombrie 23, 2012, 18:30:49 Functia strlen() are complexitatea O(N), deci practic tu ai acolo O(N^3).
Titlul: Răspuns: 198 Custi Scris de: Guianu Leon din Octombrie 23, 2012, 19:46:00 Functia strlen() are complexitatea O(N), deci practic tu ai acolo O(N^3). Am reusit! Nu mi-as fi dat seama de chestia asta in veci! :fool: Iti multumesc mult! :shock: Se pare ca trebuie sa rectific ce am zis mai sus. Problema nu e comunista, e cat se poate de capitalista. =D> Titlul: Răspuns: 198 Custi Scris de: Marian Darius din Noiembrie 03, 2012, 10:53:53 Timpul problemei asteia este gresit!!! Am facut problema O(n*n), doar partea de CITIRE si inca 2 for-uri de la 1 la n si imi da TLE ](*,) ](*,) ](*,) ](*,)
Titlul: Răspuns: 198 Custi Scris de: Marian Darius din Noiembrie 03, 2012, 11:03:46 Ignorati mesajul interior, am schimbat din scanf/printf in cin/cout si am luat 100
Titlul: Răspuns: 198 Custi Scris de: Andrei Constantinescu din Februarie 02, 2013, 12:06:18 Eu am inteles solutia O(n^2) dar sunt chiar curios de cea in O(nlogn). Cutare binara? Un hint, ceva, va rog.
,Andrei Titlul: Răspuns: 198 Custi Scris de: Radu-Andrei Szasz din Februarie 02, 2013, 14:02:17 Nu ai cum sa scoti o solutie in O(N log N) din moment ce ai complexitate O(N^2) doar pentru citirea matricii.
Titlul: Răspuns: 198 Custi Scris de: Andrei Constantinescu din Februarie 04, 2013, 22:49:53 Vroiam sa zic O(n^2*logn). Greseala mea.
,Andrei Titlul: Răspuns: 198 Custi Scris de: Cazacu Robert din Februarie 26, 2013, 18:59:51 Ok... Ma chinui de cateva ore si nu reusesc sa-mi dau seama ce e in neregula cu sursa mea ](*,) , pe primele 4 teste obtine punctaj maxim dar pe urmatoarele imi da o eroare de care nu am mai auzit.
Aici is rezultatele testelor: Cod: 1 12ms 1972kb OK 10 Titlul: Răspuns: 198 Custi Scris de: Silvia Andreea Robu din Februarie 26, 2013, 20:56:40 Stiu ca nu este cel mai potrivit loc pentru aceasta, insa daca tot sunt la aceasta problema doresc sa va indreb Q_Q Cum incep un program? In DEV C++ totul este inregula insa in Code::Blocks nu imi gaseste directoriul iostream.h si nici fstream.h Nu merge fara .h de asemenea. Observ ca aceasta chestie imi afecteaza evaluarea. :oops:
Titlul: Răspuns: 198 Custi Scris de: Simoiu Robert din Februarie 26, 2013, 21:32:48 Cele cu .h sunt deprecated, doar cele din C-ul vechi se mai pastreaza cu .h (gen stdio.h, stdlib.h, string.h, care in C++ sunt cstdio, cstdlib, cstring). Pentru fstreamuri, varianta noua este aceasta L
Cod: # include <fstream> // sau # include <iostream> Titlul: Răspuns: 198 Custi Scris de: Silvia Andreea Robu din Februarie 26, 2013, 21:40:26 o, nice
merci \o/ sper ca acum o sa-mi iasa ceva c: Titlul: Răspuns: 198 Custi Scris de: Elena Obreja din Iunie 13, 2013, 16:38:09 Iau 30 pe asta(TLE)... daca imi poate explica cineva ce trebuie sa mai modific pentru a da in timp.
Cod: #include<fstream> Titlul: Răspuns: 198 Custi Scris de: Salajan Razvan din Iunie 13, 2013, 17:00:26 E prea mare complexitatea. Citeste ce s-a mai postat pe forum si incearca sa scoti O(n^2).
Titlul: Răspuns: 198 Custi Scris de: Cretu Bogdan din Septembrie 24, 2013, 19:27:10 Vreun sfat?
http://www.infoarena.ro/job_detail/1001305 (http://www.infoarena.ro/job_detail/1001305) Dupa parerea mea am O(n*n) dar totusi iau TLE pe 3 teste :D Titlul: Răspuns: 198 Custi Scris de: Salajan Razvan din Septembrie 24, 2013, 20:45:15 Eu nu sunt de aceeasi parere... :). Ai acolo un for, care chiar daca e micut, conteaza :)).
Cod: for (k=1;k<=b[i][j];k++) h[k]++; Titlul: Răspuns: 198 Custi Scris de: Cretu Bogdan din Septembrie 24, 2013, 21:14:32 Corect, greseala mea. :D
Si...vreo idee sa reduc acea parcurgere? (nu-mi vine nimic in minte) ](*,) Titlul: Răspuns: 198 Custi Scris de: Salajan Razvan din Septembrie 24, 2013, 21:48:59 O idee ar fi smenul lui mars. Dar exista si alta solutia mai simpla. Gandeste-te in felul urmator : toate actualizarile sunt de forma [1..X], unde X e b[ i ][ j ] (la tine). Incearca sa scoti o solutie astfel incat actualizarile sa le faci in O(1).
Titlul: Răspuns: 198 Custi Scris de: Cretu Bogdan din Septembrie 30, 2013, 19:57:49 Am reusit sa duc sursa la 90 de puncte =D>
http://www.infoarena.ro/job_detail/1003513 (http://www.infoarena.ro/job_detail/1003513) La "metoda" asta te refereai? (chiar daca nu prea am facut-o in O(1)...cred ca undeva pe la O(2) sau O(3) ) Titlul: Răspuns: 198 Custi Scris de: Adrian Budau din Octombrie 01, 2013, 10:22:03 Nu exista O(2) sau O(3) :P. O(1) inseamna orice numar fix de operatii care nu depinde in niciun fel de restrictiile problemei. Daca vrei sa intelegi exact notatia asta citeste aici http://en.wikipedia.org/wiki/Big_O_notation (http://en.wikipedia.org/wiki/Big_O_notation)
Titlul: Răspuns: 198 Custi Scris de: Cretu Bogdan din Octombrie 01, 2013, 13:45:32 Aha. Mersi.
Deci am facut-o in O(1) dar totusi iau 90...o fi de la citire/afisare? :D EDIT: Am pus-o din nou in evaluator si am luat 100 (destul de ciudat) :D Oricum multumesc! ^_^ =D> Titlul: Răspuns: 198 Custi Scris de: Adrian Budau din Octombrie 03, 2013, 10:12:27 Probabil ca e prea apropiata limita. Am marit la 0.25, multumim de atentionare.
Titlul: Răspuns: 198 Custi Scris de: Andrei Otetea din Decembrie 10, 2014, 09:50:59 :shock:
Titlul: Răspuns: 198 Custi Scris de: Mercea Otniel din Martie 02, 2015, 19:30:06 ce e gresit la dinamica asta ca iau numai 10 pct
for(i=1;i<=n;i++) for(j=1;j<=n;j++) {int u=0; fscanf(f,"%d",&z); if(z==1) {m[j]=1; } if(m[i-1][j-1]!=0&&z==1) { if(m[i-1][j]==m[j-1]) {if(m[i-m[i-1][j]][j-m[i-1][j]]!=0) m[j]=m[i-1][j]+1; else {m[j]=m[i-1][j]; } } else if(m[i-1][j]>m[j-1]&&(m[i-1][j]!=0&&m[j-1]!=0)) m[j]=m[i-1][j]; else if(m[i-1][j]<m[j-1]&&(m[i-1][j]!=0&&m[j-1]!=0)) m[j]=m[j-1]; } } Titlul: Răspuns: 198 Custi Scris de: Mercea Otniel din Martie 02, 2015, 19:32:20 ce e gresit la dinamica asta ca iau numai 10 pct am gasit problemafor(i=1;i<=n;i++) for(j=1;j<=n;j++) {int u=0; fscanf(f,"%d",&z); if(z==1) {m[j]=1; } if(m[i-1][j-1]!=0&&z==1) { if(m[i-1][j]==m[j-1]) {if(m[i-m[i-1][j]][j-m[i-1][j]]!=0) m[j]=m[i-1][j]+1; else {m[j]=m[i-1][j]; } } else if(m[i-1][j]>m[j-1]&&(m[i-1][j]!=0&&m[j-1]!=0)) m[j]=m[i-1][j]; else if(m[i-1][j]<m[j-1]&&(m[i-1][j]!=0&&m[j-1]!=0)) m[j]=m[j-1]; } } Titlul: Răspuns: 198 Custi Scris de: Adrian Buzea din Martie 02, 2016, 11:14:29 Eu am o solutie in (N^2 * count[N]) si nu imi dau seama cum pot sa scap de count[N].
Cand ajung la i,j si calculez Cod: best[i][j] = n Cod: count[i]++ Nevermind, am rezolvat :aha: Titlul: Răspuns: 198 Custi Scris de: andrei din Aprilie 07, 2016, 00:05:05 N^2log(N) fara parsare nu intra :eyebrow:
Titlul: Răspuns: 198 Custi Scris de: Mihai Calancea din Aprilie 07, 2016, 00:38:27 Păi foarte bine, există N ^ 2 :).
|