Even and Odd Combinations
InterviewTime limit2sMemory limit1024 MB
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 -combination out of is a -element subset of the -element set . To denote a combination, list its elements in ascending order. For example, the 2-combinations out of 3 are , , and .
A combination is even if it has an even number of elements, and odd otherwise. For a fixed , let be the set of all even combinations out of , and let be the set of all odd combinations out of . It can be shown that and contain the same number of combinations.
For each , do the following. Construct any bijection between and . Then, given an element of one of these sets, print the corresponding element of the other set.