Google Kickstart Round E 2020

Problem B : High buildings

video explanation:

Problem:

In an unspecified country, Google has an office campus consisting of N office buildings in a line, numbered from 1 to N from left to right. When represented in meters, the height of each building is an integer between 1 to N, inclusive.

Andre and Sule are two Google employees working in this campus. On their lunch break, they wanted to see the skyline of the campus they are working in. Therefore, Andre went to the leftmost point of the campus (to the left of building 1), looking towards the rightmost point of the campus (to the right of building N). Similarly, Sule went to the rightmost point of the campus, looking towards the leftmost point of the campus.

To Andre, a building x is visible if and only if there is no building to the left of building x that is strictly higher than building x. Similarly, to Sule, a building x is visible if and only if there is no building to the right of building x that is strictly higher than building x.

Andre learned that there are A buildings that are visible to him, while Sule learned that there are B buildings that are visible to him. After they regrouped and exchanged information, they also learned that there are C buildings that are visible to both of them.

They are wondering about the height of each building. They are giving you the value of N, A, B, and C for your information. As their friend, you would like to construct a possible height for each building such that the information learned on the previous paragraph is correct, or indicate that there is no possible height construction that matches the information learned (thus at least one of them must have been mistaken).

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of a single line with four integers N, A, B, and C: the information given by Andre and Sule.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no possible height for each building according to the above information, or N space-separated integers otherwise. The i-th integer in y must be the height of the i-th building (in meters) between 1 to N.

Solution:

• Case 1: Let us first assume that C > 1.
  Consider any 2 values P and Q such that 1 ≤ P < Q ≤ N. In this case, we can put A — C buildings with height P on the left and B — C buildings with height P on the right and C buildings in the middle with height Q. Now, we have satisfied the constraint of A, B and C. We have N — A — B + C buildings remaining which should not be visible from either side. This can be done by assigning them height P and hiding them between the buildings with height Q.
• Case 2: C = 1. In this case, we cannot hide buildings between buildings with the maximum height since there is only one of them. We would have to look for some cases here:
• A + B — C = N,
  In this case, we have no buildings to hide, thus we can assign the buildings similar to Case 1 when C > 1 with heights P and Q.
• Either A > 1 or B > 1. In this case, A + B — C < N. A + B is at least 3 and C = 1. Thus, we can say that N > 2 holds. Consider any 3 values P, Q and R such that 1 ≤ P < Q < R ≤ N. In this case, we can put A — 1 buildings with height Q on the left, B — 1 buildings with height Q on the right side and a building with height R in the middle. Now, we have satisfied the constraint of A, B and C. We have N — A — B + C buildings remaining which should not be visible from either side. Let the height of remaining buildings be P. We have already placed at least 2 buildings, and all the buildings that we placed so far are higher than the buildings that we want to hide, so we can hide remaining buildings anywhere in between the already placed buildings.
• A = 1 and B = 1
  This means that the building with maximum height is both on the leftmost point and rightmost point and it is not possible for N > 1. So, the answer is IMPOSSIBLE in this case.

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
int t;
cin>>t;
int n,a,b,c;
for(int i=0;i<t;i++){
cin>>n>>a>>b>>c;

cout<<”Case #”<<i+1<<”: “;

if(a+b-c>n || (a+b-c==1 && n>=2)){
cout<<”IMPOSSIBLE”<<endl;
}
else{
if(n==1){
cout<<”1"<<endl;
}
else if (n==2){
if(c==2){
cout<<”2 2"<<endl;
}
else if(a==2){
cout<<”1 2"<<endl;
}
else if(b==2){
cout<<”2 1"<<endl;
}
else{
cout<<”IMPOSSIBLE”<<endl;
}

}
else{
vector <int> ans;
ans.reserve(n);
for(int j=0;j<a-c;j++){
ans.push_back(2);
}
for(int j=0;j<c;j++){
ans.push_back(3);
}
for(int j=0;j<b-c;j++){
ans.push_back(2);
}
int hide=n-(a+b-c);
if(hide>0){
ans.insert(ans.begin()+1,hide,1);
}
for(int j=0;j<n-1;j++){
cout<<ans[j]<<” “;
}
cout<<ans[n-1]<<endl;
}
}


}
}