Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Romanian Master of Mathematics & Sciencies 2011  (Citit de 11080 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« : Februarie 22, 2011, 21:25:30 »

În perioada 23 - 28 februarie 2011 Colegiul Național de Informatică "Tudor Vianu" organizează cea de-a patra ediție a concursului Romanian Master of Mathematics & Sciencies, care începând din acest an are și o secțiune de informatică. Infoarena găzduiește o versiune online a concursului, în același timp cu cel oficial, așa că oricine dorește poate participa! Nu uitați să vă înscrieți dacă vreți să concurați!
« Ultima modificare: Februarie 27, 2011, 09:44:22 de către Andrei Parvu » Memorat
R.A.R
Strain
*

Karma: -7
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #1 : Februarie 22, 2011, 22:22:48 »

Un link catre pagina concursului ?
Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #2 : Februarie 22, 2011, 22:25:51 »

Un link catre pagina concursului ?

http://infoarena.ro/rmms-2011

Ai acolo si pagina oficiala.
Memorat
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #3 : Februarie 25, 2011, 15:18:55 »

Rezultatele le aflam azi, sau doar maine, dupa terminarea concursului (si eventual, aflarea castigatorilor de la concursul on-site)?
Memorat
gorgovan
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #4 : Februarie 25, 2011, 15:37:59 »

Imi puteti spune cum se faceau Light2 si Walls?

Multumesc anticipat!
Memorat
vladii
Echipa infoarena
De-al casei
*****

Karma: 32
Deconectat Deconectat

Mesaje: 141



Vezi Profilul
« Răspunde #5 : Februarie 25, 2011, 17:55:46 »

Solutiile mele:

- Light2:
Eu m-am gindit la principiul includerii si excluderii, formula este:
sol = P[ d1 ] + P[ d2 ] + ... + P[ dK ] - 2 * P[ cmmmc(d1, d2) ] - 2 * P[ cmmmc(d1, d3) ] - ... - 2 * P[ cmmmc(dK-1, dK) ] + 4 * P[ cmmmc(d1, d2, d3) ] + 4 * P[ cmmmc(d1, d2, d4) ] + ...
unde P[ x ] = numarul de numere divizibile cu x de la 1 pina la N.
In general, pentru toate numerele de la 1 la (1 << K), daca descompunerea in baza 2 are B biti, atunci daca B este impar, adaug la solutie 2^(B-1) * P[ cmmmc(D[x1], D[x2], ..., D[xB]) ], iar daca B este par atunci scad din solutie 2^(B-1) * P[ cmmmc(D[x1], D[x2], ..., D[xB]) ] (x1, x2, ..., xB = pozitiile bitilor care au valoarea 1).

- Walls:
Pentru un tun fixat la (x, y), evident pot trage doar in turnurile care se afla la stinga lui x, si astfel caut binar cel mai din dreapta turn astfel incit sa fie la stinga lui x. Fie acesta TT. Acum ma intereseaza sa caut cel apropiat turn de coordonata tunului (x) din intervalul [1, TT], cu H[turn] >= y.
Astfel fac o cautare binara, limita inferioara = 1, limita superioara = TT. Testez pe intervalul [mijloc, TT] care este cel mai inalt turn (facind un query pe un arbore de intervale), daca acest cel mai inalt turn este >= y, atunci il retin ca solutie (adica turnul in care va urma sa trag) si restring intervalul (limita inferioara = mijloc + 1), altfel nu imi convine si caut intr-un interval mai mare (limita superioara = mijloc - 1).
Daca nu am gasit niciun turn cu propr respectiva, atunci afisez MISS. Sa zicem ca am gasit un turn, il notez cu T. Evident eu trag acum un shot pe linia y a acestui turn T. Imi tin un map<pair<int, int>, int> shot, unde imi notez de cite ori am tras in linia y a turnului x (adica shot[ make_pair(x, y) ]). Acum mai trag o data, deci shot[ make_pair(TURN, y) ] ++. Daca shot[ make_pair(TURN, y) ] = W[TURN], atunci nivelul se distruge, H[TURN] devine = y-1 si updatez in arborele de intervale noua inaltime.
Cum sunt maxim 200.000 de shoturi, in map nu ar trebui sa retin mai mult de 200.000 de entry`uri, asa ca memoria nu ar trebui sa fie o problema (sincer nu am trimis inca sursa caci nu e problema adaugata in Arhiva, deci este posibil sa ma insel Smile).
Complexitate: N * log^2N.

Astept sa apara problemele in arhiva ca sa vad mai exact cite puncte obtin pe aceste idei. Daca observati vreo greseala, nu ezitati sa ma corectati Very Happy

Toate cele bune!
Vlad.
« Ultima modificare: Februarie 25, 2011, 19:39:54 de către Ionescu Vlad » Memorat
gorgovan
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 37



Vezi Profilul
« Răspunde #6 : Februarie 25, 2011, 18:05:51 »


- Light2:
Eu m-am gindit la principiul includerii si excluderii, formula este:
sol = P[ d1 ] + P[ d2 ] + ... + P[ dK ] - 2 * P[ cmmmc(d1, d2) ] - 2 * P[ cmmmc(d1, d3) ] - ... - 2 * P[ cmmmc(dK-1, dK) ] + 4 * P[ cmmmc(d1, d2, d3) ] + 4 * P[ cmmmc(d1, d2, d4) ] + ...
unde P[ x ] = numarul de numere divizibile cu x de la 1 pina la N.
In general, pentru toate numerele de la 1 la (1 << K), daca descompunerea in baza 2 are B biti, atunci daca B este impar, adaug la solutie 2^(B-1) * P[ cmmmc(D[x1], D[x2], ..., D[xB]) ], iar daca B este par atunci scad din solutie 2^(B-1) * P[ cmmmc(D[x1], D[x2], ..., D[xB]) ] (x1, x2, ..., xB = pozitiile bitilor care au valoarea 1).


Ah! Era cu puterile lui 2 Aha. Un pic daca mai insistam si era super. Cred ca era solutia de 100.

Multumesc pentru raspuns!
« Ultima modificare: Februarie 25, 2011, 22:55:57 de către Aurelian Namascu » Memorat
Lgreg
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #7 : Februarie 25, 2011, 18:10:29 »

Si eu am facut rezolvarea cu principiul includerii si excluderii dar am luat 80 din 100 din cauza timpului. Este vreo optimizare care trebuie sa o faci sa iei 100 sau ce? Very Happy
Thanks Very Happy
Memorat
Lgreg
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #8 : Februarie 25, 2011, 22:42:45 »

Cand se modifica ratingu? Smile
Memorat
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #9 : Februarie 25, 2011, 22:51:47 »

Citat
Cand se modifica ratingu?

In cursul zilei de maine sau duminica.
Tot atunci vor fi adaugate si problemele in arhiva.
Memorat
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #10 : Februarie 26, 2011, 07:34:31 »

Si eu am facut rezolvarea cu principiul includerii si excluderii dar am luat 80 din 100 din cauza timpului. Este vreo optimizare care trebuie sa o faci sa iei 100 sau ce? Very Happy
Thanks Very Happy

Trebuie sa faci in 2^K (eventual cu back recursiv si sa tii cmmmc-ul la parametru), si nu in 2^K * K.
Solutiile mele:

- Walls:
Pentru un tun fixat la (x, y), evident pot trage doar in turnurile care se afla la stinga lui x, si astfel caut binar cel mai din dreapta turn astfel incit sa fie la stinga lui x. Fie acesta TT. Acum ma intereseaza sa caut cel apropiat turn de coordonata tunului (x) din intervalul [1, TT], cu H[turn] >= y.
Astfel fac o cautare binara, limita inferioara = 1, limita superioara = TT. Testez pe intervalul [mijloc, TT] care este cel mai inalt turn (facind un query pe un arbore de intervale), daca acest cel mai inalt turn este >= y, atunci il retin ca solutie (adica turnul in care va urma sa trag) si restring intervalul (limita inferioara = mijloc + 1), altfel nu imi convine si caut intr-un interval mai mare (limita superioara = mijloc - 1).
Daca nu am gasit niciun turn cu propr respectiva, atunci afisez MISS. Sa zicem ca am gasit un turn, il notez cu T. Evident eu trag acum un shot pe linia y a acestui turn T. Imi tin un map<pair<int, int>, int> shot, unde imi notez de cite ori am tras in linia y a turnului x (adica shot[ make_pair(x, y) ]). Acum mai trag o data, deci shot[ make_pair(TURN, y) ] ++. Daca shot[ make_pair(TURN, y) ] = W[TURN], atunci nivelul se distruge, H[TURN] devine = y-1 si updatez in arborele de intervale noua inaltime.
Cum sunt maxim 200.000 de shoturi, in map nu ar trebui sa retin mai mult de 200.000 de entry`uri, asa ca memoria nu ar trebui sa fie o problema (sincer nu am trimis inca sursa caci nu e problema adaugata in Arhiva, deci este posibil sa ma insel Smile).
Complexitate: N * log^2N.

Astept sa apara problemele in arhiva ca sa vad mai exact cite puncte obtin pe aceste idei. Daca observati vreo greseala, nu ezitati sa ma corectati Very Happy

Toate cele bune!
Vlad.

Prima parte a solutiei tale (cea cu cautarea binara si query-ul in arborele de intervale) se poate rezolva in O(logN), desi cred ca si O(log^2 N) intra in timp. Faci 2 query-uri pe arborele de intervale. Primul dintre ele iti spune cel mai din dreapta interval complet inclus in intervalul tau de query, care are maximul >= y. In total sunt maxim O(logN) intervale ale arborelui complet incluse in query-ul tau, asa ca pana acum avem O(logN). In cel de-al 2-lea query cautam raspunsul in intervalul gasit in pasul anterior. Stiind ca toate elementele sale sunt "bune" putem face urmatoarea chestie: verificam maximul din fiul drept, daca e mai mare decat y mergem in dreapta, daca nu, inseamna ca cel din fiul stang sigur e bun si mergem acolo. Asta este tot O(logN), inaltimea maxima a arborelui.

Sper ca am fost suficient de explicit.  Smile
Memorat
Lgreg
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #11 : Februarie 26, 2011, 08:30:43 »

Si eu am facut rezolvarea cu principiul includerii si excluderii dar am luat 80 din 100 din cauza timpului. Este vreo optimizare care trebuie sa o faci sa iei 100 sau ce? Very Happy
Thanks Very Happy

Trebuie sa faci in 2^K (eventual cu back recursiv si sa tii cmmmc-ul la parametru), si nu in 2^K * K.

Multumesc!:)
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #12 : Februarie 26, 2011, 15:25:51 »

