noi avem deja doua

Mai bagati inca 2. Doar la 4 surse corecte schimbam testele.

sigur testeke sunt bune?

Le puteti verifica chiar voi cu o sursa corecta!

Da, si liniile si coloanele!

Spre exemplu, amplasamentul (pe exemplul din enunt):

[111]0011000

este valid.

(Incepe in sir pe pozitia 1 si se termina pe pozitia 3).

Mult succes!!! 

[Runda 6]

Runda 6 a concursului Monthly 2012 s-a încheiat. Felicitări primilor clasați!

Premiul special oferit de catre firma IXIA va merge la Heidelbacher Andrei, deoarece a rezolvat problema Impartiri avand penalizarea (56 de puncte) cea mai mica! Felicitari!

Asteptam opiniile si eventualele sugestii ale voastre în legatura cu organizarea, subiectele propuse și orice probleme intampinate.

Mult succes în continuare!

Cum intre doua noduri poate exista cel mult o muchie, atunci nu va putea exista un ciclu format doar din 2 noduri.

NU NEAPARAT!

Succes tuturor!!!

Super runda, mie unul mi-a facut aceasta dupa-amiaza mai frumoasa!

Go2 -> nu am inteles enuntul, nu m-am gandit, nu am bagat nicio sursa )
Muncitori -> draguta problema
Puteri3 -> frumoasa, destul de grea, insa nu destul de originala
Spirala3 -> desi am complexitate de O(N^4) pe problema aceasta, nu am scos mai mult de 50 de puncte (se pare ca nimeni nu a scos). Cred ca limita de timp ar fi trebuit sa nu fie atit de strinsa, tinand cont ca a fost o problema grea (si o sursa mai dezordonata ca a mea ar fi trebuit sa intre in timp ^_^).

Felicitari organizatorilor! 

Foarte misto runda asta, mi se pare cea mai tare de pina acum! Problemele chiar marfa, mai ales Bal si Swaps!

Keep up the good work!

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!

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.

Rezolvarea mea in N^3:
Distanta intre doua drepte paralele (daca stim panta si un punct de pe ele) este:
d = |A * x0 + B * y0 + C| / sqrt(A*A + B*B);
unde Ax + By + C = 0 este ecuatia uneia dintre drepte si (x0, y0) un punct de pe cealalta dreapta.
Cu niste mici modificari, ajungem la:
d = |m * c1 - c2| / sqrt(m*m + 1);
unde m = panta dreptelor si c1 = x0 - x1, c2 = y0 - y1 (coordonatele punctelor de pe cele doua drepte).
Am luat acum o functie:
f(m) = |m * c1 - c2| / sqrt(m*m + 1)
si am incercat sa ii gasesc monotonia. f(m) > 0 oricare ar fi m (pentru ca f(m) reprezinta defapt o distanta), deci daca f(m) ^ 2 este monotona pe un anumit interval, si f(m) este. Deci am derivat pe f(m) ^ 2 si am aflat radacinile derivatei: sa le notam cu R1 si R2. Ceea ce inseamna ca in punctele R1 si R2 este posibil ca functia sa isi schimbe monotonia (adica sa avem un maxim local sau minim local).
Deci un prim pas in algoritm consta in alegerea tuturor perechilor de puncte (i, j), determinarea radacinilor derivatei functiei f^2 (radacinile reprezinta defapt niste PANTE) si apoi vedeam in O(N) daca intre dreptele de panta R1 si R2 care trec prin punctele i si j exista vreun alt punct. Daca nu, era o asezare valida, calculam distanta intre aceste doua drepte si o comparam cu solutia.
Acum sa zicem ca avem doua drepte de panta m care trec prin doua puncte i si j. Daca rotim aceste drepte (adica marim sau scadem panta), evident vom forma intervale compacte (pentru panta). Ceea ce inseamna ca f(m) poate fi maxim doar daca dreapta care trece prin i mai trece si printr-un alt punct p, sau daca dreapta care trece prin j mai trece prin alt punct k, sau poate fi maxim intr-un punct oarecare dintre k si p, dar acest punct poate forma ori panta R1, ori R2, ceea ce noi am calculat deja .
Deci folosind aceasta observatie, luam toate perechile de puncte (i, j) astfel incit o dreapta sa treaca SI prin punctul i SI prin punctul j, si calculam in O(N) dreptele de aceeasi panta ca dreapta (i, j) si vedem pentru care dintre aceste drepte nu exista niciun punct intre dreapta (i, j) si ele, apoi calculam distanta si comparam cu solutia.

