PROBLEM LINK:
Setter- Hasan Jaddouh
Tester- Ivan Safonov
Editorialist- Abhishek Pandey
DIFFICULTY:
Easy-Medium
PRE-REQUISITES:
Logical Reasoning, Implementation, Binary Search heuristics
PROBLEM:
Given N sticks, Chef has to given at least K sticks to his brother. Chef wants to minimize the area of rectangle formed by the sticks - and prevent rectangle from forming if possible. Now, Chef’s brother will optimally pick from given K sticks to maximize area of rectangle. What is the area of rectangle if both play optimally.
QUICK EXPLANATION:
Key to AC- Realize that its much, much easier to frame criteria to remove N-K sticks than to frame conditions to choose K sticks.
Get that choosing K sticks is same as removing N-K sticks. The logical idea of solution is, that its easier to frame criteria for removing sticks than criteria for choosing sticks. Also note that, since Chef has full control to choose the sticks to give, the area of rectangle is determined by only which sticks he chooses. His brother will then do best selection out of given option.
Now, keep a track of how many sticks of a given length are there. Now sort it in ascending order of stick length. Start from the stick with largest length and do following-
- If there are 4 or more sticks of current length (remember we start from largest length to smallest length!!), then we must remove these sticks to minimize answer. Keep only 3 sticks and go to next condition. 3 sticks ensures that rectangle isnt formed using only these sticks. If we cannot remove enough sticks, we got a candidate answer.
- If there are 3 sticks, first see what would be the area if we dont remove sticks of this kind and instead try to reduce the other dimension. (Eg- If our current sticks are \{9,9,9,8,8,1,1\} and we have to remove one stick, then removing 8 is better option as it reduces area to 9*1=1. Removing 9 is non-optimal this case). We can calculate the other dimension using Binary Search heuristics
- After executing above condition, lets check the other alternative if we remove sticks. Generalizing the condition, if we got >1 sticks, we remove all but one stick if we can. If we cannot remove enough sticks, then minimize the next dimension.
EXPLANATION:
The editorial is divided into 4 sections. The first section gives basic introduction of the situation and things to do before we start processing our conditions. Each of the next 3 sections are dedicated to each of the three conditions.
1. Initial Processing(s)-
The first thing to do is to keep a note of how many sticks of given length are there. You can use the map data structure for these purposes. Ultimately, we will need a sorted list of stick lengths and its frequencies. (Note that frequency is also sorted by stick length. You might use pairs data type or make a custom one yourself).
We will be using Binary Search heuristics later on to determine next dimension of rectangle. For this, we will be working on frequency of sticks. Hence, a prefix sum of frequency array is needed as well.
Lets now check if answer is -1. Using above pre-processing, find number of sticks to remove if we are to remove all but 1 stick of each length (i.e., if there are >1 sticks of that length, keep only 1 stick and remove rest). If we can remove enough sticks to get such a configuration, then rectangle cannot be formed. Note that, it is OK if stick of only one of the lengths (say L_i) is such that 3\ge freq_i \ge 1. A rectangle couldn’t be formed even then - this is the only catch in this simple condition.
If a rectangle is possible, then lets start with our guidelines on eliminating sticks :). For each of the three guidelines below, please remember that we sorted the sticks on basis of length, and are iterating from stick of largest length to smallest length.
2. When \ge 4 sticks of current length are available-
Since we are starting from sticks of largest length, then if there are 4 or more sticks of current length, then they themselves will form rectangle of maximum area. Chef wants to minimize it! Hence, he will tend to remove sticks so that a rectangle cannot be formed by it!
Removing all but 3 sticks is enough to make sure that a rectangle isnt formed using only these sticks. Its enough to do only this much for now and proceed to next condition - because any further processing needed for this condition, and the working of next condition are exactly same.
Can you think on how we will implement this idea? The idea and conditions are simple, and given in tab for reference.
Click to view
if(arr[i].second > 3){ // if we leave more than 3 sticks of currently tallest stick then answer is //immediately arr[i].first * 1ll *arr[i].first
if(arr[i].second - 3 > k){//If we cannot remove enough sticks
ans = min(ans, arr[i].first * 1ll *arr[i].first);
break;
}
k -= arr[i].second - 3;//else remove those many sticks.
arr[i].second= 3;
}
3. If there are exactly 3 sticks of current length-
The catch in this condition is that, we need to remove 2 sticks of current length to prevent it from being used in rectangle - what if we use those 2 removals to lower the other dimension? Also, we continue processing of above condition here as well.
Hence, what we will do here, to see what area we will get if we choose to keep stick of current length and minimize other dimension. This can be achieved in O(LogN) by Binary Search heuristics. Remember the prefix sum of frequency array we found earlier. We will use that.
The idea of Binary Search heuristics is, to check “What will be the other dimension, if we keep removing all but 1 sticks for future sticks till we can.”. In other words, for sticks of length < CurrentLength, remove all sticks except 1 (as the stick cannot be used in rectangle if only 1 stick of that length is available). Do this till we can. Check at which length we stopped. That length is the other dimension.
Can you use this idea and try to come up with an implementation for this? Its given in tab for clearer understanding
Click to view
if(arr[i].second == 3){ // if there are 3 sticks we don't know whether we should remove 2 sticks or
//not, sometimes first option is optimal sometimes second
int l=1,r=i; // so if we decided to leave 3 sticks then Chef's brother clear
//will take 2 of them for first dimension of rectangle
while(r-l>1){ // now we have to minimize the second dimension
int mid=(r+l)/2;
if(sm[i-1] - sm[mid-1] - (i-mid) > k){//If we can remove all sticks
//except 1 for all lengths from [mid,i-1]
l=mid;
} else {
r=mid;
}
}
//arr[l].first is the dimension where we stopped.
ans = min(ans,arr[i].first * 1ll * arr[l].first);
}
Note that, in this condition, we did not remove any stick. We merely checked the other dimension if current length stick is to be kept. We now proceed to the next condition.
4. If >1 sticks of current length are there-
Now, we already checked area if we kept the stick of current length. Whats left? Yes, what if we remove it :).
The only task done in this condition is to check if we can remove enough sticks so that stick of current length cannot be used in rectangle (i.e. remove all but 1 stick of current length).
In case we cannot do that, we again minimize the next dimension.
There is an interesting observation to note here. It is *necessary for this step to remove sticks of current length if they are more than 1 - thats because of what you’d have noticed by a careful reading - We are intrinsically assuming that stick of current length is the largest available stick usable in rectangle. The next dimension is searched from sticks of length shorter than current length. It is very necessary for correctness of algorithm that sticks of length greater than current length cannot be used in rectangle. Kind of obvious, but I just wanted to highlight how to read between words and focus on intrinsic assumptions. Thats the first step to develop intuition
Based on above, we can draw an interesting conclusion. If we cannot remove a stick in this step, then we can no further remove sticks. Obviously, then we have already found the optimal answer at this step or by now, as Chef’s brother will pick this largest current length and next possible largest dimension.
Try implementing this idea. You may not need to use Binary Heuristics here, linear will do as after this step we break out of loop citing we already found the answer.
Click to view
if(arr[i].second > 1){ // if there are more than 1 stick we have to take them
if(arr[i].second - 1 > k){ // if we can't take them then we minimize the second dimension
for(int j=i-1;j>=1;j--){
if(arr[j].second - 1 > k){
ans = min (ans, arr[j].first * 1ll * arr[i].first);
break;
}
k -= arr[j].second - 1;
}
break;
}
k -= arr[i].second - 1; // if we can take them we try this option
arr[i].second = 1;
}
SOLUTION:
I have pasted the codes in tabs for your convenience - in case the links dont work. Please enjoy that while @admin fixes links in back ground (if they are broken at all xD)
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
#include <map>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,k;
int sm_n=0;
map<int,int> mp;
int h;
pair<int,int> arr[100100];
int sm[100100];
int m;
map<int,int>::iterator ii;
int main(){
T=readIntLn(1,100);
while(T--){
mp.clear();
n=readIntSp(1,100000);
sm_n += n;
assert(sm_n<=100000);
k=readIntLn(0,n);
k=n-k; // instead of selecting K sticks, we remove n-k sticks
for(int i=0;i<n-1;i++){
h=readIntSp(1,1000000000);
mp[h]++; // keep frequencies of sticks in a map
}
h=readIntLn(1,1000000000);
mp[h]++;
m=1;
for(ii=mp.begin();ii!=mp.end();ii++){
if(ii->second > 1){
arr[m++] = *ii;
}
}
m--;
int req=0;
int mxx=0;
for(int i=1;i<=m;i++){
sm[i] = sm[i-1] + arr[i].second; // prefix sum of frequencies, we gonna need that
if(arr[i].second > 1){
req += arr[i].second -1;
mxx = max ( arr[i].second -1,mxx);
}
}
if (req -min(mxx,2)<= k){ // condition to tell if we can prevent having any rectangle
cout<<-1<<endl;
continue;
}
long long ans=1ll<<60;
for(int i=m;i>=1;i--){ // go through sticks from tallest to smallest
if(arr[i].second > 3){ // if we leave more than 3 sticks of currently tallest stick then answer is immediately arr[i].first * 1ll *arr[i].first
if(arr[i].second - 3 > k){
ans = min(ans, arr[i].first * 1ll *arr[i].first);
break;
}
k -= arr[i].second - 3;
arr[i].second= 3;
}
if(arr[i].second == 3){ // if there are 3 sticks we don't know whether we should remove 2 sticks or not, sometimes first option is optimal sometimes second
int l=1,r=i; // so if we decided to leave 3 sticks then Chef's brother clear will take 2 of them for first dimension of rectangle
while(r-l>1){ // now we have to minimize the second dimension
int mid=(r+l)/2;
if(sm[i-1] - sm[mid-1] - (i-mid) > k){
l=mid;
} else {
r=mid;
}
}
ans = min(ans,arr[i].first * 1ll * arr[l].first);
}
if(arr[i].second > 1){ // if there are more than 1 stick we have to take them
if(arr[i].second - 1 > k){ // if we can't take them then we minimize the second dimension
for(int j=i-1;j>=1;j--){
if(arr[j].second - 1 > k){
ans = min (ans, arr[j].first * 1ll * arr[i].first);
break;
}
k -= arr[j].second - 1;
}
break;
}
k -= arr[i].second - 1; // if we can take them we try this option
arr[i].second = 1;
}
}
cout<<ans<<endl;
}
assert(getchar()==-1);
}
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
#include <map>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,k;
int sm_n=0;
map<int,int> mp;
int h;
pair<int,int> arr[100100];
int sm[100100];
int m;
map<int,int>::iterator ii;
int main(){
T=readIntLn(1,100);
while(T--){
mp.clear();
n=readIntSp(1,100000);
sm_n += n;
assert(sm_n<=100000);
k=readIntLn(0,n);
k=n-k; // instead of selecting K sticks, we remove n-k sticks
for(int i=0;i<n-1;i++){
h=readIntSp(1,1000000000);
mp[h]++; // keep frequencies of sticks in a map
}
h=readIntLn(1,1000000000);
mp[h]++;
m=1;
for(ii=mp.begin();ii!=mp.end();ii++){
if(ii->second > 1){
arr[m++] = *ii;
}
}
m--;
int req=0;
int mxx=0;
for(int i=1;i<=m;i++){
sm[i] = sm[i-1] + arr[i].second; // prefix sum of frequencies, we gonna need that
if(arr[i].second > 1){
req += arr[i].second -1;
mxx = max ( arr[i].second -1,mxx);
}
}
if (req -min(mxx,2)<= k){ // condition to tell if we can prevent having any rectangle
cout<<-1<<endl;
continue;
}
long long ans=1ll<<60;
for(int i=m;i>=1;i--){ // go through sticks from tallest to smallest
if(arr[i].second > 3){ // if we leave more than 3 sticks of currently tallest stick then answer is immediately arr[i].first * 1ll *arr[i].first
if(arr[i].second - 3 > k){
ans = min(ans, arr[i].first * 1ll *arr[i].first);
break;
}
k -= arr[i].second - 3;
arr[i].second= 3;
}
if(arr[i].second == 3){ // if there are 3 sticks we don't know whether we should remove 2 sticks or not, sometimes first option is optimal sometimes second
int l=1,r=i; // so if we decided to leave 3 sticks then Chef's brother clear will take 2 of them for first dimension of rectangle
while(r-l>1){ // now we have to minimize the second dimension
int mid=(r+l)/2;
if(sm[i-1] - sm[mid-1] - (i-mid) > k){
l=mid;
} else {
r=mid;
}
}
ans = min(ans,arr[i].first * 1ll * arr[l].first);
}
if(arr[i].second > 1){ // if there are more than 1 stick we have to take them
if(arr[i].second - 1 > k){ // if we can't take them then we minimize the second dimension
for(int j=i-1;j>=1;j--){
if(arr[j].second - 1 > k){
ans = min (ans, arr[j].first * 1ll * arr[i].first);
break;
}
k -= arr[j].second - 1;
}
break;
}
k -= arr[i].second - 1; // if we can take them we try this option
arr[i].second = 1;
}
}
cout<<ans<<endl;
}
assert(getchar()==-1);
}
Tester
Time Complexity- O(NLogN)
CHEF VIJJU’S CORNER 
1. One of the key factors of this question is, how easy it is to frame a criteria to remove sticks than to make a criteria to pick K sticks. But lets have some fun this side too? :). So, warm-up your brains, and judge these-
For EACH of the given algorithms, either prove why they are correct or provide a counter case.
a. To pick K sticks, we use a frequency based approach. First give 1 of each stick. Then, start from smallest stick and give as many as possible. Then next larger stick and as many as possible. Keep going on until K sticks are given.
b. Follow these steps-
- If K<4 \implies Ans=-1.
- Check if there are more than K-1 distinct elements. Eg- If K=4 and there are 3 distinct elements, say, \{1,2,2,3\}, Chef can make it possible for no rectangle to be formed. Ans = -1.
- Sort the array. Give first K elements (As now rectangle is always possible if above 2 dont hold.)
- Use map etc. to see which elements have count >2 . Alternatively, since we sorted, we can check for adjacent element$>1$ . Add these elements separately to a vector and take 2 largest of them to form rectangle. Beware of overflows.
Answer for first algorithm-
Click to view
Please look only after giving a good attempt!!
Click to view
Counter case-
Sticks=[9,9,9,7,7,8,8,1,1]
You can remove only 2 sticks. That algorithm will give [1,1,7,7,8,8,9] while its optimal if we give [1,1,7,8,9,9,9]
2. Argue “Greedy” tag for this question. Is this greedy? Is this greedy + condition? Or is it actually dynamic programming but we found an optimal way and hence proceeded to simply simulate it? THAT, is for YOU to decide
