PROBLEM LINK:
Author: chitranshi351
Tester: chitranshi351
Editorialist: chitranshi351
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
Bob, the builder is working on a city project, where the city has n adjacent buildings, numbered from 0 to n-1. Each building is made by stacking 1x1 blocks. We are given an array of n elements, where ith element represents the height of the ith building.
Bob can rebuild and modify the height of any building that he is currently on by rearranging the existing blocks or any additional blocks that he has in his bag. Bob can move to an adjacent building only if it is at the same height as his current building. He can keep the extra blocks(if any) from the current building, in his bag when he moves on to the next building.But since the blocks are fragile, he can only carry the blocks of the current building to the just next building.
Help Bob find the maximum number of consecutive buildings that he can visit this way.
NOTE : Use fast Input/Output
Prerequisites:
- knowledge of array operations.
QUICK EXPLANATION:
It uses a standard concept of variable size sliding window. Don’t forget the blocks of a building can be carried to only the next building. Also, you can reconstruct the current building. So be wise and be greedy 
EXPLANATION:
We must choose the starting point wisely such that we can cover the maximum number of buildings. And since the blocks of one building cab be carried to only the very next building and reconstruction of current building is allowed, we will try to reconstruct the building by using the maximum number of old blocks as we cannot carry them forward to save the most of the current building blocks to carry forward.
Initially when we start, we do not have any blocks in our bag, so we can reach another building only if it’s height is less than or equal to the current building. Don’t forget to carry forward the extra blocks(if any). Once we reach the building, we check if we have any extra blocks in our bag. If yes, we try to reconstruct this building with the blocks in our bag, so that we can save the new blocks and keep them in my bag for the next journey. If we can reach the next building by using the current building blocks and the blocks in my bag, we move forward, otherwise we stop and compare if this is the maximum length we have covered. We repeat this process till we reach the end of the array.
SOLUTIONS:
Setter's Solution
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Codechef {
public static void main(String[] args) throws java.lang.Exception {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim());
while (t-- > 0) {
int n = Integer.parseInt(br.readLine().trim());
int[] arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine().trim());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int i = 0, j = 0;
int blocks = 0;
int maxB = 1;
while (j < n - 1) {
if (blocks + arr[j] >= arr[j + 1]) {
if (blocks >= arr[j + 1]) {
blocks = arr[j];
} else {
int rem = arr[j + 1] - blocks;
blocks = arr[j] - rem;
}
j++;
maxB = Math.max(maxB, j - i + 1);
} else {
i = j + 1;
blocks = 0;
j++;
}
}
System.out.println(maxB);
}
} catch (Exception e) {
}
}
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T > 0)
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
int i = 0, j = 0;
int blocks = 0;
int maxB = 1;
while(j < n-1){
//possible to make next move
if(blocks + arr[j] >= arr[j+1])
{
//if whole building can be constructed using prev blocks
//then rebuild, and carry the blocks of curr building forward
if(blocks >= arr[j+1])
{
blocks = arr[j];
}
else
{
//construct building using all old blocks
//and use rem curr blocks
//to maximise the curr blocks we can carry forward
int rem = arr[j+1]-blocks;
blocks = arr[j]-rem;
}
j++;
//include next building as we can reach it
maxB = max(maxB, j-i+1);
}
//not possible to make next move
else
{
i = j+1;
blocks = 0;
j++;
}
}
cout << maxB << endl;
T--;
}
return 0;
}