[Competitive Programming Review Note] Google Kick Start Round E problem 2 — High Buildings

I’ve been participating in Google’s Kickstart which is a competitive programming contest and I found out that writing a review note on those problem I struggled would be great to improve my skills and help others who struggled as well!

I use C++ for competitive programing (because it is everyone’s favorite language — haha) and I would love to discuss about the problem 2, 3, 4 of Round E which happened in August 23. (This post will talk about problem 2)

[Problem2: High Buildings]

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.

Limits

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ C ≤ N.
C ≤ A ≤ N.
C ≤ B ≤ N.

Test Set 1

1 ≤ N ≤ 5.

Test Set 2

1 ≤ N ≤ 100.

Sample

Input

Output

3
4 1 3 1
4 4 4 3
5 3 3 2
Case #1: 4 1 3 2
Case #2: IMPOSSIBLE
Case #3: 2 1 5 5 3

Comments

Yeah, we basically use the information of # buildings the left person can see, # buildings the right person can see, and # buildings both can see to give a possible building combination.

So I came up with an approach which generates the combination of buildings based on the constraints and used “greater stack”(which will only accept the new element if the new element is bigger than equal to the top of the stack) concept to find the #buildings either the left or right can see or both can see. This was so straightforward, and I got TLE for their second test case which is larger test set than the first test case.

Since I was struggling with their problem 3 and 4, I wasn’t able to spend my time finding a better way to solve this during the competition. But after the competition, I revisited the problem to figure out what can be optimized.

1. My approach is literally investigating all of the possible cases!!!!
2. Plus, at each investigation, I’m using O(N) further investigation to collect the A, B, and C information.

This so brute force way should be improved and I found some of the parts I can reduce a time.

The idea is, “Change the way of THINKING!!!!”

We just need to return one of the valid answers, then let’s just directly make a valid answer following the constraint instead of finding a valid one out of all!

In order to do so, some mathematical proof was needed for the base case!

Base case will check “IMPOSSIBLE” case and simple cases such as # of building == 1 or two.

Under the variable condition where,
A == # of buildings the left person sees
B == # of buildings the right person sees
C == # of buildings both see
a == # of buildings ONLY the left person sees
b == # of buildings ONLY the right person sees

A + B - C should be ≤ N because A + B == a + b + 2C and so A + B - C == a + b + 2C - C == a + b + C. Why? let say there are ‘d’ many buildings that are not included in any of A, B, C, a and b. Then the total # of building (N) is a + b + d, and so A + B - C which is == to a + b + C cannot be greater than N because the only case this will work is C ==0 and d == 0 but C cannot be 0 in any cases (there should be at least one building that is view-shared by both the left and the right person)

Also, except for the case where total # of buildings (N) is 1, A + B - C (equivalent to a + b + C) cannot be 1 because to get the minimum value of (a + b) there should be only one building and so both a and b == 0 and C == 1. If N ≥ 2, then the minimal value of a + b + C is 2 which is the case of two buildings with the same height.

Based on this mathematical proof, we can say

Then, let’s tackle down simple cases which is N == 1 and N ==2. Since now we don’t have to worry about “IMPOSSIBLE CASE” if N ==1, then the height of this building can be anything.

For the N ==2, the possible cases are (1) two buildings with the same height (which will have C == 2), or (2) either of them is higher than the other (ex) “1 2” or “2 1”

Lastly, we have to handle a generic case where it is NOT IMPOSSIBLE an N ≥ 3. Since we just need to return one of the valid combination, let’s only use “1”, “2”, “3” to represent the shortest building, the medium-size building, and the tallest building respectively.

In the generic case, we have to take care of ‘d’ which is the “invisible buildings” to any of them. According to my mathematical proof above, d == N - (A + B - C). And we will first build the valid building combination based on A(technically ‘a’), B(technically ‘b’), C and then insert those invisibles in some point between the leftmost building and the right most building and the invisible’s height will be “1” cuz “1” is not visible by sitting between “2” or “3”

To summarize, we put buildings that are only visible to the left person (a) by using “2” and then put the buildings that are visible by both the left person and right person(C) by using “3” and then put the buildings that are only visible to the right person (b) by using “2.” Then insert those invisibles at some point between the two buildings. In that case, we are not only following the constraint of A, B, and C and meet the requirement of N by padding those invisibles at some appropriate place

That’s it!!! Thanks to this optimized version, now we are not inspecting all of possible cases, but directly building a valid combination which will take O(1) at its best case and O(N) on average!

The entire code for this is:

Key point of this problem was: figure out all of the possible cases by N and start building from the base case and so you can create a simple and less complicated generic case handler!

If you interested in Google Kickstart Round E’s problem 3 — Toys
→ https://medium.com/@eunpyolee0420/competitive-programming-review-note-google-kickstart-round-e-problem-3-e9e645fd90c7

If you interested in Google Kickstart Round E’s problem 4— Golden Stone
→ https://medium.com/@eunpyolee0420/competitive-programming-review-note-google-kickstart-round-e-problem-3-e9e645fd90c7