Afişează mesaje
|
Pagini: [1] 2 3
|
7
|
infoarena - concursuri, probleme, evaluator, articole / ONIS 2015 / Răspuns: Feedback Runda 3
|
: Aprilie 21, 2015, 21:22:58
|
Problema ecotraseu putea fi o problema super, dar limitele au fost puse aiurea. Nu stiu cum au facut ceilalti, dar eu am un dfs si iau kbs deoarece aparent crapa stiva de memorie... In fine, mi se pare putin aiurea ca mi-a picat problema din cauza asta ( si nu sunt singurul ), si in general nu imi plac problemele unde trebuie optimizari "la sange", adica daca e ideea buna ar trebui sa intre cam orice implementare bazata pe acea idee.
|
|
|
12
|
infoarena - concursuri, probleme, evaluator, articole / Urmasii lui Moisil 2015 / Răspuns: Feedback probleme Urmasii lui Moisil
|
: Martie 21, 2015, 16:16:22
|
Problemele au fost destul de accesibile, desi la varianta live vad ca doar Buhai a scos geometrie... In fine, ma asteptam sa fie conditii ca si la concurs adica feedback pe exemplu, dar macar asa am invatat sa mai verific ocazional numele fisierelor. Naveplanare mi s-a parut destul de evidenta ca si solutie pentru cineva care observa cuplajul in probleme:)). Cat despre geometrie, era mai interesant cu queryuri online, desi oricum nu s-au luat atatea punctaje de 100 pe ea cat ar fi fost bine sa se ia, deci mai bine nu:)).
|
|
|
19
|
infoarena - concursuri, probleme, evaluator, articole / ONIS 2015 / Răspuns: Feedback
|
: Februarie 21, 2015, 22:13:07
|
Pot sa spun ca ideile de rezolvare au fost destul de originale si foarte variate. Cred ca un astfel de concurs nu trebuie sa fie usor, deoarece pana la urma scopul sau este de a simula lucrul in echipa la un posibil viitor concurs pe echipe (ACM), deci din acest punct de vedere si-a atins scopul. Ok, poate au fost cam grele problemele, si ce? Un concurs este cu atat mai util, cu cat sunt mai multe probleme pe care nu le stii face, deoarece astfel vei avea lucruri noi de invatat din ele. Singura obiectie ar fi la problema Invazie, la care ma bucur ca autorii s-au sesizat si si-au cerut scuze, si este putin pacat ca problema nu a mers cum trebuie dar din 12 probleme una sa aiba cateva greseli mi se pare complet rezonabil, sa nu uitam ca cei ce au propus runda nu sunt veterani in acest domeniu. Cu alte cuvinte, felicitari pentru runda si tineti-o tot asa!
|
|
|
21
|
infoarena - concursuri, probleme, evaluator, articole / Concursuri / Răspuns: patrate
|
: Ianuarie 26, 2015, 19:02:18
|
Pai din numarul ala de n cifre doar ultimele 9 conteaza ca sa iti iasa sufixul ala. Acum, poti sa bagi brute 10^8 numere, si fixezi ultima cifra 1 sau 9 ca sa iti iasa patratul terminat in 1, asa poti afla numerele de 9 cifre sau mai putin pentru care patratul are sufixul ala. Apoi, pentru n cifre(n>=9), raspunsul va fi : numarul de numere gasite cu 9 cifre * 10^n-10^(n-1)
|
|
|
22
|
infoarena - concursuri, probleme, evaluator, articole / Concursuri / Răspuns: Happy Birthday Infoarena 2014
|
: Ianuarie 26, 2015, 18:36:31
|
Ok, o sa pun aici solutia la kthvalue cu alb, pentru cei ce nu doresc spoiler.
In primul rand sa consideram posibile doar urmatoarele operatii: se adauga la sfarsit un element, se sterge ultimul element, query l,r,k sa se afle al klea element din intervalul [l,r]. Problema asta se poate rezolva in MlogN, unde M=numarul de operatii si N=valoarea maxima a unui numar. Puteam stoca intr-o trie, dupa x adaugari sa zicem, toate cele x numere adaugate (tria va avea doar 0 si 1, daca nu stiti cum faceti asta, cititi problema xormax ). Acum, daca am putea mentine cate o trie pentru starea sirului de numere dupa x adaugari, adica o trie pentru fiecare prefix al sirului, problema ar fi rezolvata : parcurgem simultan tria pentru prefixul [1,r] si cea pentru prefixul [1,l-1] si daca scadem din frecventa primei trii, pe cea a celei de-a 2a aflam practic cum arata tria pentru intervalul [l,r]. Acum, putem sa facem un "dfs" simultan pe cele 2 trii si vedem daca mergem pe ramura cu bitul 0 sau cu bitul 1. Acum, la problema noastra trebuie sa facem cateva modificari. Poate se realizeaza mai usor dar o sa va zic cum am facut eu : Mentinem 2 astfel de trii, una pentru adaugari in fata, cealalta pentru adaugari in spate. Problema s-ar pune atunci cand stergem un element dintr-o parte si acea trie e deja goala, dar cand intervine acest caz "resetam" tria cu numarul 0 din partea opusa, adica incrementam ordinul triei considerate 0.In fine, destul de smechera problema, GG propunatorilor.
|
|
|
|