UWCOI21C - Organisation - Editorial

PROBLEM LINK:

Contest
Practice

Author: Bumjun Kim
Tester: Smit Mandavia
Editorialist: Bumjun Kim

DIFFICULTY:

Easy

PREREQUISITES:

Constructive algorithms

PROBLEM:

There are T testcases. For each testcase, you are given the number of ducks for every color and you have to distribute the ducks into boxes such that there are at most 2 colors of ducks per box.

  • Subtask 1 [20 points]: 2 \leq N \leq 10, K=2
  • Subtask 2 [30 points]: N=2, K=5
  • Subtask 3 [50 points]: 2 \leq N \leq 10^5, 2 \leq K \leq 10^5

EXPLANATION:

Subtask 1:

For every box, you can try to select 2 different colors, and only if this is not possible, select the same color.

Subtask 2:

A 2^{NK} brute force solution can be used. Try all possible subsets for the first box and leave the remaining ducks for the second box. For every subset, you can check if the boxes match the size requirement and have at most 2 colors.

Subtask 3:

We can solve this problem using one simple observation. We can observe that by matching the color with least amount of ducks and the color with the most amount of ducks, we can reduce the number of different colors by 1 while only using 1 box. We can repeat this step n-1 times to finally reach a point where there are only 2 colors and 1 box left.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define int long long
void find(){
    int n,k;
    int ss = 0;
	cin>>n>>k;
	int cnt[n+5];
	for(int i=0; i<=n; i++) cin>>cnt[i];
	set<pair<int,int> > s; //cnt, typ
	for(int i=0; i<=n; i++){
		s.insert({cnt[i],i});
		ss += cnt[i];
	}
	assert(ss==n*k);
	
	for(int i=0; i<n; i++){ //iterate thru boxes
		int x = (*s.begin()).first,ty1 = (*s.begin()).second;
		s.erase(s.begin());
		int diff = k-x;
		cout<<ty1<<' '<<x<<' ';
		
		auto it = s.end(); it--;
		int y = (*it).first,ty2=(*it).second;
		cout<<ty2<<' '<<diff<<'\n';
		y -= diff;
		s.erase(it); s.insert({y,ty2});
	}
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        find();
    }
} 
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
 
int main() 
{
    FIO;
    ll t,n,k,i,j;
    pair<ll,ll> p,p2;
    set<pair<ll,ll>> s;
    set<pair<ll,ll>> :: iterator it;
            
    cin >> t;
    while(t--){
        cin >> n >> k;
        for(i=0;i<=n;i++){
            cin >> j;
            s.insert({j,i});
        }
        
        while(s.size()){
            if(s.size()==1){
                p=*(s.begin());
                cout << p.second << " " << k << " 0 0\n";
                s.erase(p);
                if(p.first>k)
                    s.insert({p.first-k,p.second});
                else
                    return 0;
            }else{
                p=*(s.begin());
                it = s.end();
                it--;
                p2=*(it);
                
                cout << p.second << " " << p.first << " ";
                cout << p2.second << " " << k-p.first << "\n";
                s.erase(p);
                s.erase(p2);
                if(p2.first>k-p.first)
                    s.insert({p2.first-k+p.first,p2.second});
            }
        }
    }
    
	return 0;
}
7 Likes

Why a lot of people were getting run time error for the remaining 50 marks(I also got RE).
for ex- this c++ submission and my java sub. Can anyone please point out the reason. (I was thinking there might be some problem in input file some extra space/line somewhere)

1 Like

