Under construction

Still being built. Things may change

Even and Odd Combinations

Interview

Time limit2sMemory limit1024 MB

Summary
For each n from 1 to 50, build a bijection between even-size and odd-size subsets of {1..n} and print the matching element of the other set for a given one.
Level

Medium4 of 10

Topics
Combinatorics, Bit manipulation, Implementation
Solved
No attempts yet

Problem

A kk-combination out of nn is a kk-element subset of the nn-element set {1,2,…,n}\{1, 2, \ldots, n\}. To denote a combination, list its elements in ascending order. For example, the 2-combinations out of 3 are {1,2}\{1, 2\}, {1,3}\{1, 3\}, and {2,3}\{2, 3\}.

A combination is even if it has an even number of elements, and odd otherwise. For a fixed n>0n > 0, let AnA_n be the set of all even combinations out of nn, and let BnB_n be the set of all odd combinations out of nn. It can be shown that AnA_n and BnB_n contain the same number of combinations.

For each n=1,2,…,50n = 1, 2, \ldots, 50, do the following. Construct any bijection between AnA_n and BnB_n. Then, given an element of one of these sets, print the corresponding element of the other set.

Examples2

  1. Example 1

    Input
    6
    3 0
    
    2 1
    1
    3 3
    1 2 3
    3 1
    1
    3 1
    2
    3 1
    3
    
    Expected output
    3 3
    1 2 3
    2 2
    1 2
    3 0
    
    3 2
    2 3
    3 2
    1 3
    3 2
    1 2
    
  2. Example 2

    Input
    6
    3 3
    1 2 3
    2 2
    1 2
    3 0
    
    3 2
    2 3
    3 2
    1 3
    3 2
    1 2
    
    Expected output
    3 0
    
    2 1
    1
    3 3
    1 2 3
    3 1
    1
    3 1
    2
    3 1
    3