Probleme de formula

Cosmin Negruseri
27 aprilie 2008

Creearea unei probleme pentru un concurs de programare nu e o munca usoara. De aceea nu ma surprinde cand vad ca la un concurs apare printre probleme una de formula. Totusi nu imi place cand se da o asemenea problema. Un motiv ar fi lipsa de originalitate, e foarte probabil ca problema a fost luata din o carte de matematica. Alt motiv ar fi ca nu testeaza partea de programare la olimpiada de informatica, de obicei programele ce rezolva problemele astea sunt foarte simple implicand doar o instructiune de scriere si una de citire. Cateodata mai ai nevoie sa si implementezi numere mari dar cam atat. Al treilea motiv e ca nu departajeaza elevii intre ei dupa valoarea sau ideile lor, ci mai mult randomizeaza rezultatele, pentru ca unele formule sunt foarte greu de gasit pe cale matematica, dar sunt mai usor de ghicit.

Pentru a gasi formula ce ne rezolva problema, ne uitam la cateva rezultate mici si sa incercam sa ghicim cum arata formula ce le genereaza.

O metoda banala ar fi sa variem fiecare parametru de intrare si sa vedem cum se modifica numarul cautat.

In problema mea aladdin2 , se cere numarul de colorari ale celulelor unei table nxm cu alb sau negru, astfel ca orice patrat de 2×2 sa aiba exact doua patrate colorate alb si doua colorate negru. Formula e banala 2ⁿ + 2^m - 2 si se observa imediat cu variarea dimensiunilor.

In alta problema la un baraj se cerea determinarea numarului de arbori partiali ai unui graf bipartit complet cu n noduri in o partitie si m noduri in cealalta partitie. Credeti ca era greu sa va prindeti de formula n^n-1 * m^m-1 , fara a stii ca codul prufer sta in spatele solutiei?

Adi Carcu imi zicea prin 99 ca au inceput sa se dea cateva probleme la barajele de anul respectiv pentru care rezultatul era o combinare. La a doua astfel de problema, multi dintre concurenti au generat triunghiul lui pascal si au cautat rezultatele din exemplu acolo. Astfel ei au rezolvat o problema de dificultate medie in cateva minute.

Alta problema interesanta e determinarea numarului de permutari fara puncte fixe. Problema are o solutie draguta folosind programare dinamica, dar rezultatul e foarte apropiat de n!/e si astfel prin variarea dimensiunii intrarii poti sa rezolvi problema foarte repede.

Daca e un concurs online ne putem uita imediat pe Online encyclopedia of integer sequences Am folosit siteul asta pentru cateva probleme de la concursurile topcoder, si pentru o problema la Oni by Net.

Radu Stefan a folosit o metoda destul de misto pentru a rezolva urmatoarea problema:

Se cere sa se numere in cate moduri se pot aseza k regi pe tabla de sah de n x n astfel incat regii sa nu se atace.

Radu s-a gandit ca solutia va fi un polinom in doua variabile P(n, k), iar gradul polinomului nu va fi prea mare (parca el a presupus ca limita e 6). Astfel a generat folosind metoda backtracking solutiile pentru n <= 6 si k <= 6. A considerat coeficientii polinomului ca necunoscute si a rezolvat sistemul de ecuatii liniare date P(n, k) si valorile obtinute prin algoritmul backtracking. Astfel luat punctaj maxim pe problema respectiva.

Trucul asta se aplica usor pe alte probleme, trebuie doar sa stiti sa folositi metoda de rezolvare a sistemelor liniare.

Pentru polinoame intr-o singura variabila puteti sa folositi metoda diferentelor divizate care e foarte simpla de implementat.

Daca formula e ceva mai complicata decat un polinom, putem sa speram ca sirul solutiilor e caracterizat de o recurenta liniara, si astfel putem folosi din nou rezolvarea de sisteme de ecuatii lineare pentru a afla coeficientii recurentei.