Despre două probleme de la ONI 2002: noi soluții și extinderi

Astăzi se împlinesc trei ani de când Mihai Pătrașcu ne-a părăsit. Așa cum cred că ar fi vrut, acest articol nu va fi o prezentare a carierei sale și nici o rememorare a momentelor pe care Mihai le-a petrecut împreună cu foști sau actuali membri ai redacției Gazetei de Informatică. Totuși, nu uitați să ridicați un pahar în cinstea sa, la fel ca mulți dintre prietenii săi.

Mihai a publicat numeroase lucrări de-a lungul carierei sale, dar primele le-a publicat în GInfo. Când am decis să încercăm să facem o nouă revistă, ne-am propus să "reciclăm" unele dintre vechile articole. Vom începe acum, cu unul dintre articolele lui Mihai. Și, mi se pare potrivit că acesta este primul articol de algoritmică publicat în noua Gazetă de Informatică.

Acest articol se referă pe scurt la două probleme propuse de autor la Olimpiada Naţională de Informatică 2002. Enunţurile acestor probleme au fost publicate în numărul 12/5 (mai 2002) al GInfo. Articolul aduce elemente de noutate, prezentând câte o extindere și o nouă metodă de rezolvare pentru problemele Suma divizorilor și EQS.

Suma divizorilor

În [2] este exprimată opinia că rezolvarea problemei Suma divizorilor de la ediţia 2002 a Olimpiadei Naţionale de Informatică necesită unele elemente de matematică superioară. Luând în considerare rezolvarea publicată în [1] nu putem decât să fim de acord. Această rezolvare se baza pe existenţa inversului multiplicativ pentru orice număr nenul într-un corp de resturi modulo 9901 (care este un număr prim). Acest element de matematică ar trebui să fie accesibil elevilor de clasa a XII-a, însă nu și celor de clasa a XI-a (problema a fost propusă la clasele a XI-a și a XII-a).
Când a fost propusă această problemă, a fost luată în vedere și o soluţie accesibilă elevilor de clasa a XI-a, care, pe lângă accesibilitate, mai are meritul că nu folosește faptul că 9901 este număr prim (astfel, problema este generalizată pentru numere care sunt resturi modulo numere compuse).
Pentru a prezenta soluţia alternativă a acestei probleme, să ne reamintim că determinarea sumei divizorilor numărului A^B a fost redusă la calculul sumei unei progresii geometrice modulo 9901: S_n = (1 + q + q² + ... + qⁿ) mod 9901 (vezi [1]).
Această sumă se poate calcula eficient dacă observăm următoarea recurenţă (toate calculele se efectuează modulo 9901):
S_2k+1 = 1 + q + q² + ... + q^2k + q^2k+1 =
= 1 + q · (1 + q + q² + ... + q^2k) =
= 1 + q · S_2k
S_2k = 1 + q + q² + ... + q^k +q^k+1 + ... +q^2k =
= (1 + q + q² + ... + q^k) +q^k · (1 + q + q² + ... + q^k) =
= S_k +q^k · (S_k - 1).
Dacă folosim o metodă cu timp de execuţie logaritmic pentru a calcula valoarea q^k se observă că suma poate fi evaluată într-un timp cu ordinul de complexitate O(log² N). O astfel de metodă pentru calculul valorilor q^k este folosirea unei recurenţe similare cu cea de mai sus:
q^2k+1 = q · q^2k
q^2k = (q^k)².
Deși folosirea acestui algoritm cu ordinul de complexitate O(log² N) era suficientă pentru a obţine punctajul maxim la concurs, se observă că algoritmul poate fi îmbunătăţit pentru a rula într-un timp de ordinul O(log N) dacă îmbinăm cele două recurenţe și calculăm simultan qⁿ și S_n:
q^2k+1 = q · q^2k
S_2k+1 = 1 + q · S_2k
q^2k = (q^k)²
S_2k = S_k +q^k · (S_k - 1).
Înainte de a încheia discuţia problemei, dorim să combatem o obiecţie pe care am auzit-o referitor la problemă, și anume că unii concurenţi puteau să nu cunoască unele proprietăţi cum ar fi:
(A + B) mod C = ((A mod C) + (B mod C)) mod C.
Considerăm că o astfel de obiecţie este total nejustificată, având în vedere nivelul înalt de pregătire pe care ar trebui să îl aibă participanţii la faza naţională a olimpiadei. În primul rând, astfel de proprietăţi sunt intuitive și se folosesc încă din clasa a V-a când se calculează ultima cifră a rezultatului unor expresii. În al doilea rând, calculul cu resturi este destul de important în informatică (numere pseudoaleatoare, permutări, hashing etc.), astfel încât orice elev cu un interes deosebit pentru informatică (cum ar trebui să fie concurenţii de la ONI) să îl fi cunoscut și folosit.

