Solutions for Round 4

Problem 1: Communication
Problem 2: The Wonderful Undergraduate Life


Problem 1: Communication

Only a few participants at this contest sent solutions to this problem, but many of them should be quoted in the chapter most interesting solutions.
The algorithm is based on a simple idea: every data block is sent to its destination on the shortest way. The priority of a data block is set by the distance between its actual position and its destination.

Remark:

Any data block has only two convenient movement directions. Because there still were many confusions regarding the size of the waiting lines (some of the participants calculated the maximum length during the transmission, others before the transmission), I didn't take into consideration this request.

Tests

Solution no. 1 (Pascal)
Solution no. 2 (C)


Problem 2: The Wonderful Undergraduate Life

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:
  1. the maximum average and
  2. 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*N2 + N elements, so the total calculation time is about 100 O(N2). 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? :)

Tests

Solution no. 1 (Pascal)
Solution no. 2 (C)


[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!