PROBLEM LINK:
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;
}
