Problem Link:
Clash Wildcard 2022
Practice
Problem:
Given an array of integers representing bread and cheese stacked over each other, find out if any cheese falls of the sandwich.
Explanation:
Consider an array: [5,3,7,9,11,6]. Elements at index 1, 3, and 5 are breads where as elements at index 2, 4 and 6 are cheese. In this sandwich, cheese of value 6 falls on bread of size 11. Cheese of value 9 falls on bread of size 7, and since bread of size 7 can hold no more than 7 units of cheese, 2 units of cheese overflows. These 2 units of cheese can only be caught by a bread larger than size 7, and since no such bread exists, cheese will fall off the sandwich. The bread of 5 units will only hold the 3 units of cheese even though it has the capacity to hold 2 units more.
Consider 2 breads of size 7 and 4 stacked over each other, meaning they have no cheese between them. The bread of size 4 covers 4 units of area of the bread of size 7. In other words, both the breads can replaced by single slice of bread of 7 units.
In array: [11, 9, 7, 9], the bread of size 7 holds 7 units of cheese and 2 units overflow onto bread of size 11 which is already holding 9 units of cheese and can hold only 2 more units. Hence no cheese falls.
Intuition:
Initially, the capacity of a bread to hold cheese and it’s size is the same. But this changes as soon as some cheese falls on the bread, therefore it is wise to maintain capacity of the breads in a separate array. After this, for each layer of cheese, starting from the top of the sandwich (elements on the right side of the array), we find the closest bread, drop all the cheese on it. If any overflows, we search for the next closest bread, but this time, the bread has to be larger in size than the previous bread. If no bread satisfies the condition, we break and display that cheese falls off the sandwich, else we go back and find the next layer of cheese and repeat this operations until no cheese layers are left.
Approach:
We maintain two arrays, one storing the original values of bread and cheese given in input, and another array storing the capacity of each bread. We update the capacity adjacent breads with no cheese between them as soon as we encounter them in input.
Next we enter a while loop searching the first slice of cheese then checking if it falls off the sandwich or stays. We repeat these steps until we find a slice of cheese which falls off the sandwich.
If we do not find one, we display “No” as output else we display “Yes” as output.
Setter's Solution (C++)
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tc;cin>>tc;
while(tc--)
{
int m;cin>>m;int ans=1;ll zero=0;
ll arr[m]; ll capacity[m];
for(int j=0;j<m;j++)
{
cin>>arr[j];
capacity[j]=arr[j];
if(arr[j]%3!=0)
{
if(j>0&&arr[j-1]%3!=0)
capacity[j-1]=max(capacity[j-1]-capacity[j],zero);//Reducing the capacity of the breads which overlap
}
}
int i=m-1; int limiting_area=0; ll cheesefalling=0;
while(i)//Starting from the top of the sandwich
{
if(arr[i]%3==0)//Searching for a cheese layer
{cheesefalling=capacity[i];
limiting_area=0;//Intitally the limiting area is 0
if(capacity[i]>0)
{capacity[i]=0;
for(int j=i-1;j>=0;j--)//Looping through the sandwhich till all the cheese falls on bread
{
if(arr[j]%3==0&&limiting_area==0&&capacity[j]!=0)//Adding the cheese layers which have no breads in between them
{
cheesefalling+=arr[j];
capacity[j]=0;
}
else if(arr[j]%3!=0&&limiting_area<arr[j]&&capacity[j]>0)
{ ll cap=capacity[j];
capacity[j]=max(capacity[j]-cheesefalling,zero);//updating the capacity
limiting_area=arr[j];// updating the limiting_area
cheesefalling=max(cheesefalling-cap,zero);
if(cheesefalling==0)//If cheese left is 0, go to the next layer of cheese
{i--;
break;}
}
}
if(cheesefalling>0)//if cheese left is non zero even after iterating through all the breads, answer is 0
{
ans=0;
break;
}
}
else
i--;
}
else
i--;
}
if(ans)
cout<<"No\n";
else
cout<<"Yes\n";
}
return 0;
}