$$$GCD(a,b)=GCD(a-b,b)$$$ if $$$a>b$$$

$$$a-b$$$ does not change by applying any operation. However, $$$b$$$ can be changed arbitrarily.

If $$$a=b$$$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times.

Otherwise, the maximum excitement the fans can get is $$$g=\lvert a-b\rvert$$$ and the minimum number of moves required to achieve it is $$$min(a\bmod g,g-a\bmod g)$$$.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        long long a,b;
        cin >> a >> b;
        if(a==b)
            cout << 0 << " " << 0 << '\n';
        else
        {
            long long g = abs(a-b);
            long long m = min(a%g,g-a%g);
            cout << g << " " << m << '\n';
        }
    }
}

In the optimal arrangement, the number of cars will be distributed as evenly as possible.

In the optimal arrangement, the number of traffic cars will be distributed as evenly as possible, i.e., $$$\lvert a_i-a_j\rvert\leq 1$$$ for each valid $$$(i,j)$$$.

Now that we have constructed the optimal arrangement of traffic cars, let's find out the value of minimum inconvenience of this optimal arrangement. Finding it naively in $$$\mathcal{O}(n^2)$$$ will time out.

Notice that in the optimal arrangement we will have some (say $$$x$$$) elements equal to some number $$$p+1$$$ and the other $$$(n-x)$$$ elements equal to $$$p$$$. Let the sum of all elements in $$$a$$$ be $$$sum$$$. Then, $$$x=sum\bmod n$$$ and $$$p=\bigg\lfloor\dfrac{sum}{n}\bigg\rfloor$$$. For each pair $$$(p,p+1)$$$, we will get an absolute difference of $$$1$$$ and for all other pairs, we will get an absolute difference of $$$0$$$. Number of such pairs with difference $$$1$$$ is equal to $$$x\cdot(n-x)$$$. So, the minimum inconvenience we can achieve is equal to $$$x\cdot(n-x)$$$. That's all we need to find out!

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int a[n];
        long long s=0;
        for(int i=0;i<n;i++)
        {
            cin >> a[i];
            s+=a[i];
        }
        long long k = s%n;
        long long ans = k*(n-k);
        cout << ans << '\n';
    }
}

Did you notice that $$$v\geq 0.1$$$?

The probability of drawing a pink slip can never decrease.

What would be the complexity of a bruteforce solution?

Make sure to account for precision errors while comparing floating point numbers.

Bruteforce over all the possible drawing sequences until we are sure to get a pink slip, i.e., until the probability of drawing a pink slip becomes $$$1$$$.

What's left is just implementing the bruteforce solution taking care of precision errors while dealing with floating point numbers, especially while comparing $$$a$$$ with $$$v$$$ as this can completely change things up, keeping an item valid when it should become invalid. It follows that an error approximation of 1e-6 or smaller is sufficient while comparing any two values because all the numbers in the input have at most $$$4$$$ decimal places. Another alternative is to convert floating point numbers given in the input to integers using a scaling factor of $$$10^6$$$.

#include <bits/stdc++.h>
using namespace std;

const long double eps = 1e-9;
const long double scale = 1e+6;

long double expectedRaces(int c,int m,int p,int v)
{
    long double ans = p/scale;
    if(c>0)
    {
        if(c>v)
        {
            if(m>0)
                ans += (c/scale)*(1+expectedRaces(c-v,m+v/2,p+v/2,v));
            else
                ans += (c/scale)*(1+expectedRaces(c-v,0,p+v,v));
        }
        else
        {
            if(m>0)
                ans += (c/scale)*(1+expectedRaces(0,m+c/2,p+c/2,v));
            else
                ans += (c/scale)*(1+expectedRaces(0,0,p+c,v));
        }
    }
    if(m>0)
    {
        if(m>v)
        {
            if(c>0)
                ans += (m/scale)*(1+expectedRaces(c+v/2,m-v,p+v/2,v));
            else
                ans += (m/scale)*(1+expectedRaces(0,m-v,p+v,v));
        }
        else
        {
            if(c>0)
                ans += (m/scale)*(1+expectedRaces(c+m/2,0,p+m/2,v));
            else
                ans += (m/scale)*(1+expectedRaces(0,0,p+m,v));
        }
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long double cd,md,pd,vd;
        cin >> cd >> md >> pd >> vd;
        int c = round(cd*scale);
        int m = round(md*scale);
        int p = round(pd*scale);
        int v = round(vd*scale);
        long double ans = expectedRaces(c,m,p,v);
        cout << setprecision(12) << fixed << ans << '\n';
    }
}

