Infoarena Monthly 2014, Runda 7

[•Teodor94]

Runda 7 va avea loc Joi, 31 iulie la ora 19⁰⁰.
Va uram mult succes!  

[•scipianus]

Ce bine s-a nimerit, la ora aia sunt pe drumul din Bulgaria spre casa 

[•narcis_vs]

Bancul zilei : " ATENTIE! Trebuie sa te inscrii inainte de ora 19:00 daca doresti sa ti se modifice rating-ul in urma participarii! " - Infoarena, 2014.

[•SebiSebi]

Felicitări pentru rundă! 
A fost una dintre cele mai frumoase runde de Monthly la care am participat. Ar fi fost super dacă am fi avut putin mai mult timp la dispoziție.

[•Andrei1998]

Felicitari pentru runda, foarte reusita .  Problema 1 era cum trebuie sa fie prima - simpla si "ok", sa nu fie plina de cazuri particulare. A doua a fost parca prea mult mate (trebuia sa stii putin despre teorema lui Bezout + Euclid extins + ecuatii pell ca sa o faci, poate m-am complicat, dar oricum demonstratia solutiei e destul de matematica). Rog sa puneti problemele in arhiva cat de curand (vreau sa vad daca CE-ul din ultima secunda la problema 2 era de 100). A treia a fost cam "scarboasa" adica ideea iti venea imediat dar trebuia sa fii foarte dibace sa nu gresesti nimic. Ultima ma duce cu gandul la FFT (nu m-am gandit mult prea mult la ea). Felicitari autorilor + tuturor celor care au participat la crearea si desfasurarea rundei.

P.S. : "Rating is a lie." (ca raspuns la cea a zis Narcis mai sus, mi-a luat ceva sa ma prind dar a meritat ).

[•ctlin04]

Cum se face problema 1 ca nu am avut nici o idee la ea (poate doar suma^n) dar nu am implementat?? 
Cit despre problema 3 mi s-a parut destul de draguta, cel putin mie mi s-a parut cea mai usoara. 

[•GavrilaVlad]

Mai citesc gresit enuntul si in loc de "fiecare are voie sa aleaga doar o felie adiacenta cu portiunea de pizza deja extrasa" inteleg "fiecare are voie sa aleaga doar o felie din marginea intervalului ramas"  Spre apararea mea, ma asteptam ca a treia problema sa fie ceva mai dificila.

Oricum, felicitari pentru runda - problemele au fost tare simpatice, in special ultima. Eu am facut O(N*sqrt(N)*K) cu hash-uri si impartind sirul A in bucati de radical. Care era solutia oficiala?

[•Andrei1998]

La prima problema formula chiar era Suma^n.
Iata de ce:
Sa zicem ca avem cele n cutii: x1 x2 ... xn
Acum incercam sa enumeram toate produsele necesare: (fie a1 ... am cele m numere distincte)
a1 * a1 * ... * a1 (de n ori)
a1 * a1 * ... * a2 (de n ori)
...
a1 * a1 * ... * a2 * a1 (de n ori)

Altfel scris (notam cu S(i,a,b) sigma dupa i ia valori de la a la b):
S(i,1,m) S(j,1,m) S(k,1,m) * ... * S(p,1,m) [ai*aj*ak* ... * ap] (n sigme)
Si cum sigma produsului e produs de sigme, ajungem la formula (Suma totala)^n

Pot sa detaliez daca e cineva interesat.

[•vendetta]

Partial match se mai poate face si cu suffix array. Sa zicem ca esti la pozitia i in A si la pozitia j in B vrei sa afli cate caractere sunt la fel. Poti afla folosindu-te de suffix array.

[•ctlin04]

Mda  , mai bine implementam, am intuit formula dar nu stiam cum se demonstreaza si am crezut ca e doar o parere gresita care merge doar pe exemplu, in fine mersi pentru explicatie si daca ai mai detalia un pic demonstratia cred ca ar fi foarte ok, sau poate o sa fie o demonstratie completa in articolul cu solutii oficiale.

[•maritim]

Problema Partial Match se putea rezolva si cu cautare binara folosind aceeasi idee pe care ai expus-o tu Vlad . Se cautau binar pentru fiecare subsecventa posibila cele K (maxim) puncte de nepotrivire folosind algoritmul lui Rabin-Karp . Mai existau si alte solutii, una dintre ele a fost expusa de Razvan.

Revenind la desfasurarea rundei, ne cerem scuze pentru aprecierea gresita a dificultatii problemelor. Intradevar primele doua probleme au fost putin mai grele decat ar fi trebuit, iar a treia a fost mai usoara decat trebuia sa fie o problema de nivel 3 pe rang de dificultate.

Multumim pentru feedback-ul constructiv si o sa incercam pe viitor sa apreciem intr-un mod mai corect dificultatea problemelor .

[•heisenberg]

Si la antobroasca care era solutia oficiala? Intreb pentru ca in solutia mea, care implica rezolvarea a doua ecuatii cu algoritmul lui euclid extins, aveam probleme cu anumite numere intermediare care se pare ca ieseau din long long.  

[•maritim]

Rezolvarea problemei Antobroasca se reducea la a raspunde daca urmatorul sistem de ecuatii are solutii

• Zc + Xa = A
• Zc + Yb = B

cu precizarea ca sunt 3 necunoscute (a, b, c). Pentru a nu avea un sistem in care ai 3 necunoscute si 2 ecuatii vom incerca sa obtinem o a treia ecuatie scazand prima ecuatie din a doua

• Yb - Xa = B-A

Ca raspunsul sa fie afirmativ la intrebarea problemei trebuie ca fiecare din aceste 3 ecuatii sa aiba solutii in Z.

Pentru a verifica daca o ecuatie de forma ax + by = c accepta solutii in Z pentru x si y este suficient sa verifici daca c este divizibil cu cmmdc(a,b) . Aceasta este solutia oficiala a problemei.

[•szili]

La prima problema eu m-am gandit in felul urmator: In fiecare pozitie trebuie sa avem unul din cele m numere. Un numar oarecare X pe pozitia aia o sa apara de M^(N-1) ori pentru ca pe ficeare din celelalte pozitii pot sa pun orice. Asta ii adevarat pentru fiecare numar => pentru suma de pe o pozitie avem SUM *N^(M-1). Din cauza ca avem N pozitii in total, formula va fi: N * SUM * N^(M-1). (SUM -reprezinta suma tuturor numerelor) Ma puteti ajuta va rog ce gresesc in formula aceasta si la cum am ajuns la ea? Trec 2 teste dar celelalte nu.

[•poptibi]

Rezolvarea problemei Antobroasca se reducea la a raspunde daca urmatorul sistem de ecuatii are solutii

• Zc + Xa = A
• Zc + Yb = B

cu precizarea ca sunt 3 necunoscute (a, b, c). Pentru a nu avea un sistem in care ai 3 necunoscute si 2 ecuatii vom incerca sa obtinem o a treia ecuatie scazand prima ecuatie din a doua

• Yb - Xa = B-A

Ca raspunsul sa fie afirmativ la intrebarea problemei trebuie ca fiecare din aceste 3 ecuatii sa aiba solutii in Z.

Pentru a verifica daca o ecuatie de forma ax + by = c accepta solutii in Z pentru x si y este suficient sa verifici daca c este divizibil cu cmmdc(a,b) . Aceasta este solutia oficiala a problemei.

De ce daca cele 3 ecuatii au solutii in Z, inseamna ca tot sistemul are cel putin o solutie?

[•Zenus]

Deci eu m-am gandit la problema antobroasca ca daca modul(A) divide cmmdc(x,z) si modul(B) divide cmmdc(y,z) atunci DA.. altfel NU. Imi puteti da un contraexemplu pentru ideea asta ? 

[•narcis_vs]

La rundele 6 si 7 primele 2 probleme se faceau cu formula. La runda 8 se vor da 3 probleme care se rezolva cu formula sau e ok ca la un concurs de info jumatate din setul de probleme sa se rezolve cu formule?

[•SRadu]

Exista o demonstratie riguroasa pentru problema a 2-a de ce daca toate alea au solutie in Z atunci exista solutie pentru intregul sistem?

Eu am incercat o rezolvare cu algoritmul lui Euclid extins care lua WA din cauza unui overflow banuiesc. Mi se pare ca trebuiau limitele alese astfel incat si aceasta rezolvare sa ia 100 de puncte.

PS Vrem articol cu solutiile 

[•Al3ks1002]

Solutia mea pentru problema a doua este urmatoarea:

Mai intai facem sistemul:

A = a*X + b1*Z
B = c*Y + b2*Z

Aplicam algoritmul lui Euclid extins pentru ambele ecuatii si obtinem niste valori pentru a,b1,b2,c.
Acum, pentru a afisa "DA" trebuie sa vedem daca b1 poate fi egal cu b2.

Ambele ecuatii au o infinitate de solutii, deci sistemul devine:

A = (a + k1*Z/d1)*X + (b1 - k1*X/d1)*Z
B = (c + k2*Z/d2)*Y + (b2 - k2*Y/d2)*Z,
unde d1=cmmdc(X,Z), d2=cmmdc(Y,Z) si k1,k2 intregi.

Punem conditia ca b1 - k1*X/d1 = b2 - k2*Y/d2.
Notand F=X/d1 si G=Y/d2 ajungem la:

b1 - k1*F = b2 - k2*G <=>
<=> b1 - b2 = k1*F - k2*G

Aplicam algoritmul lui Euclid extins pe aceasta ecuatie.
Daca gasim solutie cu k1,k2 intregi, atunci afisam "DA".

Facand toate calculele pe long long, mi-a intrat solutia asta de 100p (dupa concurs).

[•Impaler_009]

Solutia mea pentru problema a doua este urmatoarea:

Mai intai facem sistemul:
A = a*X + b1*Z
B = c*Y + b2*Z

Aplicam algoritmul lui Euclid extins pentru ambele ecuatii si obtinem niste valori pentru a,b1,b2,c.
Acum, pentru a afisa "DA" trebuie sa vedem daca b1 poate fi egal cu b2.

Ambele ecuatii au o infinitate de solutii, deci sistemul devine:
A = (a + k1*Z/d1)*X + (b1 - k1*X/d1)*Z
B = (c + k2*Z/d2)*Y + (b2 - k2*Y/d2)*Z,
unde d1=cmmdc(X,Z), d2=cmmdc(Y,Z) si k1,k2 intregi.

Punem conditia ca b1 - k1*X/d1 = b2 - k2*Y/d2.
Notand F=X/d1 si G=Y/d2 ajungem la:

b1 - k1*F = b2 - k2*G <=>
<=> b1 - b2 = k1*F - k2*G

Aplicam algoritmul lui Euclid extins pe aceasta ecuatie.
Daca gasim solutie cu k1,k2 intregi, atunci afisam "DA".

Facand toate calculele pe long long, mi-a intrat solutia asta de 100p (dupa concurs).

Ca tine am rezolvat-o si eu. Este necesar insa sa demonstrezi ca toate solutiile posibile pentru b1 din aX + b1Z = c sunt de forma b1 (aflat din euclid extins) + r*X/cmmdc(X,Z) cu un r ales de tine.

Fie aX + bY = c cu a si b solutii.
Incercam sa variem solutia: (a+a0)X + (b+b0)Y = c (trebuie sa le variem pe ambele pentru ca ecuatia sa se pastreze)
=> a*X + a0*X + b*Y + b0*Y = c
   Scadem a*X + b*Y = c
=> a0*X + b0*Y = 0
=> a0*X = -b0*Y = r*cmmmc(X,Y)
=> a0 = r*cmmmc(X,Y)/X
=> a0 = r*X*Y/(cmmdc(X,Y)*X)
=> a0 = r*Y/cmmdc(X,Y)
deci orice solutie pentru a este de forma a + r*Y/cmmdc(X,Y)

[•Al3ks1002]

Solutia mea pentru problema a doua este urmatoarea:

Mai intai facem sistemul:
A = a*X + b1*Z
B = c*Y + b2*Z

Aplicam algoritmul lui Euclid extins pentru ambele ecuatii si obtinem niste valori pentru a,b1,b2,c.
Acum, pentru a afisa "DA" trebuie sa vedem daca b1 poate fi egal cu b2.

Ambele ecuatii au o infinitate de solutii, deci sistemul devine:
A = (a + k1*Z/d1)*X + (b1 - k1*X/d1)*Z
B = (c + k2*Z/d2)*Y + (b2 - k2*Y/d2)*Z,
unde d1=cmmdc(X,Z), d2=cmmdc(Y,Z) si k1,k2 intregi.

Punem conditia ca b1 - k1*X/d1 = b2 - k2*Y/d2.
Notand F=X/d1 si G=Y/d2 ajungem la:

b1 - k1*F = b2 - k2*G <=>
<=> b1 - b2 = k1*F - k2*G

Aplicam algoritmul lui Euclid extins pe aceasta ecuatie.
Daca gasim solutie cu k1,k2 intregi, atunci afisam "DA".

Facand toate calculele pe long long, mi-a intrat solutia asta de 100p (dupa concurs).

Ca tine am rezolvat-o si eu. Este necesar insa sa demonstrezi ca toate solutiile posibile pentru b1 din aX + b1Z = c sunt de forma b1 (aflat din euclid extins) + r*X/cmmdc(X,Z) cu un r ales de tine.

Fie aX + bY = c cu a si b solutii.
Incercam sa variem solutia: (a+a0)X + (b+b0)Y = c (trebuie sa le variem pe ambele pentru ca ecuatia sa se pastreze)
=> a*X + a0*X + b*Y + b0*Y = c
   Scadem a*X + b*Y = c
=> a0*X + b0*Y = 0
=> a0*X = -b0*Y = r*cmmmc(X,Y)
=> a0 = r*cmmmc(X,Y)/X
=> a0 = r*X*Y/(cmmdc(X,Y)*X)
=> a0 = r*Y/cmmdc(X,Y)
deci orice solutie pentru a este de forma a + r*Y/cmmdc(X,Y)

Da, sau asta (http://en.wikipedia.org/wiki/B%C3%A9zout's_identity#Structure_of_solutions), dar demonstratia e binevenita.

[•SRadu]

Eu am pornit de la urmatoarele ecuatii:
X * H + Z * D = A
Y * V + Z * D = B

Dupa ce am facut o scadere am ajuns la:
X * H + (-Y) * V = A - B

Am facut Euclid extins pe chestia asta.
Fie H0 si V0 solutiile gasite.

H = H0 + K * (-Y) / d
V = V0 - K * X / d
Unde d = cmmdc(X, -Y)

Acum daca inlocuim intr-una din ecuatii o sa ne dea asa:
X * H0 + K * (X * (-Y) / d) + Z * D = A
X * H0 e constant si il putem trece in partea dreapta.
Notam T = X * (-Y) / d si ajungem la ecuatia
T * K + Z * D = A - X * H0

Aplicam din nou Euclid extins pe ecuatia asta si daca si asta are solutie afisam "DA", altfel "NU".

[•DorelBarbu]

Am si eu o intrebare...unde dau click sa ma inregistrez pentru runda 8? Mi-am facut curaj sa particip dar nu m-am prins cum sa ma inscriu

[•Teodor94]

@Barbu Dorel

http://www.infoarena.ro/monthly-2014/runda-8/probleme

Click pe "Inscrie-te acum!", din chenarul galben. Va trebui sa dai din nou click pe "Confirma inscrierea" si asta ar trebui sa fie tot.

Multa bafta la runda 8!