Round 4: December 5th, 1997
Problem 1: Communication
Problem 2: The Wonderful Undergraduate Life
One thousand miles' trip begins with a step.
Lao Tse (6-th Century B.C.)

Problem 1: Communication (40 points)

Prolog:
We lately witness the appearance of some applications (more and more of them) that complain about more and more powerful computing systems. The new constructive solutions for the most performant computing systems are based on parallel architecture. An interesting classification of computing systems was proposed by Flynn, in 1966. This classification is based on the number of data streams and of instruction streams, considered as a criterium.
According to this criterium there are 4 categories of computing systems:
SISD are the "classic" computers, known as "von Neumann machines", having only one processor that can execute, at a given moment, only one instruction on a single set of data.
SIMD are computers that have only one instruction stream, but several data streams, so they have only one central unit, with one control unit, but with more processing units. To this category belong, for example, the supercomputers ILLIAC-IV, DAP, Goodyear MPP.
The MISD computers have several instruction streams and only one data stream. These computers did not prove themselves to be efficient, neither from a comercial, nor from a scientific point of view.
The MIMD category includes computing systems with multiple data and instruction streams. In this case the parallelism is made by connecting several processors (that part the same memory) or by connecting several computers. Examples: Cray 2, Fujitsu VP 2000, Convex C-2, IBM SP1, IBM SP2.

Further we are going to consider a machine of the MIMD type. Oversimplified, such a machine is made of several processing entities (we will call them nodes) and of communication lines. A node can contain a processing unit, an external memory, interfaces for the links with the other nodes, a component that controls the communication, etc. A communication line connects two nodes and allows the transmission of data between the two connected nodes in the following circumstances:
  1. The data is grouped in blocks of fixed length, having as a header the addressee's adress;
  2. On a connection line only one block of data can be sent at a given time (in one way or the other);
  3. The processors work at the same time (they are synchronized), so we can define a communication stage as being the simultaneous transmission of data blocks between two nodes that have a direct connection established between them ;the data blocks having a fixed length, the duration of a communication stage is constant; this way we can tell how long a communication process lasts in a number of communication stages;
  4. If several messages arrive in a node (on different communication lines) and they want to continue their way on the same connection, a situation of conflict between links (connections) occurs. In this case only one block of data will be transmited (sent), the other being placed in a waiting line (string) of the communication line.
  5. In a communication process, each node x has to send only one block of data with the final destination d(x) (d(x)<>d(y), for any x<>y); the communication consists of the transmission of all the data blocks to their destinations.
Of course, there are several possible algorithms of planning the communication and several possible criteria to compare them: the duration of the communication process, the size of the waiting strings (lines), their determinative or aleatory nature, the on-line or off-line nature.

Text:
A MIMD machine is considered, one in which the processing entities are displayed in the nodes of a bi-dimensional grid with n lines and m columns (1<= n, m <= 20). The processor in the position (i, j) is directly connected with the processors in the positions (i-1, j), (i, j-1), (i+1, j), (i, j+1); of course, if these positions belong in the grid. The processors are numbered from 1 to n*m, in the lines' order, and in each line, in the columns' order.
Your task is to describe an algorithm which, for a given communication process, does the communication in a minimum time, with no restrictions as regards the dimension (size) of the waiting strings associated to the communication lines.

Input Data:
The name of the input file is read from the keyboard. The input file has the following structure:
      n m
      d11 d12 ... d1m
      d21 d22 ....d2m
      ...........
      dn1 dn2 ... dnm
, where n and m represent the dimensions of the grid, and dij is the number associated to the target processor of the block of data transmitted by the processor in the (i, j) position, for any 1<=i<=n, 1<=i<=m.

Output Data:
The name of the output file is read from the keyboard. For each stage of communication you have to write in the file:
On the last line you will display the maximum size reached by the waiting strings associated to the connection lines.

Restrictions:
Each program will be introduced by a comment in which the algorithm to be used is shortly described and so is the type of representation of the information.

Example Input and Output:
For the input file:
      1 5
      5 2 4 3 1
The output file will be:
      Round 1
      1 1 1 1 2
      3 1 3 1 4
      5 1 5 1 4
      Round 2
      1 1 2 1 3
      5 1 4 1 3
      Round 3
      1 1 3 1 4
      5 1 3 1 2
      Round 4
      1 1 4 1 5
      5 1 2 1 1
      4 1 4 1 3
      2

