STICKS2 - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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 :slight_smile:
  • 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 :slight_smile:

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 :slight_smile:

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) :slight_smile:

Setter

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

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 :smiley:

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 :slight_smile:

3 Likes
Please look only after giving a good attempt!! Thanks.

Reason for my WA.:wink:

1 Like

Hahahahaha xD

kept on solving using the 1st algo of Chef’s corner in competition and in practice. Feeling dumb after seeing the spoiler :stuck_out_tongue:

1 Like

Dont feel dumb dear. Many pro coders did same thing as well XD. The important thing was, coming up with a counter case. I hope you had a nice time solving the problem and hope you found the editorial useful :slight_smile:

PS: Fun fact- I predicted that many contestants will follow Algo 1, and hence gave answer for it. Feeling like…XDXD

I am looking forward for debate on Q2. of my corner. Com’mon @all , should we tag this greedy as well? XD

Nice one! I’d also stuck at approach 1 for much time. Actually I’m thinking in terms of “variables” instead of “number figures” and got stuck to the conclusion that “If by any mean we select the next greater element than we are only making the situation worse as we have already selected a stick of that length and hence now it can be used”. I can’t come on the counter case till last :(. Thanks a lot again :slight_smile:

And if you have some similar problems like this then please plz share!

Couldnt find many related problems this time for many questions this time. They were kind of unique in intuition. I will see if I come across any in future :slight_smile:

The quality of the editorials for this Cook-Off is really great ! Good to see this improvement. Great job done by the editorialist.

2 Likes

It was a huge race against time though. Glad to see its appreciated :slight_smile:

Can someone find the mistake in my code, I have commented the code well so that it could be understood easily.

I did it with another approach which I would like to share.

Consider two arrays A[] and cnt[]. A[] stores all the distinct elements and cnt[A[i]] stores the frequency of A[i].First I will check can I select K elements such that any rectangle cannot be formed.Let d be the number of distinct elements so if d>=k-1 or k<4 or (there exists atleast one element in A[] whose frequency is >=3 and d>=k-1), the answer will be -1.

For the third case consider this eg,

10 7 
1 5 4 5 4 4 2 3 4 1   

Now I will consider each 1<=i<=n and assume A[i] is the length of two of the sides of the rectangle formed.To be more specific the smaller one (if 2 and 4 are the length using which rectangle is formed then A[i]=2). First of all, cnt[A[i]]>=2 then only I will be able to take atleast two sticks of length A[i] to form a rectangle.Now we have to select two more sticks that will form remaining two sides of the rectangle. The new stick should have length between A[i]+1 to MAX[A[i]] because I have already considered A[i] to be the smaller of the two lengths.Let us call this new length A[j].Now the question is what is the minimum cnt[A[j]] that will allow me to take A[i] and A[j] as two sides of the rectangle? I can take any number of sticks whose length is smaller than A[i] because chef’s brother will always choose A[i] length sticks over smaller length sticks to maximize the area. I can select all the elements greater than A[i] once because if there is a stick whose length is greater than A[i] but frequency is 1 then it can’t be used to make a rectangle.So the equation will be cnt[A[j]]>=K-cnt[a[i]-prev-d+1. Here prev is the sum of frequency of all sticks whose length is greater than A[i] and d is the number of distinct elements greater than A[i]. ‘+1’ because I have calculated A[j] in d (Since A[j]>A[i) as well as in cnt[A[j]].

This can be implemented using a segment tree with coordinate compressions.You can see my code:https://www.codechef.com/viewsolution/19363521.

Sorry If the explanation is not clear enough I have tried my best to explain my approach.

1 Like