|
Titlul: 690 Euro2 Scris de: Airinei Adrian din Aprilie 06, 2008, 14:32:20 Aici puteţi discuta despre problema Euro2 (http://infoarena.ro/problema/euro2).
Titlul: Răspuns: 690 Euro2 Scris de: Simina Pitur din Aprilie 16, 2008, 23:19:43 ceva special la testele 3 si 5? :'(
EDIT: :yahoo: nevermind! trebuia mai multa atentie la restrictii! Titlul: Răspuns: 690 Euro2 Scris de: Florian Marcu din Iunie 02, 2008, 19:30:02 A facut cineva de 100, calculand cmlsc in O(n^2) ?
Titlul: Răspuns: 690 Euro2 Scris de: Robert Sandu din Iunie 02, 2008, 22:40:22 Ma indoiesc avand in vedere ca n=10000.
Dar poti sa calculezi cmlsc in n*log(n) Titlul: Răspuns: 690 Euro2 Scris de: Mari n din Octombrie 09, 2008, 15:53:56 In enunt zice ca:
Numerele reprezentand valoarea unui Euro in RON au toate exact patru cifre in partea zecimala si sunt distincte Mai intai am trimis o sursa in care memorez datele ca long int inmultindu-le cu 10000. Iau 80 puncte. Cand lucrez cu ele ca float iau 100. Titlul: Răspuns: 690 Euro2 Scris de: Andrei-Bogdan Antonescu din Octombrie 09, 2008, 22:24:44 Poate ai uitat sa faci undeva conversi cand aveai operatii pe tipuri diferite de date.
Alfel ar trebui sa mearga . :-' Titlul: Răspuns: 690 Euro2 Scris de: Flavius Anton din Ianuarie 15, 2009, 18:10:04 trebuie inclus neaparat valoarea maxima, adica raportarile sa creasca pana la valoarea maxima, si apoi sa scada? sau pur si simplu trebuie gasit nr. maxim de raportari. Eu as inclina spre var. nr 2. pt ca spre exemplu pt un fisier de intrare de forma
Max val val val nu cred ca ai cum sa introduci maximul in raportari. so? Titlul: Răspuns: 690 Euro2 Scris de: Florian Marcu din Ianuarie 16, 2009, 23:02:04 Da. Varianta a doua e corecta. :)
Titlul: Răspuns: 690 Euro2 Scris de: Flavius Anton din Ianuarie 17, 2009, 12:46:02 ok multumesc, am sa ma apuc de ea maine, sau poimaine :D.
Titlul: Răspuns: 690 Euro2 Scris de: speedzeal din Septembrie 13, 2009, 17:14:42 ceva special la testele 3 si 5? :'( Nici mie nu imi da corect pe aceste teste.De ce nu iti dadea corect? ???EDIT: :yahoo: nevermind! trebuia mai multa atentie la restrictii! Titlul: Răspuns: 690 Euro2 Scris de: Dragos Oprica din Septembrie 14, 2009, 15:36:26 ceva special la testele 3 si 5? :'( Nici mie nu imi da corect pe aceste teste.De ce nu iti dadea corect? ???EDIT: :yahoo: nevermind! trebuia mai multa atentie la restrictii! Reciteste aceasta restrictie si fi sigur ca o respecti: Citat Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element) Titlul: Răspuns: 690 Euro2 Scris de: speedzeal din Septembrie 15, 2009, 13:44:59 Asa fac alegerea subsecventei maximale:
Cod: freopen("euro2.out","w",stdout);int i,max=2;Cod: void solvea() Titlul: Răspuns: 690 Euro2 Scris de: Iancu David Traian din Octombrie 23, 2009, 22:13:07 Desi mi-am dat toate testele care mi-au venit in cap, nu inteleg de ce nu iau decat 70 de puncte. Imi puteti da un test ca sa imi dau seama ce gresesc?
Eu retin in max [ i ] scmax daca vectorul se termina pe pozitia i, iar in min[ i ] scmin daca vectorul incepe pe pozitia i. La sfarsit afisez maximul dintre min[ i ] si max[n-i+1], i apartinand intervalului (2;n-1) si am grija ca min[ i ] si max [n-i+1] sa fie mai mari decat 1. Ce gresesc? Titlul: Răspuns: 690 Euro2 Scris de: Florian Marcu din Octombrie 24, 2009, 12:24:09 Rezolvi in O(NlogN) ? Si ce anume primesti: TLE sau WA ?
Titlul: Răspuns: 690 Euro2 Scris de: Cohal Alexandru din Decembrie 29, 2009, 11:22:36 Solutia la problema asta nu consta in:
- determinarea maximului din sirul de valori - determinarea lungimii Subsirului Crescator Maximal de la primul element din vector pana la pozitia maximului (determinat anterior) - determinarea minimului din sirul de valori de dupa pozitia maximului - determinarea lungimii Subsirului Descrescator Maximal de pe pozitia maximului+1 pana la pozitia minimului (determinat anterior) - adunarea celor 2 lungimi si afisarea rezultatului ? :?: Eu am facut asa dar numai la 3 teste imi da corect, iar la restul WA... Titlul: Răspuns: 690 Euro2 Scris de: Andrei Misarca din Decembrie 29, 2009, 11:38:44 Primești incorect pentru că algoritmul tău nu este corect. Dacă ai ceva de genul
Cod: 9 Tu vei zice că răspunsul este 3, considerând doar secvența formată din primele 3 elemente, dar răspunsul corect este 7. Titlul: Răspuns: 690 Euro2 Scris de: George Popoiu din Ianuarie 07, 2010, 21:54:14 Fac la fel ca in solutie. Pentru fiecare i de la 1 la N calculez scmax ce se termina cu i si subsirul descrescator maximal de la i pana la N.
Astea le calculez in O(NlogN) si pe testele [8,15] iau TLE, iar pe testele 5 si 3 WA. Any hints plz? ](*,) Titlul: Răspuns: 690 Euro2 Scris de: Licker Nandor din Ianuarie 10, 2011, 16:38:26 Cat ar trebui sa fie rezultatul pentru testul:
Cod: 8 ? Titlul: Răspuns: 690 Euro2 Scris de: Dragos-Alin Rotaru din Ianuarie 10, 2011, 16:40:46 5 este rezultatul.
Titlul: Răspuns: 690 Euro2 Scris de: Matei Ionita din Februarie 14, 2011, 00:23:02 Mi se pare ambiguu formulat:
Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element). Nu inteleg, de exemplu, daca o secventa de tipul 3.1 3.2 3.3 3.5 este solutie valida - adica acel "cel putin un element" include si elementul maxim sau nu? Iau WA pe testele 3 si 5, si din ce s-a discutat pana acum inteleg ca solutia sta in formularea asta. Poate cineva sa-mi traduca va rog? :) Titlul: Răspuns: 690 Euro2 Scris de: Eugenie Daniel Posdarascu din Februarie 14, 2011, 08:42:40 Mi se pare ambiguu formulat: Raportarile alese de Banca Nationala trebuie sa contina o secventa crescatoare (formata din cel putin doua elemente), urmata de o secventa descrescatoare (formata din cel putin un element). Nu inteleg, de exemplu, daca o secventa de tipul 3.1 3.2 3.3 3.5 este solutie valida - adica acel "cel putin un element" include si elementul maxim sau nu? Iau WA pe testele 3 si 5, si din ce s-a discutat pana acum inteleg ca solutia sta in formularea asta. Poate cineva sa-mi traduca va rog? :) Da, este valida. Titlul: Răspuns: 690 Euro2 Scris de: Alexandru-Iancu Caragicu din Februarie 14, 2011, 15:32:07 Daca cursul pentru euro o sa iasa pana la urma din intervalul 3 - 4, o sa se actualizeze problema?
_________________ Oricum, eu m-am gandit in felul urmator: Fac subsir crescator maximal pe numere (in O(NlogN)) si retin pentru intervalele [1,1]; [1,2]; ...; [1,n] lungimea celui mai lung subsir comun. Rastorn v-ul si repet ca sa obtin pt intervalele [n,n];[n-1,n]...;[1,n]. Apoi incerc in toate cele n-2 pozitii (sau in fine n, ca am incercat si asa) sa stabilesc unde se termina sirul crescator si incepe cel descrescator si retin maximul sumelor scmax(1,i) + sdmax(i+1,n), punand conditii scmax(1,i) >= 2 (crescatoare) sdmax(i+1,n) >= 1 (descrescatoare) Totusi, iau 95p. E vre-un caz particular? Titlul: Răspuns: 690 Euro2 Scris de: George Marcus din Februarie 24, 2011, 21:32:49 Probabil pici (tu,eu inainte si restul cu 90+ puncte) unul dintre urmatoarele teste:
Cod: 4 Cod: 4 Cod: 4 Cod: 0 Cod: 4 Cod: 0 (primul l-am pus pentru comparatie si ultimele doua ca sa scot in evidenta restrictiile pentru alegerea raportarilor) Titlul: Răspuns: 690 Euro2 Scris de: Alexandru-Iancu Caragicu din Februarie 25, 2011, 20:11:24 Dar de ce raspunsul e 0 la a doua? Nu sunt bune
3.1123 3.1124 3.1125 ca secvanta crescatoare si 3.1126 ca secventa descrescatoare? ____________ never mind. Am luat 100. Vad ca secventa descrescatoare trebuie sa inceapa descrescator fata de cea crescatoare. Titlul: Răspuns: 690 Euro2 Scris de: Vasilut Lucian din Noiembrie 26, 2011, 18:24:36 imi dati si mie un test de intrare pt problema asta...ca iau 5 pct dar algoritmul mi se pare corect....adica fac cel mai lung subsir crescator+cel mai lung subsir descrescator;
Titlul: Răspuns: 690 Euro2 Scris de: Gabriel Bitis din Noiembrie 26, 2011, 21:51:11 Trebuie o subsecventa(nu subsir) crescatoare urmata imediat de o subsecventa descrescatoare, iar lungimea lor adunata sa fie maxima.
Titlul: Răspuns: 690 Euro2 Scris de: George Marcus din Noiembrie 26, 2011, 22:02:54 Trebuie un subsir, care la randul lui sa fie format dintr-o secventa crescatoare urmata imediat de una descrescatoare.
Titlul: Răspuns: 690 Euro2 Scris de: Mihai Visuian din Decembrie 30, 2011, 12:43:41 Iau tle pe ultimele teste.
Am determinat cel mai lung subsir descrescator, considerand ca si inceput fiecare element si dupa aceea cel mai lung subsir crescator considerand ca si capat fiecare element si dupa aceea am facut maximul in O(n); Determinarea subsirurilor le-am calculat in O(n*n) fiecare. Are cineva vreo idee de o implementare optima? :?: Titlul: Răspuns: 690 Euro2 Scris de: George Marcus din Decembrie 30, 2011, 16:22:26 Poti folosi ideea cu cautare binara pentru a determina subsirul crescator maximal in O(n logn) (sau arbori de intervale, aib). Uita-te aici (http://infoarena.ro/problema/scmax) la solutiile de 100 de puncte.
Titlul: Răspuns: 690 Euro2 Scris de: Ana Rogoz din Decembrie 07, 2012, 22:10:59 La restrictii este scris ca subsirul crescator trebuie sa aiba minim 2 elemete, iar cel descrescator minim 1......
Elementul comun este numarat in ambele subsiruri ? Titlul: Răspuns: 690 Euro2 Scris de: Petru Trimbitas din Decembrie 08, 2012, 00:00:03 e numarat o singura data :)
Titlul: Răspuns: 690 Euro2 Scris de: Ana Rogoz din Decembrie 08, 2012, 08:53:25 Ok , merci . :)
Titlul: Răspuns: 690 Euro2 Scris de: Ava Spataru din Decembrie 08, 2012, 09:50:42 Si in care dintre subsiruri este numarat ? ( in cea crescatoare sau in cea descrescatoare )
Titlul: Răspuns: 690 Euro2 Scris de: George Marcus din Decembrie 08, 2012, 11:04:43 In cel crescator.
Titlul: Răspuns: 690 Euro2 Scris de: Ana Rogoz din Decembrie 08, 2012, 11:05:55 Nu prea conteaza...Oricum , cred ca in prima secventa :)
Titlul: Răspuns: 690 Euro2 Scris de: Vasile Catana din Aprilie 13, 2014, 19:39:01 http://www.infoarena.ro/job_detail/1170567 , nu inteleg dc am numai 20 de p , daca mi-ati putea gasi greseala : J
|