EQS

Așa cum a fost propusă, problema EQS cere numărarea soluţiilor dintr-un anumit domeniu de forma [-A, +A] a unor ecuaţii de tipul:

a₁ · x³ + a₂ · y³ + a₃ · z³ + a₄ · u³ + a₅ · v³ = 0.

Pe scurt, soluţia consta în a trece două dintre necunoscute în membrul drept al ecuaţiei, schimbând semnul pentru coeficienţi. Se generau apoi toate valorile posibile pentru membrul cu două necunoscute și se sortau. În continuare, se generau toate valorile posibile pentru membrul cu trei necunoscute și se căutau logaritmic între valorile posibile ale celuilalt membru al ecuaţiei, folosind o căutare binară. Așadar, se foloseºte o cantitate de memorie de ordinul O(A²) (pentru tabloul sortat) și este necesar un timp de execuţie de ordinul O(A³ · log A) (factorul dominant este căutarea în tabloul sortat).

Propunem în continuare o extensie a acestei probleme pentru ecuaţii cu șase necunoscute de forma:

a₁ · x³ + a₂ · y³ + a₃ · z³ + a₄ · u³ + a₅ · v³ + a₆ · w³ = 0.

Menţionăm că această extensie s-a aflat în vederea comisiei de la ONI, dar nu a fost folosită în concurs, rezolvarea fiind considerată destul de dificilă.

Încercând să folosim soluţia de mai sus pentru această nouă problemă, ne lovim de imposibilitatea de a păstra în memorie toate valorile posibile ale unui membru cu trei necunoscute.

Numărul acestor valori poate atinge 100³ = 1.000.000; astfel, ar fi necesară o cantitate de memorie disponibilă de 4 MB, ceea ce nu a fost cazul la ONI 2002.

Intuim fără mare dificultate soluţia: dacă am putea să generăm toate valorile posibile ale unui membru cu trei necunoscute în ordine crescătoare, am putea interclasa pur și simplu listele de valori posibile pentru membrul stâng și membrul drept.

Algoritmul ar necesita un spaţiu de memorie constant și un timp de execuţie constant în plus faţă de codul de generare a valorilor.
Ca urmare, subproblema care trebuie rezolvată constă în generarea în ordine crescătoare a elementelor următoarei mulţimi:
S = {a · x³ + b · y³ + c · z³ | x, y, z ∈ [-A, A]}.
În primul rând se observă faptul că semnul coeficienţilor nu contează, deci putem lucra numai cu coeficienţi pozitivi.
Într-adevăr, următoarea egalitate este valabilă:
{a · x³ + b · y³ + c · z³ | x, y, z ∈ [-A, A]} = {|a| · x³ +|b| · y³ +|c| · z³ | x, y, z ∈ [-A, A]}.
Egalitatea acestor mulţimi se datorează faptului că, dacă este luat în considerare un triplet de forma (x, y, z), atunci vor fi luate în considerare toate tripletele de forma (±x, ±y, ±z).
În cazul în care coeficienţii sunt pozitivi, există o relaţie de ordine parţială foarte utilă între valorile mulţimii și anume:
z₁ < z₂ ⇒ a · x³ + b · y³ + c · z₁³ ≤ a · x³ + b · y³ + c · z₂³
Soluţia pe care o propunem se bazează pe această relaţie de ordine parţială. Vom păstra un tablou bidimensional t de dimensiuni 2 · A × 2 · A în care vom păstra, pentru fiecare pereche (x, y), cea mai mică valoare z pentru care tripletul (x, y, z) nu a fost încă luat în considerare. Versiunea în pseudocod a algoritmului este următoarea: