WTRSORT - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

Author and Editorialist: Jay Sharma
Testers: Shubham Anand Jain, Aryan Choudhary

DIFFICULTY:

TIE-BREAKER

PREREQUISITES:

Heuristics

PROBLEM:

There are reagents of N different colours and you have M ml of each reagent. You also have N+2 test tubes of initial capacity M ml each. Initiall, all the reagents are shuffled and stored in the first N test tubes. Your task is to sort these reagents according to their colour in N different test tubes. To achieve this, you may perform two types of operations -

  1. Transfer 1 ml of reagent from the top of one test tube to other. This operation is only feasible if the reagents don’t react with each other. Two reagents of colours U and V react if D_{U,V}=-1. Otherwise, the cost of this operation is D_{U,V}.
  2. Increase the capacity of a test tube by 1 ml. The cost of this operation is C_P.

Additionally, before performing any operation, you are allowed to reverse the contents of some test tubes.

Your goal is to sort the reagents using at most 1048576 operations and at the same time, minimise the cost.

BASIC SOLUTIONS:

The simplest solution sufficient to get an AC is to use a greedy approach - In each operation, find two test tubes which have the same colour at the top and transfer 1 ml of reagent from one to another. If there is no more space in the tube to which the reagent is to be transferred, increase its capacity. If there are no such test tubes, there will always be an empty test tube which can be used to transfer any reagent.

Proof

The proof follows from the Pigeonhole Principle. Suppose there are no two test tubes having the same colour at the top and no test tube is empty. Then there must be N+2 different colours at the top of test tubes which is not possible as there are reagents of N different colours only. Hence, either there will be at least two such test tubes or at least one test tube will be empty.

There is one more thing we need to take care of - oscillations, i.e., we need to make sure that we aren’t transferring the same 1 ml of reagent between two test tubes in consecutive moves otherwise this will lead to an endless loop. To handle this, we can fix the end tube for each colour dynamically. If a particular tube P contains reagent of one colour only and this colour hasn’t been assigned a tube yet, then
assign P as the end tube for that colour. While transferring reagents, if one of the tubes is an end tube, then transfer to that end tube only otherwise transfer to the tube with greater index.

It is not hard to see that after M^2 transfers, reagent of a particular colour will get sorted or in other words, a particular 1 ml of reagent will be transferred at most M times between tubes since reagents of that particular colour can appear in at most M different tubes. Also, the capacity of each tube will be increased at most M times since the top colour in the tube to which the reagent is transferred does not change. So, at most N\times M^2 transfers and N\times M tube expansions will be used. Thus, at most 139264 operations will be required which is around 8 times less than the limit. This solution incurs a cost of around 1.35\times 10^7 on the actual test data (including all the 16 test files) which was worth 0.95 points in Division 1.

Some randomness can be added to this solution by randomly reversing some of the test tubes in the beginning and by randomly choosing which colour to be transferred to the empty test tubes. These solutions incur nearly the same cost as the previous one. One possible improvement is to try multiple random trials as long as the time limit permits and choose the best one among them. This incurs nearly half the cost compared to the above solutions.

PARTICIPANTS’ SOLUTIONS:

Busa Máté’s (@busamate) Solution -

The solution was greedy and used 5 types of operations in the following order of preference -

  1. Pour reagents to their final tube.
  2. Pour reagents of same colour over each other.
  3. Pour reagents to empty tubes - For each colour, the total volume of this colour appearing at the top of test tubes is calculated and the colour with the maximum volume is poured to the empty test tube.
  4. Pour reagents of different colours over each other - The pairs of colours of minimum cost which can be poured over each other is chosen and one of them is poured over other. This operation is performed only if it’s cost is less than some threshold which was a parameter.
  5. Increase the capacity of a test tube. If it is beneficial to increase the capacity of a test tube, then such a test tube with the minimum C_P is chosen and it’s capacity is increased by 1 ml. This operation is also performed if its cost is less than a threshold which was another parameter.

Finally, if any of these operations is not performed, the threshold is increased.

This solution incured a total cost of 2.6\times 10^5 over all the test files which was the 3^{rd} best in Division 1.

Utkarsh Gupta’s (@demoralizer) Solution -

This solution made an attempt to increase the capacity of the tubes with lower cost rather than those with higher cost by transferring reagents to different test tubes even if they contain different coloured reagent at its top. Since the cost of pouring reagents of different colours over each other was much less than the cost of increasing capacity of tubes, this proves to be an efficient optimisation.

