# Problem I. 100. (March 2005)

**I. 100.** We are given a square lattice of size *mxn* (with positive integers *m* and *n*). Unit square based columns are put onto each square. The front and side views of this bar chart-like solid are represented by the vectors *u*=(*u*_{1}, *u*_{2}, ..., *u*_{m}) and *v*=(*v*_{1}, *v*_{2}, ..., *v*_{n}), where the numbers *u*_{i} and *v*_{j} are the heights of the rectangles being shadows of the columns.

Prepare a sheet into which coordinates of vectors *u* and *v* can be entered, then it computes the matrix describing heights of the columns of *the* (or, *a possible*) solid of *maximal volume.* Your program should recognize with writing ``Error!'' (see the *diagram,*), if no such solid exists.

v_{1} | v_{2} | v_{3} | v_{4} | v_{5} | ... | ... | ... | v_{n} | |||||

Error! | * | * | |||||||||||

u_{1} | |||||||||||||

u_{2} | * | ||||||||||||

... | |||||||||||||

u_{m} |

Notice that this is a converse of problem **I. 98.**, where a matrix describing the heights of the individual columns was given and we had to display the front and side views of the solid. Now we have to reconstruct the solid of maximal volume from the front and side views.

A text file (i100.txt) is to be submitted containing the precise description of the applied algorithm, further, the detailed justification of the fact that your algorithm gives the correct answer in all cases (that is, whether or not the solid exists, and, if it does, the algorithm produces the one with the required property. Finally, the sheet itself (i100.xls, ...) is also to be submitted.

(15 pont)

**Deadline expired on April 15, 2005.**

### Statistics:

8 students sent a solution. 15 points: Kisfaludi-Bak Sándor, Stippinger Marcell, Ureczky Bálint. 14 points: Acsai Péter, Vincze János. 13 points: 1 student. 7 points: 1 student. 6 points: 1 student.

Problems in Information Technology of KöMaL, March 2005