Execution time: maximum 3 seconds/test on a 586/133 MHz.

Emanuela Mateescu,
"Grigore Moisil" High School,
Iasi.

Problem 2: The Wonderful Undergraduate Life (35 points)

"The student is like a bottle. The professor comes and pours knowledge inside him, and pours, and pours, and sometimes the student overflows, but the professor still pours and pours, and pours, and..."

We all love university very much and I know you're all eager to get there. Here's how you'll get your grades there: there are only N subjects of study and for each subject you'll have to take a final exam, which will result into a mark between 10 (the best) and 0 (the poorest). An exam is promoted when the mark you get is at least 5. Otherwise the exam is failed.
Professor P(1) teaches the first subject and it's easy to get a good mark: his previous students observed that H(1, 10) hours of study guarantee you a mark of 10, H(1, 9) hours of study guarantee you a mark of 9 and so forth. If you only study H(1, 1) hours like bad students do, you'll get a 1. Of course, if you don't learn anything at all, you'll get a zero, therefore H(1, 0) = 0.
So much for the first exam. The marking systems for the other exams work similarly: professor P(i) teaches subject i and his older students found that it takes H(i, 10) hours of study to get a 10, H(i, 9) hours to get a 9 and so on. Again, H(i, 0) = 0.
All of these data can be gathered in the matrix H, having N lines (numbered from 1 to N) and 11 columns (numbered from 0 to 10). H(i, j) is the amount of time that a student must dedicate to subject i if he wants to get a j mark. It is guaranteed that j1 > j2 means H(i, j1) > H(i, j2), which means that, for any subject, the bigger the mark you want to get, the more you have to study.

A student has a total amount of time T (given in hours) to study for all the exams. He can distribute the time anyway he wants. There are two important questions:
  1. Can our virtuous student promote all the exams? If not, what is the maximum number of exams he can promote?
  2. What is the best average our student can get and how many hours does he have to study for each subject in order to get that average?
    3. These are the questions that your program will have to answer.

    Input Data:
    The input data will be found in the text file HOPES.TXT in the following format:
          Line 1:             N T
      Line 2:             H(1,1) H(1,2) ... H(1,10)
      Line 3:             H(2,1) H(2,2) ... H(2,10)
      .............................................
      Line N+1:           H(N,1) H(N,2) ... H(N,10)
    N and T are integer numbers, 1<=N<=100, 0<=T<=10,000,000 (You don't believe it ? Wait till you see it!). All the numbers in matrix H are integers between 0 and 65,535 (separated by spaces in the input file).

    Output Data:
    Output will go to the text file REALITY.TXT; on the first line, you will print either the message 
          YES
    if the student has the time to promote all the exams, or the message 
          NO F
    where F is the maximum number of exams that the student can promote.
    On the second line you will print the highest average that the student can get with three decimals. Starting with the third line you will print N numbers S(1), S(2), ..., S(N), each number in one line, where S(i) represents the number of hours that the student dedicates to subject i.

    Example:

          HOPES.TXT
      3 150
      1 15 27 29 46 56 59 65 84 87
      5 17 22 28 37 43 60 77 87 102
      11 29 49 63 69 70 75 80 95 109

      REALITY.TXT
      NO 2
      5.667
      87
      43

    Notes:

    1. Running time: one second for every test. You won't get any points for the tests that exceed the running time.
    2. The programs will be tested on a Cyrix P166+ with 16 MB RAM and MS-DOS 6.22 operating system.
    3. When your program is run, at least 550 kB base memory and 13 MB extended memory will be free.
    4. Programming languages accepted are:
      • Borland Pascal 7.0
      • Borland C++ 3.1
    5. If you want your programs to be compiled in the protected mode, make the first line of your program be: {Protected}.
    6. Please DO respect the requested output format!
    7. The best program will by rewarded with my everlasting gratitude for optimizing my studying time :)
    8. Any resemblance with real facts, people, places is not accidental at all.
    9. E-mail me at cfrancu@pcnet.pcnet.ro for further questions.

    Catalin Frâncu,
    Politehnica University,
    Bucharest.

    [First Round] [Previous Round] [Next Round] [Last Round] [Româna] [Go Back!]