BASKETS - Editorial

PROBLEM LINK

Contest

Setter : Utkarsh Gupta
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

PREREQUISITES

Observation

DIFFICULTY

Easy - Medium

PROBLEM

Chef wants to run a restaurant for N days (numbered 1 through N).

First, Chef needs to buy some plates. Each of these plates should have a positive integer capacity. Chef must decide in advance the number of plates M to buy as well as their capacities (not necessarily the same for each plate). A plate with capacity c cannot hold more than c fruits and it is called half-full if it holds at least ceil(c/2) fruits. Initially, all plates are empty and numbered 1 through M.

Chef needs to satisfy his guests on each of the N days. For each day i:

  • On the morning of this day, Chef unlocks an infinite supply of fruit of the i-th type. He may use these fruits any number of times during the i-th day and all days that follow.
  • In the afternoon, he may choose up to 4 fruits and add them to some of the plates. The fruits may be of any types (possibly the same type) and they may be added to any plates independently from each other (possibly all to the same plate). For example, if this is the 5-th day and Chef has 3 plates, he may choose fruits of types \{1, 1, 3, 4\}, add fruits of types 1 and 4 to the second plate and fruits of types 1 and 3 to the third plate.
  • By the evening of this day, he must present a single plate containing at least one of each type of fruit between 1 and i inclusive. Additionally, the plate must be at least half-full, otherwise it would look empty and his guests would not be satisfied.

Note that the same plate may be presented multiple times. When a plate is presented, the fruits on it remain (do not get eaten).

Help Chef decide the number of plates, the capacity of each plate, as well as the types of fruits to pick each day and the plates to add them to. Chef does not need to minimise the number of plates or their capacities, but the number of plates must not exceed 1,000 and their capacities must not exceed N. You may find any valid solution. It is guaranteed that under the given constraints, a solution always exists.

Constraints

  • 1 \le T \le 1,000
  • 1 \le N \le 10^5
  • the sum of N over all test cases does not exceed 10^5

EXPLANATION

Intuition 1

The sizes of the plates should be in increasing order, plates with equal sizes don’t make a lot of sense

Intuition 2

There is a lot of $2$’s everywhere, especially the half filled criteria. Is that important?

Intuition 3

It also kindof makes sense that when a new item comes, we put one occurence of that in the previously half-filled plate, and spend rest of our chosen items on rebuilding a new plate.

Failed Attempt?

We cannot have plates with capacities like 1, 2, 3, 4, 5, …. so on, it doesn’t feel right (?!). A way to argue about it is this series grows at O(n^2) whereas we only have 4N maximum fruits, so there will be a huge deficit at the end.

Final Solution

As with most other adhoc solutions, there isn’t really much to build up on for this except intuition 2. Let’s make the size of the i^{th} plate 2^i. Then, when we get a new item j, we put one occurence of j on the current half-filled plate, and put 2 other items on the next plate (which we will essentially rebuild). Notice why this works. Say some plate is half filled, that is, it has \frac{2^j}{2} items. Now for the next \frac{2^j}{2} items, we put it in plate j.But, in every turn we put 2 items in the {j+1}^{th} plate. This is obviously valid because we are just selecting 1+2 < 4 items. All this time, the “chosen” plate is essentially plate j. By the time the j^{th} plate is filled, we will have put 2*\frac{2^j}{2} items in the {j+1}^{th} plate, so it will have \frac{2^{j+1}}{2} items, which is essentially like an induction step, and we are at the same position as before.

SOLUTION

Tester’s Code
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
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){
			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 baskets[17];
int suss=0;
vector<pair<int,pii>> avl[100005];
void solve() {
//	int n=readIntLn(1,100000);
	int n;
	cin>>n;
	suss+=n;
	assert(suss<=100000);
	cout<<16<<endl;
	fr(i,1,16)
		cout<<min(n,baskets[i])<<" \n"[i==16];
	fr(i,1,n)
		avl[i].clear();
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> pq;
	fr(j,1,16)
		fr(i,1,min(n,baskets[j]))
			avl[i].pb({max(i,baskets[j-1]+1),{i,j}});
	fr(i,1,n) {
		while(!avl[i].empty()) {
			pq.push(avl[i].back());
			avl[i].pop_back();
		}
		cout<<min(4LL,sz(pq))<<endl;
		for(int j=0; j<4&&sz(pq); j++) {
			cout<<pq.top().se.fi<<" "<<pq.top().se.se<<endl;
			pq.pop();
		}
	}
}
 
 
signed main() {
	baskets[1]=2;
	fr(i,2,16)
		baskets[i]=baskets[i-1]*2+2;
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
//	int t=readIntLn(1,1000);
	int t;
	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

VIDEO EDITORIAL: