**Allow me to make an elementary reflection on dynamic
programming.**
I guess everybody knows what *the Lowenstein distance* is.
Theoretically, the Lowenstein distance between two strings is bigger when the
strings are more different. These strings can be mere character strings or can
be strings of *entities* in a wider meaning. A good example of such
entities are the *tokens* used by the Pascal and C languages -
identifiers, keywords, variable names, numeric constants and so on.
We can for example associate a unique code with every token in a Pascal
file. If we associate `WHILE` with 201, `DO` with
202, integers with 203, identifiers with 204 and any other symbol (such as ;,
=, :, ' etc) with its `ASCII` code, then the line **while
X<10 do Inc(X);** would provide a code like:
while X < 10 do Inc ( X ) ;
201 204 060 203 202 204 040 204 041 059

If we go further on our way and create a table of symbols of identifiers,
we can assign a unique code to every new identifier, i.e. we'll write 204
instead of every **X**, 205 instead of every occurence of
`Inc` and so on. This way we'll get a string of numbers assigned
to a Pascal source file.
Now, what would happen if we took two Pascal files, coded each of them and
computed the Lowenstein distance between the two attached strings ? Of course,
we may divide this distance by the length of the files to get a relative
distance between 0 and 1. Well, and if this relative distance is doubtfully
close to 0, we can almost be sure that the two sources have a common origin. We
can easily clarify this by taking a closer look at the original files. So there
we have a handy method for detecting - with certain lacks, of course - any
plagiarism attempt.
Please notice that the method described above is not affected when we copy
a program and then change the variable names, due to the creation of a symbol
table. It is also immune to the change of justification and pagination, because
it ignores the separators (blanks, tabs, <CR>, <LF> etc). Special
thanks to my brother Cristi for this funny idea.

This is the solving method for the problem `E4P2` (I'm refering to the more original methods than
*give me your solution otherwise I delete your account* and so
on):

Let's create an array named **A** with **N** rows numbered from 1 to
N and 10*N+1 columns numbered from 0 to 10*N, where `A[i,j]`
represents the minimum number of hours required for obtaining **j** points
from the first **i** exams. But how can you get **j** points?
At the i-th exam, the student can't take more than a **k** mark between
0 and 10; so, at the first i-1 exams the student should obtain a number of j-k
points between j-10 and j (of course j-k>=0). In these conditions the time
used is `A[i-1,j-k]` for the first i-1 exams and
`H[i,k]` for the i-th exam.

Because we are interested that, if we obtain the same number j of points,
to minimize time `A[i,j]` used (in order to have more time
remaining for the other N-i exams...) we'll say that:
A[i,j]=min{ A[i-1,j-k] + H[i,k] ; 0<=k<=10, k<=j }

So to determine the elements of the line i of the array A we need the
elements from the line i-1. That means that A complets itself on the row (like
Mendeleev's table). Because for each i exam we need maximum 65535 hours , it
results that for the 10 medium we'll need maximum 6,553,500 hours, this being
the maximum element which can appear in the array A. The maximum memory needed
for A array is: `100 (rows) * 1000 (columns) * 4 (longint) = 400,000
bytes.`
After we have completed the array, we have to find:
- the maximum average and
- the number of hours given for each
exam.

With the average it's simple: we must search the element `A[N,
jmax]`, with the maximum value, but less than or equal to **T**. I
mean, I want to obtain as many points as possible in the first N exams (that
meaning all of them), but to be in time. If we have found the element
`A[N, jmax]`, the average is `(imax/N)`.
In order to reconstitue we'll do like this: We know that at the first
**N** exams we have obtained **jmax** points. We search that number
**k** for which
A[N-1, jmax-j] + H[N, k] = A[N, jmax]

meaning that at the **N**-th exam we got the **k** mark. We do the same
in order to find out the marks in the exams **N-1, N-2, ..., 1**.

**Computing the
complexity:**

To complete an element of the A array 11 computations have to be done
(for `0<=k<=10)`. Array A has `10*N`^{2} +
N elements, so the total calculation time is about **100
O(N**^{2}). For N=100, 1,000,000 elementary operations have to be
done. The calculation of the average and finding out of the numbers of hours
for each exam are done in **O(N)**.

**Remark:**

You could have used dynamic programming (the *rucsac* type), absolutly
clasical, as follows: a array A[t] has to be built, where A[t] is the maximum
number of points that I can obtain in **T** time. This solution has the
complexity **O(10*N*T)**, that means more bilions (watch and win). Beside
this, the memory needed is very large (an array with T elements integer
numbers).

That's it... A Happy New Year to all of you!

**P.S.** - The competitions are the only situation we are asked to be
selfish and not to give to anyone the results of our work. Why is it that right
now some of you get filantropists? :)