In this version, $$$x\oplus z=y$$$ or in other words, $$$z=x\oplus y$$$ where $$$\oplus$$$ is the Bitwise XOR operator.

The number of queries allowed is equal to the number of possible initial passwords.

The grader provides us no information other than whether our guess was correct or not. So, we need to find a way to ask queries such that the $$$x$$$-th query will give the correct answer if the original password was $$$(x-1)$$$.

Try to ask queries in such a way that the $$$i$$$-th query reverses the effect of the $$$(i-1)$$$-th query and simultaneously checks if the initial password was $$$(i-1)$$$.

Try to use the self-inverse property of Bitwise XOR, i.e., $$$a\oplus a=0$$$.

In this version of the problem, $$$k=2$$$. So, the $$$k$$$-itwise XOR is the same as Bitwise XOR.

In case of incorrect guess, the system changes password to $$$z$$$ such that $$$x\oplus z=y$$$. Taking XOR with $$$x$$$ on both sides, $$$x\oplus x\oplus z=x\oplus y\implies z=x\oplus y$$$ because we know that $$$x\oplus x = 0$$$.

Since the original password is less than $$$n$$$ and we have $$$n$$$ queries, we need to find a way to make queries such that if the original password was $$$(x-1)$$$, then the $$$x$$$-th query will be equal to the current password. There are many different approaches. I will describe two of them.

The generalised $$$k$$$-itwise XOR does not satisfy the Self-Inverse property. So, the solution for the Easy Version won't work here.

Any property which is satisfied by $$$k$$$-its will also be satisfied by base $$$k$$$ numbers since a base $$$k$$$ number is nothing but a concatenation of $$$k$$$-its. So, try to prove properties for $$$k$$$-its as they are easier to work with.

Let $$$x_j$$$ denote the $$$j$$$-th $$$k$$$-it of $$$x$$$. Then, $$$x_j\oplus_k z_j=y_j$$$ $$$\forall$$$ valid $$$j$$$. Simplifying this,
$$$x_j\oplus_k z_j=y_j$$$ $$$\implies$$$ $$$(x_j+z_j)\bmod k=y_j$$$ $$$\implies$$$ $$$z_j=(y_j-x_j)\bmod k$$$ $$$\implies$$$ $$$z_j=(y_j\ominus_k x_j)$$$ where $$$a\ominus_k b$$$ operation is defined as $$$a\ominus_k b=(a-b)\bmod k$$$.

See Hints 2, 3 and 4 of the Easy Version.

Try to generalise the solutions for easy version by exploring properties of $$$\oplus_k$$$ and $$$\ominus_k$$$ operators.

Note — It is strongly recommended to read the proofs also to completely understand why the solutions work.

The solutions described for the easy version won't work here because the general $$$k$$$-itwise operation does not satisfy self-inverse property, i.e., $$$a\oplus_k a\neq 0$$$.

In this whole solution, we will work in base $$$k$$$ only and we will convert the numbers to decimal only for I/O purpose. Notice that any property which is satisfied by $$$k$$$-its will also be satisfied by base $$$k$$$ numbers since a base $$$k$$$ number is nothing but a concatenation of $$$k$$$-its.

When we make an incorrect guess, the system changes the password to $$$z$$$ such that $$$x\oplus_k z=y$$$. Let's denote the $$$j$$$-th $$$k$$$-it of $$$x$$$ by $$$x_j$$$. Expanding this according to the definition of $$$k$$$-itwise XOR, for all individual $$$k$$$-its $$$(x_j+z_j)\bmod k=y_j$$$ $$$\implies z_j=(y_j-x_j)\bmod k$$$. So, let's define another $$$k$$$-itwise operation $$$a\ominus_k b$$$ $$$= (a-b)\bmod k$$$. Then, $$$z=y\ominus_k x$$$. Now, let's extend the solutions of the Easy Version for this version.

This part may be interesting for hackers and those who would like to understand what goes in the background checkers and interactors which determine the correctness of their solutions.