Stiu ca ieri nu se stia exact dar azi poate e decis. Cand se modifica rating-ul ca sunt nerabdator?
Memorat
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #13 : Februarie 26, 2011, 18:35:04 »

Probabil in seara aceasta.
Memorat
vladii
Echipa infoarena
De-al casei
*****

Karma: 32
Deconectat Deconectat

Mesaje: 141



Vezi Profilul
« Răspunde #14 : Februarie 26, 2011, 18:58:29 »

Prima parte a solutiei tale (cea cu cautarea binara si query-ul in arborele de intervale) se poate rezolva in O(logN), desi cred ca si O(log^2 N) intra in timp. Faci 2 query-uri pe arborele de intervale. Primul dintre ele iti spune cel mai din dreapta interval complet inclus in intervalul tau de query, care are maximul >= y. In total sunt maxim O(logN) intervale ale arborelui complet incluse in query-ul tau, asa ca pana acum avem O(logN). In cel de-al 2-lea query cautam raspunsul in intervalul gasit in pasul anterior. Stiind ca toate elementele sale sunt "bune" putem face urmatoarea chestie: verificam maximul din fiul drept, daca e mai mare decat y mergem in dreapta, daca nu, inseamna ca cel din fiul stang sigur e bun si mergem acolo. Asta este tot O(logN), inaltimea maxima a arborelui.

Sper ca am fost suficient de explicit.  Smile


Smecher, GJ Cezar!
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #15 : Februarie 26, 2011, 20:56:09 »

Stiu ca ieri nu se stia exact dar azi poate e decis. Cand se modifica rating-ul ca sunt nerabdator?

S-au updatat ratingurile acum.
Memorat
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #16 : Martie 02, 2011, 21:10:03 »

Din cauza unei neatentii testele de la problema walls nu erau cele care au fost folosite in concursul on-site, si aveau strecurate cateva greseli (nu respectau niste restrictii). In consecinta testele au fost schimbate, problema reevaluata si ratingurile updatate.
Ne cerem scuze pentru neplacerile provocate si multumim lui Eugenie Posdarascu si Serban Stan pentru atentionarea cu privire la teste.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines