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 chartlike 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 15 April 2005.
Statistics:
