Rezolvari pentru Etapa 4

Problema 1: Comunicare
Problema 2: Frumoasa viata de student


Problema 1: Comunicare

Putini concurenti au trimis solutii la aceasta problema, dar dintre acestia, majoritatea pot fi citati la capitolul solutii foarte interesante.
Majoritatea concurentilor si-au comentat amanuntit codul. In esenta, algoritmul aplicat este de aglutinare: fiecare bloc de date este trimis spre destinatia sa pe cel mai scurt drum. In cazul unui conflict de legaturi, are prioritate pachetul cu destinatia cea mai indepartata (care se grabeste cel mai tare :).

Observatie:

Orice bloc de date are maxim doua directii convenabile de miscare. Deoarece au persistat confuziile referitoare la calcularea dimensiunii firelor de asteptare (unii au calculat dimensiunea firelor de asteptare pe parcursul transmiterii blocurilor, altii inainte de transmiterea acestora), la corectare am facut abstractie de aceasta cerinta.

Teste

Solutia nr. 1 (Pascal)
Solutia nr. 2 (C)


Problema 2: Frumoasa viata de student

Permiteti-mi sa fac o observatie elementara in privinta programarii dinamice.
Presupun ca toata lumea stie ce este distanta Lowenstein. In principiu, distanta Lowenstein intre doua siruri este cu atat mai mare cu cat cele doua siruri sunt mai diferite. Aceste siruri pot fi simple siruri de litere sau pot fi siruri de entitati in sensul mai general al cuvantului. Un bun exemplu de entitati sunt token-ii folositi de limbajele Pascal si C - identificatori, cuvinte cheie, nume de variabila, constante numerice etc.
Putem de pilda sa asociem fiecarui token dintr-un fisier Pascal un cod unic. Daca notam WHILE cu 201, DO cu 202, intregii cu 203, identificatorii cu 204 si restul simbolurilor (cum ar fi ;, =, :, ', etc) cu codul lor ASCII, atunci linia "while X<10 do Inc(X);" s-ar codifica astfel:
while  X      <     10    do    Inc   (     X     )     ;
201    204    060   203   202   204   040   204   041   059
Daca mergem mai departe pe acest drum si cream o tabela de simboluri a identificatorilor, vom putea atasa fiecarui nou identificator un cod unic. Adica, in locul fiecarui X se va pune 204, in locul fiecarui Inc se va pune 205 s.a.m.d. In felul acesta vom obtine un sir de numere atasat unui fisier Pascal.
Acum, ce-ar fi sa luam doua fisiere Pascal, sa le codificam pe fiecare si sa calculam distanta Lowenstein intre cele doua siruri obtinute? Desigur, vom putea raporta aceasta distanta la lungimea fisierelor pentru a obtine o distanta relativa cuprinsa intre 0 si 1. Ei, si daca aceasta distanta relativa este ingrijorator de aproape de 0, putem fi aproape siguri ca cele doua surse au o origine comuna. De acest lucru ne putem convinge usor aruncandu-ne o privire peste fisierele originale. Iata deci o metoda foarte comoda de a detecta - cu anumite scapari, desigur - tentativele de plagiat, fara a fi necesara compararea cu ochiul liber a celor doua fisiere suspecte.
De remarcat ca metoda de mai sus este imuna la copierea unui program si schimbarea numelor variabilelor, datorita crearii unei tabele de simboluri. De asemenea, este imuna la schimbarea alinierii, intrucat ea ignora separatorii (blank, tab, <CR>, <LF> etc). Multe multumiri fratelui meu Cristi pentru aceasta idee simpatica.


Iata cum se facea problema E4P2 (ma refer la metodele mai originale decat da-mi si mie rezolvarea ta ca altfel iti sterg contul si asa mai departe):

Sa cream o matrice A cu N linii numerotate de la 1 la N si 10*N+1 coloane numerotate de la 0 la 10*N, in care A[i,j] reprezinta numarul minim de ore necesare pentru a obtine j puncte la primele i examene. Dar cum se pot obtine j puncte ?
La al i-lea examen, studentul nu poate lua decat o nota k cuprinsa intre 0 si 10; prin urmare, la primele i-1 examene elevul trebuie sa ia un numar de j-k puncte cuprins intre j-10 si j (bineinteles cu restrictia j-k>=0). In aceste conditii, timpul folosit este A[i-1, j-k] pentru primele i-1 examene si inca H[i,k] pentru al i-lea examen.

Fiindca interesul este ca, in conditiile in care obtinem acelasi numar j de puncte, sa minimizam timpul A[i,j] folosit (ca sa avem mai mult timp ramas pentru celelalte N-i examene...), vom spune ca:
      A[i,j] = min { A[i-1, j-k] + H[i,k] | 0<=k<=10, k<=j }
Deci pentru determinarea elementelor liniei i a matricei A avem nevoie de elementele liniei i-1. Asta inseamna ca matricea A se completeaza pe linie (ca tabelu' lu' Mendeleev). Deoarece pentru orice examen i avem nevoie de maxim 65535 ore, rezulta ca pentru media 10 ne vor trebui cel mult 6.553.500 ore, acesta fiind elementul maxim care poate aparea in matricea A. Necesarul de memorie pentru matricea A este de maxim 100 (linii) * 1000(coloane) * 4 (longint) = 400.000 octeti.
O data ce am completat matricea, trebuie sa aflam
  1. media maxima si
  2. numarul de ore alocate fiecarui examen.
Cu media e simplu: trebuie cautat elementul A[N, jmax] de valoare maxima, dar mai mic sau egal cu T. Cu alte cuvinte vreau sa obtin cat mai multe puncte la primele N examene (adica la toate), dar sa ma incadrez in timp. Daca am gasit elementul A[N, jmax], media este (imax/N).
Pentru reconstituire facem astfel: Stim ca la primele N examene am obtinut jmax puncte. Cautam acel numar k pentru care
      A[N-1, jmax-k] + H[N,k] = A[N, jmax]
ceea ce inseamna ca la al N-lea examen am luat nota k. Procedam la fel pentru a afla si notele la examenele N-1, N-2, ..., 1.

Calculul complexitatii:

Pentru a completa un element al matricii A se efectueaza 11 calcule (pentru 0<=k<=10). Matricea A are 10*N2 + N elemente, deci timpul total de calcul este cam 100 O(N2). Pentru N=100, rezulta 1.000.000 de operatii elementare. Calculul mediei si aflarea numerelor de ore pentru fiecare examen se fac in O(N).

Observatie:

Se mai putea aplica si o programare dinamica de tipul rucsac absolut clasic, la modul: se construieste un vector A[t], unde A[t] este numarul maxim de puncte pe care il pot obtine in timpul T. Aceasta rezolvare are complexitatea O(10*N*T), adica de ordinul miliardelor (te uiti si castigi). In afara de aceasta, necesarul de memorie este foarte mare (un vector cu T elemente numere intregi).

Cam asta e... Sarbatori fericite si-un curcan mare tuturor !

P.S. - Concursurile sunt singura situatie in care ni se cere sa fim egoisti si sa nu dam nimanui roadele muncii noastre. De ce tocmai acum pe unii dintre voi ii apuca filantropia ? :)

Teste

Solutia nr. 1 (Pascal)
Solutia nr. 2 (C)


[Enunturile] [Prima etapa] [Etapa anterioara] [Etapa urmatoare] [Ultima etapa] [English] [Inapoi!]

Inapoi!