You must have noticed a large number of submissions failing on Test 1 itself. If you check the checker logs of those solutions, you will find that they fail on many different test cases although the test itself has 1 or 2 test cases. This is because the grader is also adaptive apart from the Rap Sheet System being adaptive. The initial password is not fixed and the grader checks if the solution will give correct answer or not for all possible initial passwords in just a single run! Here is how this is implemented.

The grader maintains a set which initially contains all possible initial passwords. Whenever you ask a query, the grader finds out which initial password will give correct answer for this query. This is found using the generalised expression of queries derived in the Method 2 solution. Take some time to convince yourself that this initial password will be unique. It then removes this initial password from the set if it still exists. After that, if the set is empty, the grader returns 1 (meaning that there is no other password for which the solution can give Wrong Answer), otherwise 0 (obviously after checking the constraints on $$$y$$$). In this way, only a solution which gives correct answers for all possible initial passwords for a particular $$$n$$$ and $$$k$$$ defined in the input will manage to pass.

Sometimes, checkers and adaptive interactors are more difficult to write than the solution itself! This was one such case.

In a simple $$$n$$$-Dimensional Hypercube, two vertices are connected if and only if they differ by exactly $$$1$$$ bit in their binary representation.

The $$$n$$$-Dimensional Hypercubes are highly symmetric and all vertices are equivalent.

If we select a particular vertex, then all directions in which the edges connected to it goes are also equivalent.

For any two vertices $$$a$$$ and $$$b$$$ separated at a distance of exactly $$$2$$$, there are exactly $$$2$$$ vertices connected to both $$$a$$$ and $$$b$$$.

Any permuted $$$n$$$-Dimensional Hypercube is isomorphic to the simple $$$n$$$-Dimensional Hypercube. So, its structure is same as the simple $$$n$$$-Dimensional Hypercube.

You can find the permutation greedily

Before moving to the solution, notice a very important property of simple $$$n$$$-Dimensional Hypercubes — Two vertices $$$a$$$ and $$$b$$$ are connected if and only if $$$a$$$ and $$$b$$$ differ by exactly one bit in their binary representations.

The permutation can be found using the following greedy algorithm — First, assign any arbitrary vertex as $$$p_0$$$. This is obvious since all vertices are equivalent. Then, in the simple $$$n$$$-Dimensional Hypercube, all powers of $$$2$$$ must be connected to the vertex $$$0$$$. Moreover, these vertices are added only when we are adding another dimension to the cube. Since all directions are also equivalent, it does not matter in which direction we add a new dimension. So, we can assign all the $$$n$$$ vertices connected to $$$p_0$$$ in the permuted $$$n$$$-Dimensional Hypercube as $$$p_1$$$, $$$p_2$$$, $$$p_4$$$, $$$p_8$$$, $$$\ldots$$$, $$$p_{2^{n-1}}$$$ in any arbitrary order. Now, we will find $$$p_u$$$ for the remaining vertices in increasing order of $$$u$$$.

In order to find $$$p_u$$$, first find a set $$$S$$$ of vertices $$$v$$$ such that $$$v < u$$$ and $$$v$$$ is connected to $$$u$$$ in the simple $$$n$$$-Dimensional Hypercube. Then find any vertex $$$w$$$ connected to all the vertices $$$p_v$$$ such that $$$v\in S$$$ in the permuted $$$n$$$-Dimensional Hypercube and assign $$$p_u=w$$$. I claim that we can never make a wrong choice because we will never have a choice! There will only be one such vertex $$$w$$$ for any $$$u$$$. Let's prove it.

Instead of colouring the permuted $$$n$$$-Dimensional Hypercube, try to colour the simple $$$n$$$-Dimensional Hypercube and map these colours to the permuted one in the end using the permutation found in Part 1.

The number of vertices of each colour will be equal.

Try to colour a simple $$$4$$$-Dimensional Hypercube. This is not a graph problem, rather a constructive problem.

The way in which vertices are connected in a simple $$$n$$$-Dimensional Hypercube suggests something related to Bitwise XOR.

Let's try to colour the simple $$$n$$$-Dimensional Hypercube instead of the permuted one. We can map the colours to the permuted one in the end using the permutation found in Part 1.