Cam asta este rezolvarea mea, in N^3 (sper ca nu am gresit cu nimic la calcule sau rationament), si solutia implementata pe ideea asta a luat 50p , cu TLE pe restul de teste. Partea mai nasoala este ca daca sar peste prima parte a algoritmului (adica nu mai calculez radacinile derivatei) si fac doar a doua parte, desi NU MERGE pe al 2lea exemplu din enunt, tot 50 de pcte ia .

Sunt curios si eu cum se rezolva problema (N^2, N^2 * logN ?).

Bafta!
Vlad.

Salut! Acum ca s-a terminat runda, vreau sa va intreb si eu ceva la problema Bonus.
Am avut si eu o idee, am luat 0 pe ea, dar sunt curios daca este corecta (deci am gresit la implementare) sau este gresita ca idee.

Am o functie solve(int st, int dr) care imi spune cite siruri de N elemente au gcd = 1. Stiind asta, rezultatul se obtine in genul: solve(A, D) + solve(B+1, C-1) - solve(A, C-1) - solve(B+1, D).
Acum... ce fac in solve() ? Imi tin 2 vectori
P[ i ] = numarul de elemente divizible cu i din intervalul [st, dr];
put[ i ] = i ^ N;
Numarul total de siruri este put[ dr - st + 1 ], deci daca as afla "nr" = numarul total de siruri cu N elemente cu gcd > 1, atunci solve() returneaza put[ dr - st + 1] - nr.
Ca sa aflu "nr" am facut ceva gen principiul includerii si excluderii:
nr = put[ P[2] ] + put[ P[3] ] - put[ P[2*3] ] + put[ P[5] ] - put[ P[2*5] ] - put[ P[3*5] ] + put[ P[7] ] - put[ P[2*7] ] - put[ P[3*7] ] - put[ P[5*7] ] + ...
Cu alte cuvinte, adun put[ P[ x ] ] daca x este prim si scad put[ P[ x ] ] daca x este produs de fix 2 numere prime. (evident x = 2 -> dr).

LE: Mi-am dat seama ca este gresita ultima parte, am constientizat dupa ce am stins calculatorul ), trebuia facut EXACT ca la principiul includerii si excluderii, adica adaugam put[ P[ x ] ] daca x se scria FIX ca un produs de un numar impar de numere prime diferite si il scadeam daca x se scria FIX ca un produs de un numar par de numere prime diferite (fara ca acelasi numar prim sa apara de doua ori in descompunerea lui x)...

Cam asta este tot. As fi recunoscator daca v-ati uita 2 minute peste ceea ce am scris sau daca mi-ati impartasi ideea voastra de rezolvare. Multumesc mult! Vlad.

Salut!

Am si eu nevoie de un hint la problema asta, rezolvarea mea nu merge si cred ca nici ideea nu este buna. So, orice indiciu este binevenit!

Multumesc!

LE: Am rezolvat problema in N^2 (cu un pairUp). Iau doar 10 pcte  (MLE pe restul), oricum nu ma asteptam sa iau prea multe puncte. Deci... care-i jmenul pentru 100?

Am rezolvat problema asta acum mult timp, dar m-am uitat in sursa si eu am luat 100 cu urmatoarea sortare:

Cod:

