Solution of Stax

Let's take a look at Xorin's perspective from left to right, and, for each column, calculate maxXorin[j] = the height of the stack Xorin sees. It is clear that Xorin will only see the tallest stack out of all those which lie on the same column.

The same idea applies for maxXoranna[i].

When attempting to reconstruct a possible solution, for each stack (i, j), two conditions must hold:

  • stax[i][j] ≤ maxXorin[j]
  • stax[i][j] ≤ maxXoranna[i]

In other words, the height of any stack must not exceed the height that Xorin sees, and the height that Xoranna sees.

However, this piece of information is incomplete. We also need to make sure that each column j (and line i) contains the value maxXorin[j] (and maxXoranna[i], respectively) at least once. To make sure this always happens, we can try a greedy approach: stax[i][j] = min(maxXorin[j], maxXoranna[i]), for each set of coordinates (i, j) that need to contain a stack.

Time complexity: O(n*m + n*h * m*h) ≈ O(n*m)

C++ solution (Sergiu Puscas)

    1 #include <iostream>
    2 #include <cstring>
    3 #define nmax 1000
    4 #define hmax 10
    5 using namespace std;
    6 
    7 int n, m, h, a[nmax][nmax], maxXorin[nmax], maxXoranna[nmax];
    8 string topView[nmax], XorinView[nmax], XorannaView[nmax], sol[nmax];
    9 
   10 int main() {
   11     cin>>n>>m>>h;
   12     cin.get();
   13 
   14     for(int i=0; i<n; i++) getline(cin, topView[i]), sol[i].resize(m, '.');
   15     for(int i=0; i<h; i++) {
   16         getline(cin, XorinView[i]);
   17         for(int j=0; j<m; j++)
   18             if(XorinView[i][j] == '#' && maxXorin[j] == 0) maxXorin[j] = h-i;
   19     }
   20 
   21     for(int i=0; i<h; i++) {
   22         getline(cin, XorannaView[i]);
   23         for(int j=0; j<n; j++)
   24             if(XorannaView[i][j] == '#' && maxXoranna[n-j-1] == 0) maxXoranna[n-j-1] = h-i;
   25     }
   26 
   27     for(int i=0; i<n; i++)
   28         for(int j=0; j<m; j++)
   29             if(topView[i][j] == '#')
   30                 sol[i][j] = '0' + min(maxXorin[j], maxXoranna[i]);
   31 
   32     for(int i=0; i<n; i++) cout<<sol[i]<<"\n";
   33     return 0;
   34 }
   35 
Questions?

Sponsors Gold