I claim that if $$$n$$$ is not a power of $$$2$$$, then no colouring exists. A simple explanation is that the graph is symmetric and also the colours. So, it is natural that the number of vertices of each colour must be equal meaning $$$2^n$$$ must be divisible by $$$n$$$ or in other words, $$$n$$$ must be a power of $$$2$$$ itself. But if symmetry doesn't satisfy you, I have a formal proof too.

Construction - This is the most interesting and difficult part of the whole problem. The following construction works —

Consider a vertex $$$u$$$. Let its binary representation be $$$b_{n-1}b_{n-2}\ldots b_2 b_1 b_0$$$. Then the colour of this vertex will be $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$. Let's show why this works.

• $$$\bigoplus\limits_{i=0}^{n-1} i\cdot b_i$$$ will always lie between $$$0$$$ and $$$n-1$$$ inclusive because $$$n$$$ is a power of $$$2$$$.
• If we are at a vertex $$$u$$$ with a colour $$$c_1$$$ and we want to reach a vertex of colour $$$c_2$$$, we can reach the vertex $$$v=u\oplus(1\ll (c_1\oplus c_2))$$$. This is a vertex adjacent to $$$u$$$ since it differs from it by exactly $$$1$$$ bit and this is the $$$(c_1\oplus c_2)$$$-th bit. Notice that the colour of this vertex $$$v$$$ will be $$$c_1\oplus (c_1\oplus c_2) = c_2$$$.
• $$$(c_1\oplus c_2)$$$ will always lie between $$$0$$$ and $$$n-1$$$ because $$$n$$$ is a power of $$$2$$$. So, $$$v$$$ will always be a valid vertex number.

You can see that many of these facts break when $$$n$$$ is not a power of $$$2$$$. So, this colouring will not work in such cases.

Finally, after colouring the simple hypercube, we need to restore the vertex numbers of the permuted hypercube. This can be simply done by replacing all vertices $$$u$$$ with $$$p_u$$$ using the permutation we found in Part 1.

Well, that's enough of theoretical stuff. For those who like visualising things, here is a 4-D Hypercube and its colouring -

Finding the permutation takes $$$\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$$$ time if implemented using set or $$$\mathcal{O}(n^2\cdot 2^n)$$$ time if implemented using vector. Constructing the colouring for the simple $$$n$$$-Dimensional Hypercube takes $$$\mathcal{O}(n\cdot 2^n)$$$ time. Restoring colours for the permuted $$$n$$$-Dimensional Hypercube takes $$$\mathcal{O}(2^n)$$$ time.

So, the overall time complexity is $$$\mathcal{O}(n\cdot\log_2 n\cdot 2^n)$$$ or $$$\mathcal{O}(n^2\cdot 2^n)$$$ depending upon implementation.

#include <bits/stdc++.h>
using namespace std;

