Romanian Master of Mathematics & Sciencies 2011

[•andrei.12]

Î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!

[•R.A.R]

Un link catre pagina concursului ?

[•skull]

Un link catre pagina concursului ?

http://infoarena.ro/rmms-2011

Ai acolo si pagina oficiala.

[•DraStiK]

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

[•gorgovan]

Imi puteti spune cum se faceau Light2 si Walls?

Multumesc anticipat!

[•vladii]

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 ).
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

Toate cele bune!
Vlad.

[•gorgovan]

- 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 . Un pic daca mai insistam si era super. Cred ca era solutia de 100.

Multumesc pentru raspuns!

[•Lgreg]

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?
Thanks

[•Lgreg]

Cand se modifica ratingu?

[•andrei.12]

Cand se modifica ratingu?

In cursul zilei de maine sau duminica.
Tot atunci vor fi adaugate si problemele in arhiva.

[•CezarMocan]

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?
Thanks

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 ).
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

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. 

[•Lgreg]

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?
Thanks

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

Multumesc!:)

[•eudanip]

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

[•andrei.12]

Probabil in seara aceasta.

[•vladii]

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. 

Smecher, GJ Cezar!

[•bogdan2412]

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.

[•andrei.12]

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.