PROBLEM LINK:
Author: Jishnu Roychoudhury
Tester: Smit Mandavia
Editorialist: Jishnu Roychoudhury
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Binary representation of numbers.
PROBLEM:
You are given two integers, N and K. Output K pairs (x_i,y_i). Define a function f such that f(x_i)=y_i and f is undefined for all other values of x. Pairs must then meet the following conditions:
-
All x_i are distinct.
-
All y_i are distinct.
-
All x_i,y_i are in the range [0, 2^N - 1] and are integers.
-
f(f(x_i)) is defined for all $i$i.
-
Let H(x) be the number of set bits in the binary representation of x. Then, H(x_i) \neq H(f(f(x_i)))
Subtask 1 [20 points]: K \leq 8
Subtask 2 [40 points]: K = 2^N
Subtask 3 [40 points]: No additional constraints.
QUICK EXPLANATION:
-
In order for f(f(x_i)) to be defined for all x_i, we need to create a set of disjoint cycles on the graph with edges x_i \rightarrow f(x_i).
-
We can solve for N=2, K=4 with the cycle 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0, and solve for K=2^N by copying this cycle many times.
-
By creating cycles of length 5, 6, and 7, we can solve for arbitrary K.
EXPLANATION:
There are many valid solutions for this problem, so this editorial only considers one of the solutions. To see other solutions, you can read some of the Accepted submissions for the problem.
Subtask 1:
Let a value v be an “input” to function f if v = x_i for some i and an “output” to function f if v = y_i for some i.
Consider some value a which is an input. Then, there must be an output b, where b = f(a). But for f(f(a)) to be defined, we need b to be an input as well, so that there can be an output c = f(b) = f(a). Now b is an input, so f(f(b)) must be defined. And to do this, we need to make c an input, but now f(f(c)) must be defined. This process seems to go on infinitely.
To fix this, we need to create a cycle. That is, the outputs to f should be a rearrangement (permutation) of the inputs. More formally, the output should be a disjoint set of cycles.
Note that for this subtask, getting solutions for N=3 is enough, because for higher N you can just use the same answer as N=3. At this point, you can either hand-code valid cycles or brute force permutations to find solutions.
Subtask 2:
Consider the case N=2, K=4. Note that the cycle 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0 solves this case.
We can simply copy this cycle many times to produce a solution for K=2^N. More formally, we can create cycles 4i \rightarrow 4i+1 \rightarrow 4i+2 \rightarrow 4i+3 \rightarrow 4i.
This works since apart from the last two bits, all other bits are the same between all in a single cycle. So the relative bit parity is maintained compared to the prototypical cycle 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0.
Subtask 3:
The idea is that we can simply combine many 4-cycles with a single cycle of different size. However, note that it is impossible to form 1-cycles or 2-cycles. Instead, we can form a single cycle of size 5, 6, or 7 (depending on the value of K modulo 4$) from the values in the range [0,7], and fill the remainder with 4-cycles. We can get cycles of size 5, 6, or 7 from the solution in subtask 1.
K=3 is a special case.
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
void sol(){
int n,k;
cin>>n>>k;
int goal=k;
if(k%4!=0) goal=(k/4)*4;
if(k%4!=0&&k%4!=3) goal-=4;
if(k%4==0){
for(int i=0; i<(goal/4); i++){
cout<<((i*4)+0)<<' '<<((i*4)+1)<<'\n';
cout<<((i*4)+1)<<' '<<((i*4)+2)<<'\n';
cout<<((i*4)+2)<<' '<<((i*4)+3)<<'\n';
cout<<((i*4)+3)<<' '<<((i*4)+0)<<'\n';
}
}
if(k%4==1){
cout<<0<<' '<<1<<'\n';
cout<<1<<' '<<2<<'\n';
cout<<2<<' '<<3<<'\n';
cout<<3<<' '<<7<<'\n';
cout<<7<<' '<<0<<'\n';
for(int i=2; i<=(goal/4)+1; i++){
cout<<((i*4)+0)<<' '<<((i*4)+1)<<'\n';
cout<<((i*4)+1)<<' '<<((i*4)+2)<<'\n';
cout<<((i*4)+2)<<' '<<((i*4)+3)<<'\n';
cout<<((i*4)+3)<<' '<<((i*4)+0)<<'\n';
}
}
if(k%4==3){
cout<<"0 1\n";
cout<<"1 3\n";
cout<<"3 0\n";
for(int i=1; i<=(goal/4); i++){
cout<<((i*4)+0)<<' '<<((i*4)+1)<<'\n';
cout<<((i*4)+1)<<' '<<((i*4)+2)<<'\n';
cout<<((i*4)+2)<<' '<<((i*4)+3)<<'\n';
cout<<((i*4)+3)<<' '<<((i*4)+0)<<'\n';
}
}
if(k%4==2){
cout<<1<<' '<<3<<'\n';
cout<<3<<' '<<0<<'\n';
cout<<0<<' '<<7<<'\n';
cout<<7<<' '<<5<<'\n';
cout<<5<<' '<<2<<'\n';
cout<<2<<' '<<1<<'\n';
for(int i=2; i<=(goal/4)+1; i++){
cout<<((i*4)+0)<<' '<<((i*4)+1)<<'\n';
cout<<((i*4)+1)<<' '<<((i*4)+2)<<'\n';
cout<<((i*4)+2)<<' '<<((i*4)+3)<<'\n';
cout<<((i*4)+3)<<' '<<((i*4)+0)<<'\n';
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t; cin>>t;
while(t--) sol();
}