void permuteHypercube(int n,int m,vector<int> adj[],set<int> s[],int p[])
{
    for(int i=0;i<m;i++)
        p[i]=-1;
    bool used[m];
    for(int i=0;i<m;i++)
        used[i]=false;
    p[0]=0;
    used[0]=true;
    for(int u=1;u<m;u++)
    {
        vector<int> req;
        for(int i=0;i<n;i++)
        {
            int v=u^(1<<i);
            if(v<u)
                req.push_back(v);
        }
        if(req.size()==1)
        {
            int v=req[0];
            for(int i=0;i<adj[p[v]].size();i++)
            {
                int w=adj[p[v]][i];
                if(used[w])
                    continue;
                p[u]=w;
                used[w]=true;
                break;
            }
        }
        else
        {
            int v=req[0];
            for(int i=0;i<adj[p[v]].size();i++)
            {
                int w=adj[p[v]][i];
                if(used[w])
                    continue;
                if(s[w].find(p[req[1]])!=s[w].end())
                {
                    p[u]=w;
                    used[w]=true;
                    break;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int m = (1<<n);
        int p[m];
        set<int> s[m];
        vector<int> adj[m];
        for(int i=0;i<n*m/2;i++)
        {
            int u,v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
            s[u].insert(v);
            s[v].insert(u);
        }
        permuteHypercube(n,m,adj,s,p);
        for(int i=0;i<m;i++)
            cout << p[i] << " ";
        cout << '\n';
        if(n!=1 && n!=2 && n!=4 && n!=8 && n!=16)
        {
            cout << -1 << '\n';
            continue;
        }
        int temp[m];
        for(int i=0;i<m;i++)
        {
            int clr=0;
            for(int j=0;j<n;j++)
            {
                if(i&(1<<j))
                    clr=clr^j;
            }
            temp[i]=clr;
        }
        int c[m];
        for(int i=0;i<m;i++)
            c[p[i]]=temp[i];
        for(int i=0;i<m;i++)
            cout << c[i] << " ";
        cout << '\n';
    }
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <utility>
#include <queue>
#include <map>
#include <assert.h>
#include <stack>
#include <string>
#include <ctime>
#include <chrono>
#include <random>
using namespace std;
 
const int MAX=65536;
int power[21]={0};
vector<int> adj[MAX+1];
bool xtra[MAX+1];
bool in[MAX+1];
vector<int> f(vector<int> s)
//given a set of vertices [graph], returns the permutation that was applied to the simple hypercube to get this graph
{
	/*
	cout << "set\n";
	for (auto it : s)
	{
		cout << it << " ";
	}
	cout << '\n';
	*/
	if ((int)s.size()==2)
	{
		vector<int> p(2);
		p[0]=s[0];
		p[1]=s[1];
		return p;
	}
	for (auto i: s) in[i]=true;
	int v1=s[0];
	int v2=-1;
 
	for (auto i: adj[v1])
	{
		if (in[i])
		{
			v2=i;
			break;
		}
	}
	assert(v2!=-1);
	//cout << "v1= " << v1 << " v2 = " << v2 << '\n';
	vector<int> component;
	//multisource BFS from (v1, v2)
	{
		queue<int> q;
		q.push(v1);
		q.push(v2);
		map<int, bool> vis;
		vis[v1]=true;
		vis[v2]=true;
		map<int, bool> cmp;
		cmp[v1]=true;
		component.push_back(v1);
		while (!q.empty())
		{
			auto u=q.front();
			q.pop();
			for (auto i: adj[u])
			{
				if ((!vis[i])&&in[i])
				{
					vis[i]=true;
					q.push(i);
					cmp[i]=cmp[u];
					if (cmp[i]) component.push_back(i);
				}
			}
		}
	}
	for (auto i: s) in[i]=false;
	for (auto i: component) in[i]=true;
	vector<int> p1=f(component);
	for (auto i: s) in[i]=true;
	for (auto i: component) xtra[i]=true;
	
	vector<int> p((int)s.size());
	
	int z=component.size();
	assert(2*z==(int)s.size());
	
	for (int i=0; i<z; i++) p[i]=p1[i];
	
	for (int i=0; i<z; i++)
	{
		//i+z
		int g=-1;
		for (auto i: adj[p[i]])
		{
			if (in[i]&&(!xtra[i]))
			{
				g=i;
				break;
			}
		}
		assert(g!=-1);
		p[z+i]=g;
	}
	for (auto i: component) xtra[i]=false;
	for (auto i: s) in[i]=false;
	return p;
}
 
vector<int> colorit(int n)
{
	vector<int> ret(n);
	for (int i=0; i<n; i++)
	{
		int res=0;
		for (int z=0; z<20; z++) res^=z*((power[z]&i)!=0);
		ret[i]=res;
	}
	return ret;
}
 
void solve()
{
	int n;
	cin>>n;
	for (int i = 0; i < power[n]; i++) adj[i].clear();
	for (int j = 0; j < n * power[n - 1]; j++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	vector<int> p;
	
	{
		vector<int> s;
		for (int i=0; i<power[n]; i++) s.push_back(i);
		p=f(s);
	}
	
	for (int i=0; i<power[n]; i++) cout<<p[i]<<' ';
	cout<<'\n';
	
	if (power[n]%n)
	{
		cout<<-1<<'\n';
		return;
	}
	vector<int> col=colorit(power[n]);
	vector<int> out(power[n]);
	for (int i=0; i<power[n]; i++)
	{
		out[p[i]]=col[i];
	}
	for (int i=0; i<power[n]; i++) cout<<out[i]<<' ';
	cout<<'\n';
	return;
}
 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	//t=1;
	
	power[0]=1;
	for (int j=1; j<=20; j++) power[j]=power[j-1]*2;
	
	while (t--)
	{
		solve();
	}
	return 0;
}