Voi reformula problema in termeni de grafuri pentru a usura intelegerea explicatiei:

Se da un graf complet cu 6 noduri in care fiecare muchie este colorata sau in rosu, sau in albastru. Spunem ca un triplet de noduri (a, b, c) este monocromatic daca muchiile (a, b), (b, c) si (a, c) au acceasi culoare. Se cere sa se demonstreze ca exista cel putin 2 triplete monocromatice.

Solutia mea este urmatoarea: Numarul total de triplete este egal cu 20. Voi incerca sa demonstrez ca pot fi maxim 18 triplete care nu sunt monocromatice. Pentru a numara cate astfel de triplete sunt, putem sa folosim jmenul de la problema Color. Pentru fiecare nod vom inmulti numarul de muchii albastre incidente cu numarul de muchii rosii incidente. Adunand aceste valori si impartind la 2, obtinem numarul de triplete nemonocromatice. Va voi lasa pe voi sa demonstrati aceasta afirmatie :P. Numarul maxim de triplete nemonocromatice se obtine atunci cand pentru fiecare nod in parte produsul dintre numarul de muchii albastre si rosii este cat mai mare. Cum gradul unui nod este egal cu 5, rezulta ca produsul poate fi maxim 6. Deci, numarul maxim de triplete ce nu sunt monocromatice este 6 * 6 / 2 = 18.

Rezolvarea poate fi generalizata pentru grafuri mari.

Solutii corecte constructive au fost oferite de: Alex Mosoi, Andrei Dragus, Daniel Anghel.

Recent am aflat urmatoarea problema draguta de la •Cosmin Negruseri:

Sa se demonstreze ca intr-un grup de 6 persoane, exista cel putin un subgrup de 3 persoane in care toti membri subgrupului se cunosc intre ei sau niciun membru nu ii cunoaste pe ceilalti doi.

Eu va propun urmatoarea varianta modificata:

Sa se demonstreze ca intr-un grup de 6 persoane, exista cel putin doua subgrupuri de 3 persoane in care toti membri subgrupului se cunosc intre ei sau niciun membru nu ii cunoaste pe ceilalti doi.

Astept solutiile voastre la adresa andrei.grigorean at gmail.com

Cum numarul de rezolvari atat bune cat si rele a fost mare la problema anterioara, va mai zic o problema cu statistici de ordine pe care am auzit-o de la Mihai Patrascu.

Se dau n numere intregi scrise pe disc. Se cere sa se detemine mediana lor in timp O(n), citind fiecare numar de pe disc de O(1) ori si folosind O(sqrt(n)) memorie totala. Mediana unui sir de numere cu n elemente e elementul de pe pozitia n/2 din sirul rezultat in urma sortarii sirului initial.

Ca de obicei imi puteti trimite solutii pe adresa cosminn at gmail.com

Am gasit problema in cartea "Introduction to Algorithms: A Creative Approach" de Udi Manber. Udi e VP of engineering la Google si daca stiti de suffix arrays, el a publicat o metoda eficienta pentru a determina LCP (longest common prefix) a doua sufixe. Cartea imi place mai mult decat Cormen-ul pentru ca partea de teorie e orientata mai mult spre intelegerea lucrurilor decat spre demonstratii matematice stufoase si pe langa asta fiecare capitol are foarte multe probleme interesante la sfarsit. Eu cred ca problemele sunt esentiale cand inveti un subiect tehnic, pentru ca intelegi bine ideile din un domeniu cand esti obligat sa le aplici in contexte diverse.

Pana sa vad cerinta din cartea respectiva credeam ca problema selectiei celor mai mici k numere din un stream se poate face doar in O(n log k) daca esti obligat sa folosesti O(k) memorie, dar citind-o mi-am dat seama ca nu e greu sa scoti o solutie in O(n) timp si O(k) spatiu. E o diferenta mare intre a sti ca o problema e rezolvabila sau nu :), de aceea munca de cercetare e foarte dura.

Cei ce au rezolvat corect problema sunt urmatorii: Stefan Istrate, Andrei Marius Teodorescu, Adrian Vladu, Marius Pungaru, Marius Buzea, Daniel Pasaila si Alexandru Mosoi.

Va dau si solutia:
Pastram un sir A in care avem cele mai mici k numere din stream pana la momentul curent. Apoi la fiecare pas citim k noi elemente din stream in sirul B. Acum in sirul C punem elementele din ambele siruri si aplicam algoritmul de gasire a medianei care are complexitate O(k), vom pastra in A elementele din C mai mici sau egale cu mediana. Astfel obtinem un algoritm de complexitate O(n) timp si O(k) spatiu.

Daca tot am inceput sa scriu, am o problema draguta ce s-ar potrivi la un interviu tehnic:

Se da un stream de n numere intregi. Sa se gaseasca un algoritm ce determina cele mai mici k numere din acest stream in timp O(n) si memorie O(k). Streamul are urmatoarele doua metode int getNext() si bool hasNext().

Ca de obicei, puteti trimite solutiile pe adresa cosminn at gmail.com

