E joi si am decis de mult ca voi continua a oferi saptamanal probleme de perspicacitate. Saptamana trecuta a fost o problema cu niste arcasi. Multumesc celor care s-au chinuit s-o rezolve. Cei care au solutionat corect problema arcasilor sunt Alex (Seviyor), Laura (Lieserl) si Adrian (no website). Pentru ca fondurile ne sunt limitate, premiul va fi oferit astfel: la 3 raspunsuri corecte se ofera o bere/suc celui care a raspuns. In rest, nu va putem oferi decat recunoastere publica a faptului ca ati rezolvat probleme mai interesante.
Problema de saptamana aceasta e mai simpla intr-un fel. In primul rand, nu mai exista probabilitati. De asemenea, voi publica direct cerinta: “Sa zicem ca exista un colectiv de N persoane si exista E evenimente care trebuiesc programate. Traind intr-o societate democratica, fiecare persoana primeste cate un biletel in care va scrie ordinea in care ar dori ca acele evenimente sa fie programate. Apoi, cel care a impartit biletelele face un tabel in care pe linii pune evenimentele si pe coloane ordinea. Astfel, elementul de pe linia i, coloana j in tabel v reprezenta numarul celor care au votat ca evenimentul i sa fie al j-lea programat. Se cere o strategie optima de analiza a acestui tabel astfel incat evenimentele sa fie programate conform dorintei majoritatii. Se cere demonstratia faptului ca strategia aleasa este buna si ca contabilizarea optiunilor sub forma acestui tabel duce tot timpul la o solutie. NU se cere o alta modalitate de contabilizare a optiunilor dar daca exista o puteti prezenta, demonstrand si faptul ca duce la raspunsul corect.” Termen limita: joia viitoare.
Prima sesiune şi sunt probleme la planificarea examenelor… am înţeles. Cea mai bună soluţie e să modifici opţiunile celorlalţi. Să îi convingi că programarea e uşoară şi merge pusă ultima, USO primul, că aşa vror profii (e şi mai bine aşa, nu veţi mai fi tentaţi de calculator după sub pretextul că învăţaţi la Linux); din celelalte 3… depinde de profi, mie Algebra îmi pare mai uşoară şi merge pusă deci penultima, apoi.. la fizică se folosesc unele rezultate matematice, deci cea mai bună soluţie ar fi USO – Analiză – Fizică – Algebră – PC.
Îmi pare bună soluţia mea, dar bănuiesc că tu vroiai o generalizare… o să mă mai gîndesc. Dar trebuie să specifici mai bine ce se cere (cum adică dorinţei majorităţii? e interpretabil, şi neinteligibil
)
Ai avut dreptate cumva. Problema a fost generata saptamana trecuta cand s-a votat ordinea in care dam examenele. Am rezolvat problema si vroiam sa aflu daca exista o varianta mai simpla.
Dorinta majoritatii inseamna ca sa fie cat mai multi oameni satisfacuti de decizia finala. Stiu ca nu te lamureste mai mult decat prima varianta dar nu am cum sa explic mai bine fara a oferi direct solutia gasita de mine.
Si nu voi modifica niciodata parerea celorlalti chiar daca nu-mi va conveni. Doar daca…
Eu ma gandeam cam asa: din tot tabelul alegem casuta cu numarul cel mai mare de cereri (adica ce examen a fost votat de cei mai multi oameni sa fie pe pozitia j). Sa zicem ca aceasta casuta are coordonatele l0 (linia) is c0 (coloana). Stabilim examenul [l0,c0] sa fie programat atunci.
Din matrice calculam apoi urmatorul numar cel mai mare de cereri, eliminand coloana c0 (pentru ca al c0-lea examen a fost deja programat) si eliminand si linia l0 (pentru ca examenul l0 a fost programat sa fie al c0-lea) si obtinem iar 2 coordonate care reprezinta iar un examen de programat. Repetam chestia asta pana ramanem fara examene, adica pana cand au fost toate stabilite.
seviyor: Uneori sa gasesti cerinta e cel mai greu lucru
Noi nu stiam decat ca trebuie sa facem grupa cat mai fericita 
.. Nu stiam, pe moment, ce inseamna asta – daca trebuie ca ordinea sa coincida cu cat mai multe biletele, sau daca un examen care apare cel mai des pe o pozitie in toate biletelele sa ocupe acel loc etc. Uneori se bat cap in cap. De exemplu, un examen care e ales cel mai frecvent pe pozitia 2 va fi intuitiv programat al doilea. Problema e ca se poate intampla ca aceasta decizie sa duca la rezultate nedorite pentru celelalte E-1 examene. Sa zicem ca, ipotetic, ai putea face compromis de la o optiune care apare cu frecventa foarte mare pentru a nu induce astfel diferente mari pentru celelalte E-1 examene. Poate ca, cine stie, daca nu il sacrificai pe ala frecvent restul – toate cele E-1 ii nemultumeau pe foarte multi dintre votanti. Uf, greu mai e in scris 
Lavinia: Daca ai egalitate? Eliminand un maxim cu tot cu c0 si l0 renunti la date importante din matricea ta, inducand erori mari pentru deciziile urmatoare? Intreb doar
Cel mai bun sfat e sa aplicati problema in realitate. Veti avea o mare surpriza
, cel putin noi am avut. Mihai, tine-ma sa nu zic 
Hmm. Daca ai egalitate, sa zicem ca [lx,cx] e egal cu [ly,cy] atunci propun: daca [lx,cy]>[ly,cx] atunci alegem ca maxim pe [ly,cx], pentru ca sunt mai multi care si-ar fi dorit ca primul examen sa fie al cx-lea decat celalalt sa fie al cy-lea. Nu spun ca e solutia ideala, dar… e o solutie, nu?
E o solutie dar nu prea respecta cerinta. Incearca sa rulezi cateva simulari…
De data asta chiar am o posibilă soluţie: pentru fiecare coloană păstrăm un indice de genul “Număr nemulţumiţi” nn, definit ca diferenţa dintre suma elementelor de pe acea coloană şi maximul dintre acele elemente. Cu alte cuvinte, nn reprezintă… numărul de nemulţumiţi dacă, pentru acea coloană se alege evenimentul cel mai dorit. Alegem apoi coloana cu nn maxim, şi de pe acea coloană alegem linia elementului maxim din ea. Recalculăm indicii nn, şi reluăm procedeul.
Acest algoritm nu va furniza întotdeauna soluţia cea mai bună, dar una f apropiată. Îmbunătăţire se pot aduce luînd în calcul şi cel de-al doilea maxim pe fiecare coloană, alţi indici, altă bătaie de cap.
Poate nu e NP, dar în mod sigur se poate folosi backtrackingul (tot ce am avea nevoie de ar fi o funcţie care să calculeze costul unei configuraţii).
Lavinia: e posibil sa ai acelasi nr de voturi pt ca evenimentele ‘x’ si ‘y’ sa file plasate pe pozitia ‘k’, adica ‘cx=cy’ si nu mai merge.
deci io sunt de acord cu primul post al laviniei, numa atunci cand ne dau valori egale, calculam media artimetica a patratelor valorilor de pe celelalte pozitii pt ‘lx’ si vedem care e cea mai mica (teoretic sunt cazuri in care sa ne dea valori egale si atunci da probabilitatea e f mica). cand gasim cea mai mica medie, eliminam linia si coloana cum a indicat si lavinia
Vom avea o matrice patratica. (a[i][j])
Suma elementelor de pe fiecare coloana este constanta si este egala cu numarul N. (pentru ca fiecare persoana poate pune o singura materie pe pozitia 1, 2, 3 etc.)
Suma elementelor de pe fiecare linie este constanta si este egala cu numarul N. (pentru ca fiecare persoana pune o singura data o materie)
Luam un vector (v[i]) cu E elemente. Pentru fiecare materie aflata pe linia i din matricea a[i][j] vom retine in v[i] pozitia j in care linia a[i] ia valoarea maxima.
Cautam elementele din vectorul v[i] care nu se repeta. Este clar ca acestea reprezinta decizia majoritatii, iar evenimentul de pe linia i va fi programat ca fiind al v[i]-lea.
Eliminam din matrice linile deja stabilite si coloanele deja stabilite. In noua matrice cautam elementul a[i][j] (elementele s-au eliminat prin punerea valorii 0 pe linile si coloanele respective) maxim. Daca se afla o singura data in matrice, atunci se va programa si acest eveniment pe pozitia j si se va elimina linia i si j (punandu-se valoarea 0); Daca se afla de 2 ori (sau de mai multe ori), pentru acele evenimente i se va vedea care este urmatorul numar maxim de pe fiecare linie. Se va face diferenta intre cele doua pentru fiecare linie, si unde valoarea este mai mica acela va fi evenimentul i cu numarul de ordine j. Se elimina si aceasta linie si coloana si procedeul se repeta, incepandu-se din nou cautarea numarului maxim din tabela. Si tot asa pana tabela ramane vida (numai cu elemente 0) si toate evenimentele vor fi programate in mod optim.
Sper ca m-am facut inteleasa, pot da si lamuriri suplimentare daca este cazul. Nu ma intrebati de ce o consider ca fiind cea mai buna metoda, este doar o intuitie a mea. Specific ca nu am luat pe foaie niciun exemplu concret (desi as fi putut), dar imi este prea multa lene si somn la ora asta (deja).
Salut, frumoasa treaba cu problemele.
Nu stiu cat de mault ma duce capul dar am sa incerc sa dau si eu un raspuns problemei tale.Sper sa te multumeasca.
E cat se poate de evident ca tabelul e o matrice patratica de E dimensiuni iar suma elementelor de pe o coloana e egala cu suma elementelor de pe o linie (oricum ar fi ele alese) dar asta conteaza doar ca sa vezi daca nu cumva persoanele ce au completat biletele nu te-au inselat (ca ce dracu doar suntem in tar tuturor posibilitatilor). Iei prima coloana si cauti numarul maxim de voturi; linia care va avea numarul maxim de voturi pe prima coloanava fi primul eveniment ce se va produce. Daca vrei sa fim matematici punem acest prim eveniment intr-o matrice coloana unde ordinea coloanelor va reprezenta ordinea de proucere a evenimentelor (sa- i zicem Matricea Viitorului Dorit). Punem, va sa zica, evenimentul in nostru pe prima linie a MVD, dupa acea taiem coloana unu a matrici initiale si linia evenimentului, obtinem o matrice de ordinul E-1 si analog ca la prima fazapentru urmatoarele lini si cololane pana n-o sa mai avem matrice de studiat. In caz de egalitate la o coloana din maticea initiala pentru doua sau mai multe evenimente cred ca cel mai echitabil lucru e sa revenim la matricea din care a fost iterata matricea actuala si vom cauta care dintre evenimente s-a dorit a se intampla mai devreme de mai multe persoane.Daca si aici avem egalitate pentru un anumit numar de evenimente din cele deja avute in calcul vom merge la metricea superioara si tot asa pana ce un eveniment va iesi invingator.Dar daca se ajunge la matricea mama si nu e o situatie clara mergem in sens invers de la matricea origine(nu initiala, ci origine pentru discutiea cazului de egalitate) si cautam evenimentul dintre cele analizate ca egalitati ce se doreste a se intampla de mai multe persoane dar cu o pozitie in timp mai tarziu,si daca avem si aici egalitate tot asa pana ce un eveniment devine cstigator; dar dac nu avem nici acu un eveniment castigator i pui sa laeaga pur si simplu ce doresc dintre evenimente sa se produca pe acea pozitie.
Totusi cred ca acest mod de abordare e gresit. Putem avea persoane ce nu li se va intampla nici un eveniment in ordinea propusa de ele si ce faci atunci. Nu poti sa sacrifici mai pe nimeni doar de dragul democratiei. Dupa cum a spus colegul tau la inceput cel mai bun liucru de rezolvare a chestiuni in cauza o reprezinta compromisuri din partea tuturor. Matematica va esua lamentabil, dar poate deveni un instrument de convingere ca asa e mai bine pentru toti si eventual de a face si unele schimbari pentru a multumi macar partial.
Totusi inca nu mi-ai rezolvat problema. Ai timp o viata intraga; dar ca sa fiu sincer nici nu cred ca te intereseaza rezolvarea. Si daca nu te interseaza cu atat mai bine
Referitor la ceea ce am scris mai sus, vreau sa corectez ceva. Evident ca acolo unde am scris despre niste diferente nu am vrut sa scriu ca diferenta trebuie sa fie minima, ci maxima …
(asta in gandirea de aseara)
Gandind acum problema…
Consideram linia i si calculam urmatoarea suma
for j=1 to E
S[i]+=a[i][j]*j
ordonam crescator dupa s[i] si cam asta ar fi… cred
sfat: incercati fara backtracking:d
Lothlorien: Inca n-am destule indicii pentru a rezolva aceasta problema cu un singur raspuns…
Pai da, ca backtracking-ul nu e prea eficient. D-aia am si propus solutia 2
. Exemplu pe foaie tot nu am luat deoarece pentru a obtine ceva elocvent numarul N ar trebui sa fie destul de mare. 
Hmm.. eu nu mă gîndisem că toate coloanele au aceaşi sumă. Iniţial, este adevărat, dar ulterior dacă algoritmul lucrează pe principiul eliminăm linia cutare… se mai schimbă treaba.
Tot nu am găsit soluţia.
Pai eu as construi un graf bipartit, prima multime optiunile, a doua numerele de ordine. Le-as uni fiecare cu fiecare, si as atasa muchiilor ponderi. In felul asta reduc problema la una de cuplaj maximal(flux maximal), care este evident, mai eficienta decat backtracking.
Se poate si mai simplu…
hmmm….dak as fii un copil genial de clasa a patra…cum as face chestia asta fara backtracking sau graf bipartit?…
Indiciile le ai cu siguranta, sau cel putin poti sa ti le construiesti. Si in legatura cu problema, m-am tot gandit si cred ca e un exemplu clasic si elocvent de principiul nedeterminarii, in sensul ca nu exista o solutie convenabila pentru toti oricat ai incerca iar o solutie ACCEPTABILA pentru majoritatea nu e unica, exemplul find solutile de mai sus. Toate au aplicabilitate foarte buna si egala chiar pentru o masa de oameni. Acum nu ca as bate campul dar propun sa te gandesti la un lucru: la ce numar de oameni poti aplica o lege matematica standard chioar si cele ale matematici probabilistice?
Cred ca problema asta e destul de spinoasa, mai ales daca doresti ca majoeitatea sa fie sadisfacuta si ceilalti (fii atent la sensul cuvintelor) in mare parte sa accepte. Uite ce cred ca pentru un grup de pana in 10 persoane poate esua cu brio modelul ales, in schimd e aplicabil si ceu rezulatate foarte , foarte bune cred ca pentru grupuri de la 10 pana la 100 de persoane, dar pentru valori mai mari intra in discutie si factorul de omogenitate al gandirii persoanelor, cum ar fi sa aplici modelul tau la 2500 de oameni? Ce faci dac vei avea sa spunem 100 de nemultumiti aproape total? daca vrei o utem discuta la nesfarsit, intra foarte multe variabile cu cat cres nr de persoane.
Dar ti-ai pus in vedere si numarul de evenimente ce trebuie sa fie votate? Oare nu exista un nr optim de evenimente ce trebuie date pentru ca modelul sa fie cat mai aplicabil(normal ca optimul depinde si de numarul de persoane); dar importanta evenimentelor pentru fiecare persoana;c? Crezi ca poate fi cuantificata????
Da am filozofat mai mult decat era cazul dar de acum inainte cred ca filozofia acestor lucruri tre sa isi faca loc cat mai mult si in informatica mai ales pentru cea ce doresti tu sa faci; gandestete daca nu le convine oamenilor ce fac poti apela la alternativa de a-i convinge ca asa e mai bine caci cica mai au si ratiune; dar cu atomi ce faci daca uni nu sunt multumiti si tu ai nevoie si de ei cum ii convingi? e ceva de abordat la asta nu?
De fapt tu incerci prin aceasta problema sa aplici teoria haosului, si e frumos pusa, mai ales ca ai si ajutor neconditionat din partea celor de pe net. Foarte inteligent, si sa sti ca din partea mea (atat cat ma duce capul ) am sa incerc sa dau si eu niste soluti poate poti sa alegi ceva bun din ele.
Da am uitat un fapt. Daca tot nu e aplicabila la un numar foarte mare de persoane metoda oare nu e mai usor sa faci sa spunem alegera “manual”?? Oricum tre sa completezi datele din tabelul tau in compilator ,nu!? si in timp ce faci asta oare nu e la fel de usor sa aplici acea metoda a mea dar pe hartie taind linile cu un creion (mai ales daca nu sunt foarte multe evenumente???
Si acu vorbind din punctul de vedere al factorului uman (ce pe mine unul ma cam omoara, si cu el te stresez si pe tine fara nici o vina din patrea-ti) nu crezi ca facand tu calculul nu ai putea amplasa anumite evenimente mult mai corect daca cumva ai egalitate si nu numai?
Chiar inca o mide ,care nu stiu cat de alicabila poate fi dar la cat e de ciudata poate aplicabila,(ma intelegi tu) daca in algoritmul tau ai introduce un factor “aleatoriu conditionat de a gandi” ce sa simuleze un fel de creir omenesc ce ia anumite deciozi dupa unele aspecte generale sa le sounem.
poate din doua incertitudini reiese o incerttuydine mai mica??????
Gata te las ca ti-am scris nu povesti ci basme in adevaratul sens al cuvantului. mai vb
OK, analyze this:
Primul: Ordinea evenimentelor: A, B, C
Al doilea: Ordinea evenimentelor: B, C, A
Al treilea: Ordinea evenimentelor: C, A, B
Scoate tu algoritmul optim ca sa le pui pe astea in ordine.
Mai discutam despre asta… Curand.
Mai vezi ce zice si Domnu Sageata.
care sageata?
Nea Sageata. Kenny.