int Produs(Puncte P1, Puncte P2, Puncte P3) {
    return P2.x*P3.y - P2.x*P1.y - P1.x*P3.y + P1.x*P1.y - 
           P3.x*P2.y + P3.x*P1.y + P1.x*P2.y - P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
    if((a.x-P[1].x)*(b.y-P[1].y)!=(b.x-P[1].x)*(a.y-P[1].y)) {
         return (a.x-P[1].x)*(b.y-P[1].y) > (b.x-P[1].x)*(a.y-P[1].y);
    }
    else if(P[1].y==a.y && P[1].y==b.y) {
         return (a.x-P[1].x)*(a.x-P[1].x) + (a.y-P[1].y)*(a.y-P[1].y) <
                (b.x-P[1].x)*(b.x-P[1].x) + (b.y-P[1].y)*(b.y-P[1].y);
    }
    else if(!Produs(a, b, P[1])) {
          return a.x<b.x;
    }
}

P[1] este punctul din stinga jos.

Poate te ajuta cu ceva. Bafta !

E ok ideea, insa cred ca gresesti ceva pe la coada de prioritati. Am implementat aceeasi sursa, dar in loc de coada am folosit multiset (pe post de heap) si imi dadea ok.

Oricum, am luat 100 cu sursa ta facind mici modificari (si pastrind priority_queue`ul). Uite aici: http://infoarena.ro/job_detail/482815?action=view-source ! Poate te ajuta cu ceva.
Nu stiu insa ce greseai tu in sursa ta (probabil ca la functia cmp, insa nu stiu sa rezolv).

Bafta!
Vlad.

Cum sa o implementez cu memoizare? Nu stiu, nu ma prind deloc la problema asta... Daca vrei, da-mi te rog un pic mai multe detalii.

LE: Am incercat sa memoizez si cu solve(stare) si cu solve(stare, nod). Cu solve(stare, nod) merge foarte greu pe calculatorul meu, iar cu solve(stare) merge aproximativ la fel ca dinamica fara memoizare. "stare" este un numar in baza 2, iar pentru fiecare "stare" parcurg toate numerele de la 1 la 2^(nrbiti) pentru a-mi forma stari de triti. Cred ca ramin la 40 de puncte la problema aceasta

Multumesc!
Vlad.

Salut!
Complexitatea mea la problema aceasta (la fel ca si in solutia oficiala) este de 3^N * N^2 si primesc OK doar pe primele 4 teste, pe restul am TLE. Nu am nici o idee despre ce sa mai optimizez... So, un hint ar fi foarte bine venit! Am vazut ca mai sunt useri care au facut saltul de la 40 la 100 de puncte si as vrea sa stiu si eu cum.

Multumesc!
Vlad.

In enunt scrie ca este o permutare Cauta intr-un manual de mate sau pe net despre permutari si ai sa intelegi mai bine.

M-am uitat pe teste si se incepe mereu cu punctul cel mai din stinga - jos. Intr-adevar in enuntul problemei nu se incepe cu acel punct si poate induce lumea in eroare . Dar oricum, din modul de functionare al algoritmului (Graham), cind introduci prima data exact acel punct in stiva (si care evident nu va mai fi scos niciodata), se poate da seama care va fi primul punct care trebuie afisat.

LE: Scuze, acum (si inainte, nu stiu sigur, nu m-am uitat) exista un evaluator si cred ca se poate incepe cu orice punct

Si cred ca pentru intreaga arhiva educationala si pentru intreaga infoarena s-a depus destul efort, btw.

Ai omis un mic detaliu:
"Pe urmatoarele H linii se vor gasi cele H puncte ce alcatuiesc poligonul, in ordine trigonometrica.".

Elementele permutarii apartin multimii: {1, 2,.., N} (fiecare numar apare exact o data). Deci nu sunt o infinitate de posibilitati.


In cazul exemplului din enunt rezultatul este chiar 8, tinind cont ca N este destul de mic (5).

Salut!
Vreau si eu un hint la problema asta...
M-am prins de solutia de 30 de pcte (adica de dinamica aceea pentru radacina fixata). Iau 50 de pcte daca imi fixez radacina doar in nodul 1 si maxim 70 de puncte daca fac un random si imi selectez citeva noduri drept radacina (si imi aleg solutia cea mai buna).
Care ar fi ideea pentru O(N) ? Am citit solutia oficiala, dar nu prea inteleg cum calculez optim noua valoare pentru o noua radacina (vecina cu vechea radacina).
Multumesc!