I got re on this
https://www.codechef.com/viewsolution/40547491
Can you provide a tc where this would give re?
Removing one condition from line 32 gives me AC ( https://www.codechef.com/viewsolution/40547534 ) but I don’t see any wrong even in the first submission.

1 Like

I copy-pasted the setter’s solution and it only passes the first two subtasks!
UPD: I didn’t notice #define int long long. Now it gets AC.

1 Like

i just changed my pair<int,int> to pair<lld,lld> and now i am getting correct answer how can it overflow?
MY correct submission- https://www.codechef.com/viewsolution/40554967

Code i submitted during contest-https://www.codechef.com/viewsolution/40546681

1 Like

Can someone please help why is the below code giving WA for the 1st and 3rd subtasks-

    cin>>n>>k;
  	fr(i,0,n)
  	{
  		cin>>x;
  		if(x>0)
  			vect.pb({x,i});
  	}
  	sort(all(vect));
  	int l=0,r=sz(vect)-1;
  	while(l<=r)
  	{
  		if(l<r)
  		{
  				cout<<vect[l].ss<<" "<<vect[l].ff<<" "<<vect[r].ss<<" "<<(k-vect[l].ff)<<endl;
  				vect[r].ff-=(k-vect[l].ff);
  				if(vect[r].ff==0)
  					r--;
  				l++;
  		}
  		else if(l==r)
  		{
  			fr(i,1,vect[l].ff/k)
  			{
  				int temp=((vect[l].ss==0)?1:0);
  				cout<<vect[l].ss<<" "<<k<<" "<<temp<<" "<<0<<endl;  			
  			}
  			break;
  		}
  	}

When you’re removing from last index…that values becomes less. Say for this next iteration sum of first and last doesn’t sums upto k, then you won’t be filling the box fully. So, if the sum becomes less than k append last to first.
You can see this part in my submission-

if new[0]+vals[0][0]<k:
	vals.appendleft(new)
else:
	vals.append(new)

Can you give some testcase. I checked that case but I found no testcase for it.

Because N*K could be up to 10^10. Consider a case where N= 10^5, K = 10^5 and there is only one color that contains all the ducks.

Like even if I consider some case like-
1
3 3
2 2 2 3
This condition never occurs. Can you please give one testcase :sweat_smile:

5 2
0 0 2 2 3 3

I hope now you get it.

Thanks a lot for the testcase :smile:
But i made a change and now it is giving WA on subtask 3 .

fr(i,0,n)
  	{
  		cin>>x;
  		if(x>0)
  			vect.pb({x,i});
  	}
  	sort(all(vect));
  	int l=0,r=sz(vect)-1;
  	while(l<=r)
  	{
  		if(l<r)
  		{
  				if(vect[l].ff>k)
  				{
  					int temp=((vect[l].ss==0)?1:0);
  					cout<<vect[l].ss<<" "<<k<<" "<<temp<<" "<<0<<endl; 
  					vect[l].ff-=k;
  					continue;
  				}
  				cout<<vect[l].ss<<" "<<vect[l].ff<<" "<<vect[r].ss<<" "<<(k-vect[l].ff)<<endl;
  				vect[r].ff-=(k-vect[l].ff);
  				if(vect[r].ff==0)
  					r--;
  				l++;
  		}
  		else if(l==r)
  		{
  			fr(i,1,vect[l].ff/k)
  			{
  				int temp=((vect[l].ss==0)?1:0);
  				cout<<vect[l].ss<<" "<<k<<" "<<temp<<" "<<0<<endl;  			
  			}
  			break;
  		}
  	}

I’ll check this in a while.

1 Like

It would still fail on that tc provided above.
Try printing vect[r].ff after subtraction. I think it would go negative.

Since you’re doing if(x>0) vect.pb({x,i}); while taking input it would work in this case but I doubt there’ll be cases when that value becomes negative.

1 Like

I did not get RE and also the I used the assert statement to verify it then I also I did not got any RE. If all the conditions were satisfied I don’t why it was giving wrong answer. I did like this only used a set to maintain the minimum one and maximum one .Please can anyone see my solution -
https://www.codechef.com/viewsolution/40553902

You are using int and not long long. That’s why maybe.

You are not using long long int

I will give you a test case soon. This will definitely not work.

Is this for me? I think so I did not paid attention to it as there were no constraints specified for the number of ducks for each color . What a pitty mistake

1 Like

Can some explain the logic for this problem?

https://www.codechef.com/viewsolution/40553954