|
Titlul: 209 Sir Scris de: Bogdan-Alexandru Stoica din Martie 29, 2006, 18:05:04 Aici puteţi discuta despre problema Sir (http://infoarena.ro/problema/sir).
Titlul: 209 Sir Scris de: Filip Cristian Buruiana din Martie 29, 2006, 20:04:53 A reusit cineva sa scoata O(N)?
Titlul: 209 Sir Scris de: Andrei Grigorean din Martie 29, 2006, 20:20:59 ma mai chinui putin. iau WA pe 3 teste si nu stiu de ce ](*,) ](*,) ](*,)
Titlul: Raspuns: 209 Sir Scris de: Tandrau Alexandru din Aprilie 07, 2006, 11:54:09 Am o rezolvare care ia 90-95 de puncte. Iau WA pe testul nr 14. Am trimis o rezolvare care verifica si datele de intrare si cred ca acest test nu corespunde la conditia:
Citat - Valorile sirului sunt numere naturale ≤ 30.000 Titlul: Raspuns: 209 Sir Scris de: Alex Dimitriu din Aprilie 07, 2006, 13:08:21 Da ai dreptate, am verifcat testul respectiv si exista ~ 5-6 valori de 30001 si 30002 ...
Cred totusi ca o poti rezolva si in acest caz .. nu vad un impediment. Probabil ca enuntul va fi modificat. Titlul: Raspuns: 209 Sir Scris de: Marius Stroe din Iunie 26, 2006, 20:25:01 Si eu am scos O(N)... :D
Titlul: Raspuns: 209 Sir Scris de: Toma Radu din Iunie 26, 2006, 21:05:57 Imi zice si mie cineva o idee cam cum ar trebui rezolvata problema?
Titlul: Raspuns: 209 Sir Scris de: u-92 din Iunie 28, 2006, 22:32:05 o cautare binara te poate ajuta
Titlul: Raspuns: 209 Sir Scris de: Marius Stroe din Iulie 02, 2006, 03:16:41 Ideea de O(N) pe care am avut-o a fost sa stiu la fiecare pas unde incepe secventa si sa tot aleg o pozitie convenabila doar avansand, normal. Acum nu iti mai ramane decat sa stii ce valori ai in intervalul tau. :P
Titlul: Raspuns: 209 Sir Scris de: Toma Radu din Iulie 02, 2006, 17:42:13 Presupunand ca am un sir a[] de n elemente, si un subsir de lungime l, al carui inceput il iau pe rand pe ppozitiile 1, 2, ....n-l, care este cea mai eficienta metoda pentru a stii minimul si maximul din subsecventa de lungime l?
Este vreo metoda sau trebe sa verific pentur fiecare pozitie de inceput in O(l) minimul si maximul? Titlul: Raspuns: 209 Sir Scris de: Marius Stroe din Iulie 02, 2006, 17:58:09 Presupunand ca am un sir a[] de n elemente, si un subsir de lungime l, al carui inceput il iau pe rand pe ppozitiile 1, 2, ....n-l, care este cea mai eficienta metoda pentru a stii minimul si maximul din subsecventa de lungime l? Este vreo metoda sau trebe sa verific pentur fiecare pozitie de inceput in O(l) minimul si maximul? Minimul si maximul il construiesti treptat pe masura ce avansezi cu pozitiile tale cu ajutorul a doua deque-uri. Uite: Cod: pentru k = 1, N executa Intuitiv mi se pare bine... Titlul: Raspuns: 209 Sir Scris de: Toma Radu din Iulie 02, 2006, 18:10:09 Nu cred ca ai inteles ce am intrebat de fapt. Am doua variabile maxim si minim.
Cum stiu in timpul rularii, care este maxim si care este minim, pentru un anume i (1...n-l) si care este cea mai eficienta metoda sa le determin, ca sa nu fac : Cod: for ( i = 1; i <= n-l; i++ ) ? :-k Titlul: Raspuns: 209 Sir Scris de: Marius Stroe din Iulie 02, 2006, 18:30:01 Eu cred ca tu nu m-ai inteles... prima valoare din deque este minimul/maximul cautat.
Titlul: Raspuns: 209 Sir Scris de: Toma Radu din Iulie 02, 2006, 22:20:30 A da ...am inteles :aha:...sorry....
Titlul: Răspuns: 209 Sir Scris de: Ion Ureche din Iulie 12, 2011, 20:04:19 Imi poate sugera cineva de ce imi pica al 2-lea test...in rest toate merg perfect, am 95 puncte si nu-mi pot gasi greseala in program...
Titlul: Răspuns: 209 Sir Scris de: Andi Arnautu din Ianuarie 06, 2015, 01:47:13 Este ceva special la testul 14? E singurul care imi pica, iau 95p. ](*,)
Titlul: Răspuns: 209 Sir Scris de: Trasca Andrei din Martie 07, 2016, 21:46:15 Am si eu o intrebare. Functiile consuma mult timp? Adica m-am chinuit o gramada sa iau 100 de puncte la problema asta, chiar daca o faceam in O(N). Am incercat pana si parsarea si m-a ajutat sa ajung de la 80 la 90, tot am avut 2 teste cu TLE. Apoi m-am gandit sa scot o functie si am ajuns de la peste 0,3 secunde la 8ms. Nu prea inteleg de ce.
Titlul: Răspuns: 209 Sir Scris de: Alex Cociorva din Martie 07, 2016, 22:06:57 Asta e pentru ca tu transmiti prin valoare un obiect de tip deque de fiecare data cand apelezi functia. Practic copiezi tot deque-ul care il ai intr-un nou deque de fiecare data cand apelezi. Incearca sa transmiti doar adresa (adica prin referinta) si ai sa vezi ca o sa mearga rapid.
Titlul: Răspuns: 209 Sir Scris de: Florea Daria din Martie 08, 2016, 16:47:50 Imi da WA pe testele 2 si 4 ](*,).Am facut problema in o(n) cu doua cozi(una pentru minim,alta pentru maxim).Imi puteti da niste teste sau o idee pentru 100 ? :) (p.s. n-am folosit cautarea binara cum spune in indicatii)
Titlul: Răspuns: 209 Sir Scris de: Usurelu Florian-Robert din Martie 08, 2017, 21:29:47 Eu iau 95 puncte, sursa mea pica pe testul 2 WA. I s-a mai intamplat cuiva asta si a gasit ce e cu testul acela?
|