Fill the Cube Codevita 9 Solution

by

Fill the Cube Codevita 9 Solution

A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have huge difference in quality. The company manufactures walls of square shapes only to optimize their costs.

A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-quality material – material C.

To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnace starts heating.

Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.

Constraints

1 < N < 100

Input

  • First Line will provide the size of the original wall N.
  • Next N lines will provide the type of material (C and D) used for each brick by the novice employee.

Output

Size of the biggest possible C square wall which can be fitted in the final wall.

Time Limit

1

Examples

Example 1

Input

4

C D C D

C C D C

D D D D

C D D D

Output

3

Explanation

If the wall is placed with its left side at the bottom, space for a new C wall of size 2×2 can be created. This can be visualized as follows

D C D D

C D D D

D C D D

C C D C

The melted bricks can be visualized as follows

– – – –

– C – –

C C – –

C C – C

Hence, the maximum wall size that can be replaced is 2×2.

If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3×3 can be created. Post melting, this can be visualized as follows.

– – – –

C – – –

C – – –

C C C C

Hence, the maximum wall size that can be replaced is 3×3 in this approach.

Since no rotations followed by heating is going to a yield a space greater than 3×3, the output is 3.

Example 2

Input

7

C D D C D D D

C D D C D D D

D D D D D D C

D C D C D D D

D D D C D C D

C D D C D C C

C D C D C C C

Output

5

Explanation

If the wall is placed with its left side at the bottom, a space for new C wall of size 5×5 can be created. This can be visualized as follows

D D C D D C C

D D D D C C C

D D D D D D C

C C D C C C D

D D D D D D C

D D D C D D D

C C D D D C C

When this orientation of the wall is heated, a space for new C wall of size 5×5 is created after the D bricks melt

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ _ _ _C

_ _ _ _ _ _ C

_ _ _ _ _ C C

C C _ C C C C

C C C C C C C

Whereas, if the rotation was not done, the wall formed after the D bricks melt will be as follows

_ _ _ _ _ _ _

_ _ _ _ _ _ _

_ _ _ C _ _ _

C _ _ C _ _ _

C _ _ C _ _ C

C _ _ C _ C C

C C C C C C C

When this orientation of the wall is heated, a space for new C wall of size 3×3 only is created after the D bricks melt

Hence rotation is important and correct answer is 5×5

Since no rotations followed by heating is going to a yield a space greater than 5×5, the output is 5.

SOLUTION

Program: Fill the Cube Codevita 9 Solution in C++

#include<bits/stdc++.h>
using namespace std;
bool isPerfectSquare(int n) 
{ 
    for (int i = 1; i * i <= n; i++) { 
  
        // If (i * i = n) 
        if ((n % i == 0) && (n / i == i)) { 
            return true; 
        } 
    } 
    return false; 
} 
int getMaxArea(int hist[], int n) 
{ 
    // Create an empty stack. The stack holds indexes  
    // of hist[] array. The bars stored in stack are  
    // always in increasing order of their heights. 
    stack<int> s; 
  
    int max_area = 0; // Initialize max area 
    int tp;  // To store top of stack 
    int area_with_top; // To store area with top bar 
                       // as the smallest bar 
  
    // Run through all bars of given histogram 
    int i = 0; 
    while (i < n) 
    { 
        // If this bar is higher than the bar on top  
        // stack, push it to stack 
        if (s.empty() || hist[s.top()] <= hist[i]) 
            s.push(i++); 
  
        // If this bar is lower than top of stack,  
        // then calculate area of rectangle with stack  
        // top as the smallest (or minimum height) bar.  
        // 'i' is 'right index' for the top and element  
        // before top in stack is 'left index' 
        else
        { 
            tp = s.top();  // store the top index 
            s.pop();  // pop the top 
  
            // Calculate the area with hist[tp] stack  
            // as smallest bar 
            area_with_top = hist[tp] * (s.empty() ? i :  
                                   i - s.top() - 1); 
  
            // update max area, if needed 
            if (max_area < area_with_top) 
                max_area = area_with_top; 
        } 
    } 
  
    // Now pop the remaining bars from stack and calculate 
    // area with every popped bar as the smallest bar 
    while (s.empty() == false) 
    { 
        tp = s.top(); 
        s.pop(); 
        area_with_top = hist[tp] * (s.empty() ? i :  
                                i - s.top() - 1); 
  
        if (max_area < area_with_top) 
            max_area = area_with_top; 
    } 
  
    return max_area; 
} 
  
int main()
{
    int n;
    cin>>n;
    
    char arr[100][100];
    int arr2[100][100];
    int row[100], col[100];
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>arr[i][j];
        }
    }
    
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(arr[i][j]=='D')
              arr2[i][j] =0;
            else 
               arr2[i][j] = 1;  
        }
    }
    
    for(i=0;i<n;i++)
    {  int sum=0;
        for(j=0;j<n;j++)
        {
            sum = sum+ arr2[i][j];
        }
        row[i] =n - sum;
    }
    
    for(i=0;i<n;i++)
    {  int sum=0;
        for(j=0;j<n;j++)
        {
            sum = sum+ arr2[j][i];
        }
        col[i] =n - sum;
    }
    int count = 0;
    for(i=0;i<n;i++)
    {
        if(row[i]!=0)
         {
             break;
            
         }
         else
          count++;
         
    }
    int count2 = 0;
    for(i=0;i<n;i++)
    {
        if(col[i]!=0)
         {
             break;
            
         }
         else
          count2++;
         
    }
     if( count == n && count2 ==n)
       cout<<"0";
else
{
       
    int area1 , area2;
    area1 = getMaxArea(row ,  n) ;
    area2 = getMaxArea(col ,  n);
    
     if (isPerfectSquare(area1) &&  isPerfectSquare(area2) ) 
         {
               int max1 = max(sqrt(area1), sqrt(area2));
               cout<<max1;
         } 
    else if(isPerfectSquare(area1) && !isPerfectSquare(area2) )
        cout<<sqrt(area1);
    else if(isPerfectSquare(area2) && !isPerfectSquare(area1) )
        cout<<sqrt(area2);    
    else 
      cout<<"1";    
    
}
}

Codevita Season 9 All Questions Solution

Leave a Comment

3 × 5 =