Solutie Problema

In primul rand imi cer scuze pentru intarziere cu care scriu acest post (am fost prins cu diferite chestii nesemnificative cum ar fi sesiunea - care nu merge f bine btw).

Problema era asa:
Dandu-se o lista simplu inlatuita de lungime necunoscuta sa se gaseasca un algoritm care returneaza un element random din aceasta lista printr-o singura parcurgere. Problema se rezolva in felul urmator.

La pasul 1 alegem elementul de pe pozitia 1.
La pasul i alegem elementul de pe pozitia i cu o probabilitate de 1 / i.

Voi scrie algoritmul intr-un pseudocod pentru a fi mai clar.

ret = 0
pointer = baza listei
for (i = 1; pointer != null; i++, p = p->next) {
if (rand(i) == 0) {
ret = p->valoare;
}
}

Practic la fiecare pas inlocuiesc elementul returnat cu elementul aflat pe pozitia aceea cu o probabilitate de 1 / i, iar la sfarsit returnez elementul din ret.

De ce toate elementele au aceeasi probabilitate?

Demonstratia se face cu o inductie simpla.

pasul 1.
Lista are lungime 1, elementul returnat este chiar primul din lista -> evident.

pasul i.
Sa zicem ca am ajuns la elementul i si am ales deja un element din primele i-1 elemente cu probabilitatea 1 / (i - 1). Acum avem probabilitate (i - 1) / i ca elementul dinainte sa ramana si 1 / i ca acesta sa fie inlocuit.
Avand in vedere ca elementul de dinainte avea deja probabilitatea 1 / (i - 1) probabilitatea ca acesta sa fie continuare e (1 / (i - 1)) * ((i - 1) / i) = 1 / i.
Evident probabilitatea elementul ales sa fie cel din casuta i e 1 / i deci elementul ales va avea probabilitatea 1 / i.

Daca aveti nelamuriri puteti sa imi trimite-ti si sper sa va raspund cat de curand cu lamuriri :).

Problema a fost rezolvata de:
- Cosmin Gheorge
- Andrei Dragus
- Tudor Muresan & Cristi Urlea (au lucrat la comun)
- Dan Sanduleac

Am mai auzit o idee care mie nu mi se pare ok insa o sa postez aici argumentele mele impotriva ei.
La fiecare pas generam un numar random si la sfarsit alegem elementul cu cheia minima. In practica aceasta idee merge insa ce te faci in cazuri de egalitate? Cineva a zis ca in cazul in care ai egalitate intre 2 elemente dai cu banu pe care sa il iei (adica fifty - fifty chance) insa nu vad cum ai putea argumenta corectitudinea acestei solutii. Din aceasta cauza am respins aceasta solutie (oricum toti cei care au venit cu solutia asta au revenit ulterior cu solutia buna). Nestiind insa lungimea listei nu prea stii in ce interval sa generezi acele numere riscand astfel sa ai multe egalitati ceea ce ar duce la dubiosenii :D. Daca reuseste cineva sa demonstreze ca merge sa dai cu banul in caz de egalitate il invit sa posteze aici comment sau sa imi trimita un mail.

Problema

Am mai postat acum ceva vreme o problema care mi s-a parut interesanta, iar zilele trecute am mai dat peste una.

Se da o lista simplu inlatuita a carei lungime nu este cunoscuta. Se cere sa se construiasca o functie care sa returneze un numar random din aceasta lista si sa respecte urmatoarele conditii:
- nu se poate parcurge lista de mai multe ori
- fiecare element al listei trebuie sa aibe aceeasi probabilitate de a fi selectat.

O sa postez si solutia peste ceva vreme, pana atunci daca aveti solutii trimiteti-le la tiberiu.savin@gmail.com.

Pana acum problema a fost rezolvata de:
- Cosmin Gheorghe
- Andrei Dragus

Cum sa iti pui webcamul ca desktop

Dadeam mai devreme de-aiurea cu stumbleu (procrastination :-") si am dat peste o chestie care m-a amuzat si anume asta

Totusi de la chestia asta am inceput sa ma gandesc daca nu poti cumva sa iti pui webcamul sa inregistreze si sa iti puna streamul pe desktop.
Ei bine se poate (cel putin in ubuntu). Here is the proof:

Pentru cei care au ubuntu, rulati comanda asta:

xwinwrap -ni -o 0.40 -fs -s -sp -st -b -nf -- mplayer -wid WID -quiet -fps 15 tv://

(Parametrul -o reprezinta opacitatea)
Daca nu aveti xwinwrap instalat rulati comenzile astea inainte:

sudo apt-get install build-essential libx11-dev x11proto-xext-dev libxrender-dev libxext-dev cvs
cd xwinwrap
cvs -d :pserver:anoncvs@cvs.freedesktop.org:/cvs/xapps co xwinwrap
make
sudo cp xwinwrap /usr/bin

Solutie problema

Consider ca am lasat destul de mult timp de gandire la aceasta problema asa ca o sa ii postez solutia.
Solutia se bazeaza atat pe faptul ca cele 2 numere sunt consecutive cat si pe faptul ca ele sunt naturale. Astfel vom pleca de la cazul banal cand una din persoane are numarul 0. In cazul acesta el stie cu siguranta ca celalalt are numarul 1 si va iesi din camera la prima bataie a ceasului.
In cazul in care una din persoane are numarul 1 ea va rationa in felul urmator. Asteapta prima bataie a ceasului. Daca cealalta persoana nu a iesit din camera inseamna ca aceasta nu are numarul 0 deci va avea numarul 2 si va iesi din camera la a doua bataie a ceasului. Rationamentul este asemanator si pentru numere mai mari astfel ca daca o persoana are numarul k va iesi din camera la bataia cu numarul k+1.
Astept sa imi ziceti daca v-a placut :).

Problema interesanta

Am aflat aseara o problema de logica care mi-a placut si m-am gandit sa o zic si eu mai departe (mi-a zis-o colegu de camera). Here it goes:

Intr-o camera se afla 2 oameni si amandoi stiu cate un numar. Ei nu stiu numarul pe care il are cealalta persoana, insa amandoi stiu ca sunt numerele naturale consecutive. De fiecare data cand bate ceasul daca vreunul dintre ei stie cu siguranta care este numarul celuilalt, poate iesi din camera. Cei doi nu au voie sa vorbeasca sau sa comunice intre ei in orice fel (semne etc.). Sa se zica daca exista vreo strategie pe care cele doua persoane sa o urmeze astfel incat intr-un final unul dintre acestia sa ghiceasca numerele si care este aceasta.

Trimiteti solutiile la tiberiu.savin-at-gmail.com

Update:
Cei care au gasit solutia pana acum sunt:
- Alexandru Tandrau
- Andrei Olariu
- Stefan Istrate
- Stefan Filip
- Adrian Airinei
- Andrei Dragus
- Cosmin Gheorghe