Nu am mai scris de mult si v-am ramas dator cu solutia problemei Monede, daca ati uitat cerinta, puteti citi enuntul:

Pe o masa dreptunghiulara punem monede de raza 1 pana cand nu mai putem adauga o noua moneda fara ca ea sa se suprapuna cu altele. Unele monede pot fi partial inafara mesei. Daca numarul total de monede este n, sa se demonstreze ca toata suprafata mesei poate fi acoperita de 4n monede de raza unu care se pot suprapune.

Daca inlocuim cele n monede de raza unu cu monede centrate la fel dar care au raza doi, ele vor acoperi total masa, pentru ca in configuratia initiala, orice punct neacoperit era la o distanta mai mica decat unu de o moneda (in caz contrar am fi putut plasa inca o moneda de raza unu centrata in punctul respectiv).
Asta inseamna ca, cu n monede de raza unu putem acoperi un dreptunghi cu aria un sfert din aria mesei. Cu patru astfel de dreptunghiuri acoperite, putem obtine o configuratie a 4n monede ce acopera intreaga masa.

Singurul rezolvitor a fost Andrei Dragus, felicitari.

Pe o masa dreptunghiulara punem monede de raza 1 pana cand nu mai putem adauga o noua moneda fara ca ea sa se suprapuna cu altele. Unele monede pot fi partial inafara mesei. Daca numarul total de monede este n, sa se demonstreze ca toata suprafata mesei poate fi acoperita de 4n monede de raza unu care se pot suprapune.

Ca de obicei puteti trimite solutiile la adresa cosminn at gmail.com

Problema curenta a fost rezolvata de Alexandru Mosoi, Marius Andrei, Igor Naverniouk, Delia David si Dumitru Daniliuc.

Problema cerea sa se demonstreze ca, dandu-se doi cartofi, exista o curba inchisa in trei dimensiuni care se poate desena pe suprafetele ambilor cartofi.

Aceasta e una dintre problemele care par foarte grele la prima vedere si apoi daca auzi sau te prinzi de solutie pare foarte simpla.

Ne imaginam "fantomele" cartofilor. Le intersectam. O curba de intersectie a celor doua corpuri ne va da o curba ce poate fi desenata pe suprafete ambilor cartofi.

Problema curenta a fost rezolvat de Ovidiu Gheorghioiu, Delia David, Andrei Olariu si de Radu Grigore.

Nu exista nici o modalitate prin care sa obtinem rezultate uniform aleatoare folosind un numar finit de aruncari pentru ca se poate intampla ca la orice aruncare a monedei sa obtinem cap la infinit si atunci nu avem cum sa obtinem rezultate diferite.

Solutiile lui Andrei:

1. Se arunca moneda de cate 2 ori. Daca pica pajura si apoi cap -> pajura, daca avem cap si apoi pajura -> cap, daca avem 2 rezultate egale, repetam ambele aruncari.

2. Generam doua numere din multimea {0, 1} folosind metoda de la pct 1. Obtinem 00 -> mar, 01 -> para, 10 -> portocala, 11 -> repetam cele 2 generari.

Prima problema are mai mult de 50 de ani fiind rezolvata de unul dintre pionierii informaticii, John Von Neumann

A doua e interesanta in contextul generatoarelor de numere aleatoare. De exemplu in C++ unii folosim, pentru a genera numere aleatoare de la 0 la n - 1, instructiunile rand() % n. Acum dupa ce ati vazut problema 2 este clar ca unele rezultate sunt mai probabile ca altele.

In java sau Python generatoarele aleatoare sunt mai bune.

Varianta implementata in java:

public int nextInt(int n) {
     if ((n & -n) == n)  // i.e., n is a power of 2
         return (int)((n * (long)next(31)) >> 31);

     int bits, val;
     do {
         bits = next(31);
         val = bits % n;
     } while(bits - val + (n-1) < 0);
     return val;
 }

puteti citi aici explicatia codului.

O varianta care foloseste ceva mai multe dintre rezultatele aruncarilor pentru prima problema ar fi sa consideram si rezultatele de genul cap, cap, pajura, pajura ca 0 si pajura, pajura, cap, cap ca 1 si asa mai departe.

Ovidiu sugera urmatoarea generalizare pentru problema 2: Care e numarul mediu maxim de numere aleatoare intre 0 si k - 1 pe care le putem obtine dintr-un stream de biti uniform aleatori.

De data asta va dau doua probleme interesante de probabilitati, sunt relativ clasice, deci nu va suparati daca le-ati mai vazut inainte. Va amintesc ca imi puteti trimite solutii la cosminn at gmail.com.

1. Se da o moneda ce nu e ideala, adica nu cade cap sau pajura cu probabilitatea 0.5 ci cu o probabilitate p respectiv 1-p. Nu stim cat e valoarea lui p. Exita o metoda de a genera valori 0 sau 1 cu probabilitati egale?

2. Presupunem ca am gasit o modalitate de a obtine valori 0 sau 1 cu probabilitati egale. Exista acum o modalitate de a alege cu aceiasi probabilitate unul dintre fructele mar, para sau portocala, folosind metoda de generare a numerelor 0 sau 1?