UWCOI21F - Binary Puzzle - Editorial

PROBLEM LINK:

Contest

Practice

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();
}

I have a different solution using Gray Code Sequences.

What is a Gray Code Sequence and How to Generate an n-bit Gray Code Sequence

An n-bit Gray Code Sequence is a permutation of all integers in the range [0,2^n-1] such that any two consecutive integers (and also the first and last integer) differ by exactly 1 bit. For example, a 4-bit Gray Code Sequence is 0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8.

In order to generate such a sequence, the following algorithm can be used -
Let us consider the sequence 0-indexed and a_0=0
a_i can be obtained by flipping the j-th bit of a_{i-1} where j is the rightmost set bit in i. Alternatively, a_i=i\oplus \left \lfloor{i/2}\right \rfloor

Let us try to construct pairs (x_i,y_i) satisfying y_i=x_{i\%k+1} and all x_i are distinct. This clearly satisfies the first 4 conditions. Also, notice that f(f(x_i))=x_{(i+1)\%k+1}. So, we need to find a sequence in which x_i and x_{(i+1)\%k+1} have different number of set bits. If we construct a graph by connecting the positions i with i+2 (and also k-1 with 1 and k with 2), we have two cases -

  • k is odd - In this case, we will get a single cycle of length k. Since two consecutive numbers of the Gray Code Sequence differ by exactly 1 bit, they can never have the same number of set bits. Hence, we can assign the first k numbers of an n-bit Gray Code Sequence to the positions in this cycle. Also, since 0 has no set bits, it will always have different number of set bits from the last selected number.
  • k is even - In this case, we will get two disjoint cycles of length k/2 (one containing all odd positions and other containing all even positions). To the positions in the first cycle, we can assign the first k/2 numbers of an (n-1)-bit Gray Code Sequence. Let this sequence be z_i. Then, to the positions of the second cycle, we can assign the numbers 2^{n-1}+z_i. Note that all the numbers are still distinct and the last condition is satisfied individually for each of the two cycles.

Submission

5 Likes

Why cant we create a single cycle for them? I wrote a code that would create a single cycle of the form (2 set bits) -> (2 set bits) -> (3set bits) -> (3set bits) -> and so on. Since f(f(a)) is the number 2 edges away from a, such a cycle will be valid right?

I have checked your solution and it fails for the test case with n=10, k=7. Your code is printing the sequence 0,768,1020,1023,512,256,640. According to this, f(f(640))=768 but both 768 and 640 have 2 set bits. Also, your solution was printing the last pair in the reverse way.

1 Like

Thanks a lot man! I almost gave up upsolving this since my hardcoded solution for 20 pts was also incorrect. I completely forgot the fact that order mattered while drawing cycles, I’ll try to solve it now

In the Setter’s Solution, k=3 is not handled as a special case and instead when k%4==3 one loop of size 3 is formed. This seems more simpler than finding a loop of size 7. Can update the editorial.