This solution incured a total cost of about 7\times 10^5 which was the 5^{th} best in Division 1.

Pranav Rajagopalan’s (@explodingfrz) Solution -

This solution was similar to the basic solution but used a lot of optimisations -

  1. If the amount of reagent of the same colour at the bottom of a tube is greater than that at the top of the tube then reverse the tube.
  2. While pouring reagents to empty tubes, pour the reagent with the maximum volume over the top of all tubes.
  3. Instead of directly increasing the capacity of a tube, consider all the tubes. Suppose we want to pour K ml of reagent of colour U from P to a particular tube PQ, whose colour at the top was V. Then the cost of pouring will be D_{U,V}+C_P\times total capacity to be increased of tube Q to accomodate all the K ml of reagent in tube P. Choose the tube Q with minimum such cost.

This solution incurs a total cost of around 9\times 10^5 over all the test files which was the 6-th best in Division 1. It was also the first solve for the problem!

SOLUTIONS:

Setter's Solution
//Problem - Water Sort Puzle
//Author - Jay Sharma (jay_1048576)
//Basic Solution
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin >> n >> m;
    int c[n+2];
    for(int i=0;i<n+2;i++)
        cin >> c[i];
    int d[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> d[i][j];
    int b[n][m];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin >> b[i][j];
            b[i][j]--;
        }
    }
    vector<int> emptytesttubes;
    emptytesttubes.push_back(n);
    emptytesttubes.push_back(n+1);
    int finaltube[n];
    for(int i=0;i<n;i++)
        finaltube[i]=-1;
    vector<int> tubes[n+2];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            tubes[i].push_back(b[i][j]);
    int capacity[n+2];
    for(int i=0;i<n+2;i++)
        capacity[i]=m;
    vector<pair<int,pair<int,int> > > ans; 
    while(true)
    {
        if(emptytesttubes.size()>0)
        {
            int q=emptytesttubes.back();
            emptytesttubes.pop_back();
            int p;
            bool found=false;
            for(int i=0;i<n+2;i++)
            {
                if(tubes[i].size()>0&&finaltube[tubes[i].back()]==-1)
                {
                    p=i;
                    found=true;
                    break;
                }
            }
            if(!found)
                break;
            int u=tubes[p].back();
            tubes[p].pop_back();
            tubes[q].push_back(u);
            finaltube[u]=q;
            ans.push_back({1,{p,q}});
            if(tubes[p].size()==0)
                emptytesttubes.push_back(p);
        }
        else
        {
            vector<int> ends[n];
            for(int i=0;i<n+2;i++)
            {
                ends[tubes[i].back()].push_back(i);
            }
            bool found=false;
            int u;
            for(int i=0;i<n;i++)
            {
                if(ends[i].size()>1)
                {
                    if(finaltube[i]!=-1)
                    {
                        if(tubes[finaltube[i]].size()<capacity[finaltube[i]])
                        {
                            found=true;
                            u=i;
                            break;
                        }
                    }
                    else
                    {
                        int q=ends[i].back();
                        if(tubes[q].size()<capacity[q])
                        {
                            found=true;
                            u=i;
                            break;
                        }
                    }
                }
            }
            if(!found)
            {
                for(int i=0;i<n;i++)
                {
                    if(ends[i].size()>1)
                    {
                        found=true;
                        u=i;
                        break;
                    }
                }
            }
            if(!found)
                break;
            if(finaltube[u]==-1)
            {
                int q=ends[u].back();
                ends[u].pop_back();
                int p=ends[u].back();
                tubes[p].pop_back();
                tubes[q].push_back(u);
                if(tubes[q].size()>capacity[q])
                {
                    capacity[q]++;
                    ans.push_back({2,{q,0}});
                }
                ans.push_back({1,{p,q}});
                if(tubes[p].size()==0)
                    emptytesttubes.push_back(p);
                else
                {
                    int u=tubes[p][0];
                    if(finaltube[u]!=-1)
                        continue;
                    bool single=true;
                    for(int i=1;i<tubes[p].size();i++)
                    {
                        if(tubes[p][i]!=u)
                            single=false;
                    }
                    if(single)
                        finaltube[u]=p;
                }
            }
            else
            {
                int q=finaltube[u];
                int p;
                while(true)
                {
                    p=ends[u].back();
                    ends[u].pop_back();
                    if(p==q)
                        continue;
                    break;
                }
                tubes[p].pop_back();
                tubes[q].push_back(u);
                ans.push_back({1,{p,q}});
                if(tubes[p].size()==0)
                    emptytesttubes.push_back(p);
                else
                {
                    int u=tubes[p][0];
                    if(finaltube[u]!=-1)
                        continue;
                    bool single=true;
                    for(int i=1;i<tubes[p].size();i++)
                    {
                        if(tubes[p][i]!=u)
                            single=false;
                    }
                    if(single)
                        finaltube[u]=p;
                }
            }
        }
    }
    for(int i=0;i<n+2;i++)
    {
        while(tubes[i].size()>0)
        {
            if(finaltube[tubes[i].back()]==i)
                break;
            else
            {
                int u=tubes[i].back();
                int q=finaltube[u];
                tubes[q].push_back(u);
                tubes[i].pop_back();
                ans.push_back({1,{i,q}});
            }
        }
    }
    cout << 0 << " " << ans.size() << '\n';
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i].first==1)
            cout << 1 << " " << ans[i].second.first+1 << " " << ans[i].second.second+1 << '\n';
        else
            cout << 2 << " " << ans[i].second.first+1 << "\n";
    }
    return 0;
}
Tester's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define rforn(i,s) for(int i=s;i>=0;--i)
#define rforsn(i,s,e) for(int i=s;i>=e;--i)
#define bitcount(a) __builtin_popcount(a) // set bits (add ll)
#define ln '\n'
#define getcurrtime() cerr<<"Time = "<<((double)clock()/CLOCKS_PER_SEC)<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inputfile freopen("input.txt", "r", stdin)
#define outputfile freopen("output.txt", "w", stdout)
#define dbg(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cerr<<endl; }
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << "\t"; err(++it, args...);
}
template<typename T1,typename T2>
ostream& operator <<(ostream& c,pair<T1,T2> &v){
	c<<"("<<v.fi<<","<<v.se<<")"; return c;
}
template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& out,TT<T...>& c){
    out<<"{ ";
    forstl(x,c) out<<x<<" ";
    out<<"}"; return out;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef pair<int,p32> p96;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<p64> vp64;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM=2e5+5,MOD=1e9+7;
const ld EPS = 1e-9;
 
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
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 main(){
	fastio;
 
	int n, m;
	// cin>>n>>m;
	n = readIntSp(512, 512);
	m = readIntLn(16, 16);
	ll c[n+2];
	ll cap[n+2];
	forn(i,n+2){
		cap[i] = m;
		// cin>>c[i];
		if(i<n+1) c[i] = readIntSp(1,1'000);
		else c[i] = readIntLn(1,1'000);
	}
	ll d[n][n];
	forn(i,n){
		forn(j,n){
			// cin>>d[i][j];
			if(j<n-1) d[i][j] = readIntSp(-1,100);
			else d[i][j] = readIntLn(-1,100);
		}
	}
	forn(i,n){
		assert(d[i][i] == 0);
		forn(j,n){
			assert(d[i][j] == d[j][i]);
		}
	}
	stack<int> tt[n+2];
	int cnt[n] = {0};
 
	ll inp[n][m];
 
	forn(i,n){
		forn(j,m){
			int x;
			// cin>>x;
			if(j < m-1) x = readIntSp(1,n);
			else x = readIntLn(1,n);
			x--;
			cnt[x]++;
			inp[i][j] = x;
		}
	}
 
	forn(i,n) assert(cnt[i] == m);
 
	ll mx_score = 1e18;
	vector<v32> fin_ans;
	v32 fin_flip;
 
	int num_tt = 11;
 
	forn(l,1<<num_tt){
		priority_queue<pair<int,int>> empty;
		ll score = 0;
		vector<v32> ans;
		v32 flip;
 
		forn(i,n+2){
			while(tt[i].size() > 0) tt[i].pop();
		}
		forn(i,n+2){
			cap[i] = m;
		}
 
		forn(i,n){
			if(rng() % 2){
				flip.pb(i+1);
				rforn(j,m-1){
					tt[i].push(inp[i][j]);
				}
			}
			else{
				forn(j,m){
					tt[i].push(inp[i][j]);
				}
			}
		}
 
		empty.push(mp(-c[n],n));
		empty.push(mp(-c[n+1],n+1));
 
		vp32 ord;
		forn(i,n){
			ord.pb(mp(c[i], i));
		}
		sort(all(ord));
 
		int fill[n] = {0};
		forn(i,n) fill[i] = -1;
 
		forstl(r,ord){
			// cout<<"doing "<<r<<ln;
			int id = r.se;
			while(!tt[id].empty()){
				auto t = tt[id].top();
				if(fill[t] == -1 && empty.size() > 0 && (-empty.top().fi) <= 1.2*c[id]){
					auto k = empty.top();
					empty.pop();
					fill[t] = k.se;
				}
				if(fill[t] == -1) break;
				int new_tt = fill[t];
				if(tt[new_tt].size() == cap[new_tt]){
					v32 op;
					op.pb(2);
					op.pb(new_tt+1);
					ans.pb(op);
					cap[new_tt]++;
					score += c[new_tt];
				}
				tt[new_tt].push(t);
				tt[id].pop();
				v32 op;
				op.pb(1);
				op.pb(id+1);
				op.pb(new_tt+1);
				// cout<<id+1<<" "<<" to new testtube "<<new_tt+1<<endl;
				ans.pb(op);
			}
			if(tt[id].empty()){
				empty.push(mp(-c[id],id));
			}	
			else{
				auto t = tt[id].top();
				assert(fill[t] == -1);
				fill[t] = id;
			}
		}
 
		forn(i,n){
			if(fill[i] == -1){
				assert(empty.size() > 0);
				auto k = empty.top();
				empty.pop();
				fill[i] = k.se;
			}
		}
 
		// cout<<"OK"<<endl;
 
		int final[n] = {0};
		forn(i,n) final[i] = -1;
		vp32 rev_ord;
		forn(i,n+2){
			rev_ord.pb(mp(c[i], i));
		}
		sort(all(rev_ord), greater<p32>());
 
		int rev_fill[n+2] = {0};
		forn(i,n+2) rev_fill[i] = -1;
		forn(i,n){
			int x = fill[i];
			// cerr<<i<<" "<<fill[i]<<endl;
			assert(x!=-1);
			rev_fill[x] = i;
		}
 
		// cout<<"OK"<<endl;
 
		forstl(r,rev_ord){
			int id = r.se;
			int aa = rev_fill[id];
			if(aa!=-1){
				fill[aa] = -1;
			}
			while(!tt[id].empty()){
				auto t = tt[id].top();
				tt[id].pop();
				if(fill[t] == -1 && final[t] == -1){
					assert(empty.size()>0);
					auto k = empty.top();
					empty.pop();
					final[t] = k.se;
				}
				assert((final[t] != -1) || (fill[t] != -1));
				int new_tt = final[t];
				if(final[t] == -1) new_tt = fill[t];
				// cout<<id+1<<" "<<" to new testtube "<<new_tt+1<<endl;
				if(tt[new_tt].size() == cap[new_tt]){
					v32 op;
					op.pb(2);
					op.pb(new_tt+1);
					ans.pb(op);
					cap[new_tt]++;
					score += c[new_tt];
				}
				tt[new_tt].push(t);
				v32 op;
				op.pb(1);
				op.pb(id+1);
				op.pb(new_tt+1);
				ans.pb(op);
			}
			// cout<<"DONE"<<endl;
			assert(tt[id].empty() == 1);
			empty.push(mp(-c[id], id));
		}
 
		cerr<<l<<" "<<score<<endl;
 
		if(score < mx_score){
			mx_score = score;
			swap(fin_ans, ans);
			swap(fin_flip, flip);
		}
 
	}
 
 
 
	// forn(i,n){
	// 	cout<<"final "<<1+i<<" "<<1+final[i]<<endl;
	// }
 
	cerr<<mx_score<<ln;
	cout<<fin_flip.size()<<" "<<fin_ans.size()<<ln;
	forstl(r,fin_flip) cout<<r<<" ";
	cout<<ln;
	forstl(r,fin_ans){
		forstl(k,r) cout<<k<<" ";
		cout<<ln;
	}
 
	return 0;
}

Solution by busamate
Solution by demoralizer
Solution by explodingfrz

2 Likes

I would like to clarify that my solution DOES NOT use simulated annealing. I thought of doing something like that but never actually did it. (The author thinks I used SA because I wrote it on top of my code in a comment, which was just a reminder to myself that I can try this)

The basic idea of my solution was - try to increase only the cheapest test tubes. You can check out the video on my youtube channel for a more detailed explanation if interested.

1 Like

Oops. Sorry about that. You are right. I saw that comment of yours about Simulated Annealing and saw that you are using multiple trials saving the best answer. So, I thought that it must be SA.

1 Like