Solutii Summer Challenge 2020

• Lista de probleme
• Groaza
• Voodoo
• Expand

Solutia problemei Groaza

Solutia de 100 de puncte construieste mai intai o linie de N - 1 muchii (1 - 2, 2 - 3, ..., (N-1) - N) si apoi construieste, pe cat posibil, o clica din primele noduri. Cu alte cuvinte, urmatoarele muchii sunt alese asa:

• 3 - 1
• 4 - 2
• 4 - 1
• 5 - 3
• 5 - 2
• 5 - 1
• 6 - 4
• 6 - 3
• etc...

Nota. O solutie asemanatoare, care construieste clica la mijlocul liniei, obtine in jur de 71 de puncte.

Bonus. Gasiti o solutie si mai buna sau demonstrati ca cea care acum ia 100 de puncte nu poate fi depasita ca performanta.

Solutia problemei Voodoo

Pentru început, trebuie să analizăm cum ar arăta funcţia G_B(N). O să analizăm cazul B = 10 pentru a ne fi mai uşor de vizualizat, chiar dacă nu o să fie în teste.

• G₁₀(0) = 1
• G₁₀(1) = 10
• G₁₀(2) = 19
• G₁₀(3) = 199
• G₁₀(4) = 1999...9 (de 22 de ori)

De la un punct încolo, putem să observăm deja o formă generală: G începe cu 1 şi este urmat de mai mulţi de 9.

Demonstraţie

I) Fie X < Y. Atunci cel mai mic număr cu suma cifrelor X este mai mic decât cel mai mic număr cu suma cifrelor Y.

Putem genera cele mai mici numere folosind o strategie greedy, pentru început minimizăm numărul de cifre. Pentru asta, vom folosi cât mai multe cifre de 9. Numărul de cifre de 9 va fi [X / 9], iar prima cifră va fi x % 9, asta dacă e diferită de 0. Dacă cele două numere au acelaşi număr de cifre, atunci cel cu suma cifrelor X va fi mai mic, deoarece restul lui la împărţirea cu 9 va fi mai mic. Altfel Y va avea mai multe cifre şi va fi mai mare.

II) Restul unui număr X la împărţirea cu 9, va fi egal cu restul sumei cifrelor lui X la împărţirea cu 9. Pentru a generaliza problema, restul unui număr la împărţirea cu B, va fi egal cu restul sumei cifrelor lui X în baza B la împărţirea cu B.

Această afirmaţie poate fi demonstrată prin inducţie. Pentru numerele de la 0 până la B - 2, afirmaţia este evidentă. Dacă adăugăm repetat la aceste numere B - 1, avem următoarele cazuri:

• Cea mai din dreapta cifră creşte cu B - 1 şi nu avem transport, caz în care suma cifrelor creşte cu B - 1 şi restul se păstrează.
• Cea mai din dreapta cifră, care la început să zicem că e t, creşte cu B - 1, dar după trebuie să ducem transport la următoarea cifră, altfel ea va deveni t + B - 1 - B = t - 1, deci ea scade cu 1, dar următoarea cifră va creşte cu 1 şi nu va duce transport în continuare. În acest caz suma cifrelor rămâne aceeaşi.
• Se întâmplă toate lucrurile din cazul anterior, dar a doua cifră va duce transport, deci ea se va transforma în t + 1 - B = t - 1, dar cifra următoare va creşte cu 1 şi nu va duce transport, deci suma cifrelor scade cu B - 1 şi restul se păstrează.
• ...

III) G₁₀(N) = 199999...9 pentru N ≥ 2, sau, generalizat, G_B(N) = 1(B-1)(B-1)(B-1)...(B-1) în baza B.

Folosindu-ne de I) şi II), putem genera într-un mod recursiv pe G_B(N), fixându-i suma cifrelor ca fiind G_B(N - 1). Putem demonstra într-un mod inductiv faptul că numărul va avea forma de mai sus:

• G_B(2) = 1(B-1) în baza B
• G_B(N) va avea multe cifre de B - 1 la sfârşit, rămâne de demonstrat faptul că prima cifră va fi 1. Aceasta va fi defapt restul sumei cifrelor la (B - 1). Cum G_B(N - 1), care este şi suma cifrelor lui G_B(N), este format dintr-un singur 1 şi multe cifre de B - 1, atunci, folosind II), restul lui la împărţirea cu B - 1 va fi restul sumei cifrelor sale la împărţirea cu B - 1, deci prima cifră va fi 1.

Soluţie de 20 de puncte

O primă soluţie care ne-ar veni în minte ar fi să implementăm modul de construcţie inductivă de mai sus.

Soluţie de 70 de puncte

Vom analiza în continuare G₁₀(N) şi vom încerca să rescriem funcţia.

• G₁₀(2) = 19 = 1 + 9 * 2 * 1 = 1 + 9 * 2 * H₁₀(0)
• G₁₀(3) = 199 = 1 + 9 * 2 * 11 = 1 + 9 * 2 * H₁₀(1)
• G₁₀(4) = 1999...9 (de 22 de ori) = 1 + 9 * 2 * 1111...1 (de 22 de ori) = 1 + 9 * 2 * H₁₀(2).

Aici este introdusă o nouă funcţie: G₁₀(N), care nu are o semnificaţie chiar clară, dar putem să deducem recurenţa.

• H₁₀(0) = 1
• H₁₀(N) = 1111...1 (de 2 * H₁₀(N - 1) ori)

Generalizând, obţinem:

• H_B(0) = 1
• H_B(N) = 1111...1 (de 2 * H_B(N - 1) ori, în baza B)

IV)Formulă pentru 1 + X + X² + ... + X^K

S = 1 + X + X² + ... + X^K
X * S = X + X² + ... + X^{(K + 1)}
=> (X - 1) * S = X^{(K + 1)} - 1
=> S = (X^{(K + 1)} - 1) / (X - 1)

Astfel, folosind IV), obţinem H_B(N) = (B^{2 * H_B(N - 1)} - 1) / (B - 1).

Aici intervin mai multe probleme cu operaţia de modulo:

• Dacă (B - 1) nu este divizibil cu 3, atunci putem să folosim orice tehnică de a calcula inversul modular, aceasta poate fi fie cu algoritmul lui Euclid, fie folosind Teorema lui Euler, metodă folosită şi explicată aici
• Dacă (B - 1) este divizibil cu 3, nu putem folosi inversul modular la împărţirea cu 3.
• Dacă B este divizibil cu 3, atunci nu putem folosi teoreme legate de modulo precum Fermat sau Euler.

Dacă B este divizibil cu 3, atunci pe noi ne intereseaza doar ultimele T cifre în baza B, unde M = 3^T. Putem folosi un brut, deoarece T este maxim 12.

Dacă B - 1 este divizibil cu 3, atunci putem calcula partea de sus a fracţiei, adică (B^{2 * H_B(N - 1)} - 1) modulo (3 * M). Astfel, partea de sus va fi de forma (3 * M) * K + R, R < 3 * M, unde noi cunoaştem doar R, deci (B^{2 * H_B(N - 1)} - 1) / 3 = M * K + (R / 3). Pe scurt, ca să calculăm totul modulo M, trebuie să calculăm partea de sus a fracţiei modulo (3 * M), iar după restul pe care îl obţinem sus îl împărţim la 3. Cum B este de forma 3 * K, ca să facem împărţirea şi prin K, folosim metoda inversului modular.

În continuare, pentru a calcula rezultatul modulo M, partea de sus a fracţiei va fi calculată modulo 3 * M sau modulo M, în funcţie de ce caz ne aflăm. Astfel, noi va trebui să folosim teorema lui Euler. Astfel, pentru a calcula B^{2 * H_B(N - 1)} modulo M sau 3 * M, va trebui să calculăm B^{2 * H_B(N - 1)} modulo phi(M) sau phi(3 * M). Cum M este de forma 3^T, atunci phi(M) = 2 * 3^T, ba chiar mai mult, phi(phi(M)) = 2 * 3^T ş.a.m.d. Aşadar, în cazul în care B - 1 este divizibil cu 3, putem calcula totul modulo 2 * M. În cazul în care B = 3 * K + 2, atunci, în realitate, vom putea în continuare să calculăm funcţia modulo M, fără să trecem la phi(M), datorită acelui 2 de lângă H_B(N - 1).

Ca o scurtă recapitulare, avem grijă în ce caz ne încadrăm, şi după calculăm H_B(0), H_B(1), ..., H_B(N - 2), toate modulo M sau 2 * M . Cum calculăm N - 2 valori diferite ale funcţiei şi avem nişte ridicări în timp logaritmic, complexitatea acestei soluţii va fi O(N * logM).

Soluţie de 100 de puncte

Pentru a calcula H_B(N), ne folosim doar de o variabilă, şi anume de H_B(N - 1). Dacă la un moment dat în timp ce calculăm şirul H_B găsim un element care se repetă, atunci ştim că şirul o să cicleze. Astfel, trebuie calculate doar M elemente, deci complexitatea finală va fi O(M * logM).

Părţile colorate astfel reprezintă cazuri particulare care dacă nu sunt tratate cum trebuie, atunci se pot greşi teste.

Solutia problemei Expand

O soluţie care merge bine pe poligoane regulate este să calculăm un punct G ca fiind media aritmetică a tuturor vârfurilor poligonului (adică abscisa lui G este media aritmetică dintre abscisele tuturor vârfurilor, la fel şi ordonata lui G este media aritmetică dintre ordonata tutoror vârfurilor), şi să mutăm fiecare punct diametral opus faţă de G. Această soluţie ar obţine aproximativ 44 de puncte.

O idee ar fi să luăm mai multe puncte potenţiale pentru fiecare vârf, apoi ne fixăm un vârf şi calculăm o dinamică de tipul dp[i][j] = aria maximă pe care o putem obţine dacă am fixat primele i vârfuri, iar vârful i l-am fixat în al j-lea punct potenţial pentru el. Cea mai bună soluţie implementată de comisie pe această idee obţine 76 de puncte.

O altă idee ar fi să incercăm să fixăm optim fiecare vârf în felul următor : fie 3 vârfuri consecutive A, B, C. Considerăm că A şi C sunt fixate. Ducem perpendiculara din B pe AC şi îl mutăm pe B în punctul B' de pe perpendiculara care se află la distanţa R faţă de B (cum sunt două puncte B', îl alegem pe cel mai depărtat faţă de dreapta AC). Pentru o soluţie cât mai bună, repetăm de mai multe ori strategia asta. O soluţie de genul ar trebui să obţină 100 de puncte. Fără a repeta de mai multe ori strategia se obţin ~92 de puncte.