PROBLEM LINK:
Author: Aman Nautiyal
Tester: Suyash Saxena
Editorialist: Suyash Saxena
DIFFICULTY:
MEDIUM
PREREQUISITES:
None
PROBLEM:
Given the length l, breadth b and height h of n buildings in a Lego model (height can be 0 indicating that instead of a building there is a gap there of dimension l * b) find out the total volume of dust which can be accumulated in the gaps between the buildings. Hence, given the amount of time (in seconds) to clean a cubic unit block of dust and a constant time of 60 seconds to clean the dust off the buildings, find the total time (in seconds) to clean the whole model.
QUICK EXPLANATION:
Before we start calculating the dust accumulated in the gaps, lets handle the corner case of 0 buildings in the model, i.e., the input contains n buildings each of height 0. In this case the final answer should be 0 instead of 60 as there are no buildings to clean the dust off of. This corner case was actually the reason behind many, many incorrect solutions.
Once this is handled, we can start by dealing just with the given heights and find the total volume of dust which we can later multiply by the given length and breadth since it is constant for the whole model. Using the two pointer approach keep track of the height of highest building on the left as well as on the right of current building, then simply use the formula min(maxLeft, maxRight) - h_i to calculate the number of dust blocks over the top of current i^{th} building. Add all of these and then multiply with l, b and s using modular arithmetic, add 60 to the result which would give the final required answer.
EXPLANATION:
Before we dive into the details of how to calculate the amount of dust accumulated, let’s see what are the broad distinct cases that we have to deal with:
- There are buildings with gaps between them, or suitable height differences amongst buildings for dust to get accumulated.
- There is just one building, or buildings with same height, or models where buildings have heights in only increasing or only decreasing order or heights of buildings keep increasing up to a point and then starts decreasing.
- There are no buildings in the model (this case would be represented by all the n values have height as 0.
The first two cases will be handled by the logic we will use to calculate the amount of dust accumulated, while the third case is what we need to handle explicitly.
We can handle the third case while we are reading the n values or after they have been read. All we need to do is count the number of zeroes in the input and if they are same as the value of n, then the answer is simply 0 nothing else needed.
Now let’s handle the first two cases, how to actually find the dust accumulated within the gaps.
From the above graph, we can infer certain things,
- The length in which the dust is accumulated is defined by the height of the buildings on the left and right.
- The height of the dust accumulated is defined by the smaller of the highest left and right buildings.
Using these two inferences, we can calculate the total number of blocks of dust that can be accumulated on top of each building in the model. (Each block of dust = 1 x l x b cubic unit).
For simplicity we can assume the length and breadth of the model to be 1 and later we can simply multiply our answer with the original values. For each building we will find the height of the highest buildings on left and right respectively. Then find the minimum of the two as we can see that the dust accumulated has the same height as the smaller of the two buildings. It can’t be more than that because then it will just spill over. This is the same reason for unaccumulated dust on the buildings at the extreme ends, dust just spills over to the other sides.
Since the constraints of the problem are small we can do this by brute force with time complexity of O(n^2), like this
int dustCollected(int heights[], int n) {
int totalDust = 0;
for (int i = 0; i < n; i++){
int maxLeft = 0, maxRight = 0;
for (int j = 0; j <= i; j++){
maxLeft = max (maxLeft, heights[j]);
}
for (int j = i; j < n; j++) {
maxRight = max (maxRight, heights[j]);
}
totalDust += min (maxRight, maxLeft) - heights[i];
}
return totalDust;
}
But a better approach would be to use two pointers, left and right which are initially placed at the first and last index of the array. While left is less than right, we do the following:
- If the height of left building is greater than the height of right building, check if it is greater than the maximum height on right, if it is update max right height, else find the value of maxRightHeight - heights[right] and add it to final result. In either case, decrement the value of right by 1 so that it moves 1 step to the left.
- On the other hand, if the height of left building is smaller or equal to the right, do the same things as above, just instead of checking for max right, check max left, find the value of maxLeftHeight - heights[left], add it to the final result and instead of decrementing, increment left by 1 so that it moves 1 step to the right.
Then simply use the result to find the final answer. Result we have obtained is nothing but the total number of dust blocks present in the model.
ll findTotalGap(ll n, ll height[])
{
// support variables
int left = 0, right = n - 1, maxLeft = height[i], maxRight = height[j], res = 0, e;
while (left <= right)
{
// case 1: left points to a bigger element, so we advance j
if (height[left] > height[right])
{
e = height[right];
if (e > maxRight)
maxRight = e;
else
res += maxRight - e;
j--;
}
// case 2: right points to a bigger/equal element, so we advance left
else
{
e = height[left];
if (e > maxLeft)
maxLeft = e;
else
res += maxLeft - e;
left++;
}
}
return res;
}
This solution has a time complexity of O(n)
Once we have calculated the number of blocks of dust present on each building we can simply multiply the result by the original values of l and b to find the correct volume. Then multiply the result by s seconds and add 60 to it. For doing all the mathematical operations (especially multiplication) we will use modular arithmetic. It will look something like this in C++
ans = findTotalGap(n, h);
ans = ((ans % mod) * (l % mod) * (b % mod) * (s % mod)) % mod;
ans = ((ans % mod) + 60) % mod;
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
#include <chrono>
#define ull unsigned long long int
#define ll long long int
#define incr(n) for (ll i = 0; i < n; ++i)
#define decr(n) for (ll i = n - 1; i >= 0; --i)
#define rep(x, s, n) for (ll x = s; x < n; ++x)
using namespace std;
ll findTotalGap(ll n, ll height[])
{
// support variables
int i = 0, j = n - 1, maxLeft = height[i], maxRight = height[j], res = 0, e;
while (i <= j)
{
// case 1: i points to a bigger element, so we advance j
if (height[i] > height[j])
{
e = height[j];
if (e > maxRight)
maxRight = e;
else
res += maxRight - e;
j--;
}
// case 2: j points to a bigger/equal element, so we advance i
else
{
e = height[i];
if (e > maxLeft)
maxLeft = e;
else
res += maxLeft - e;
i++;
}
}
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll t;
ll mod = 1000000007;
cin >> t;
while (t--)
{
ll l, b, n, s;
ll countzero = 0;
cin >> l >> b >> n >> s;
if (n == 0)
{
cout << 0 << endl;
continue;
}
ll h[n];
incr(n)
{
cin >> h[i];
if (h[i] == 0)
countzero++;
}
if (countzero == n)
{
cout << 0 << endl;
continue;
}
ll ans = 0;
ans = findTotalGap(n, h);
// ans = ans * l * b * s;
// ans += 60;
ans = ((ans % mod) * (l % mod) * (b % mod) * (s % mod)) % mod;
ans = ((ans % mod) + (60 % mod)) % mod;
cout << ans << endl;
}
return 0;
}