Skip to code
Skip to analysis

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are ‘1’.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are ‘1’.



A single line with three space separated integers: N, L, and I.


5 3 19


A single line containing the integer that represents the Ith element from the order set, as described.

SAMPLE OUTPUT (file kimbits.out)







Russ Cox

Suppose we knew how to calculate the size of the set of binary numbers for a given nbits and nones. That is, suppose we have a function sizeofset(n, m) that returns the number of n-bit binary numbers that have at most m ones in them.

Then we can solve the problem as follows. We’re looking for the ith element in the set of size n with m bits. This set has two parts: the numbers the start with zero, and the numbers that start with one. There are sizeofset(n-1, m) numbers that start with zero and have at most m one bits, and there are sizeofset(n-1, m-1) numbers that start with one and have at most m one bits.

So if the index is less than sizeofset(n-1, m), the number in question occurs in the part of the set that is numbers that start with zero. Otherwise, it starts with a one.

This lends itself to a nice recursive solution, implemented by “printbits”.

The only difficult part left is calculating “sizeofset”. We can do this by dynamic programming using the property described above:

sizeofset(n, m) = sizeofset(n-1, m) + sizeofset(n-1, m-1)

and sizeofset(0, m) = 1 for all m. We use double’s throughout for bits, but that’s overkill given the rewritten problem that requires only 31 bits intead of 32.

PROG: kimbits
ID: rsc001

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

FILE *fout;

/* calculate binomial coefficient (n choose k) */
double sizeofset[33][33];

	int i, j;

	for(j=0; j<=32; j++)
		sizeofset[0][j] = 1;

	for(i=1; i<=32; i++)
	for(j=0; j<=32; j++)
		if(j == 0)
			sizeofset[i][j] = 1;
			sizeofset[i][j] = sizeofset[i-1][j-1] + sizeofset[i-1][j];

printbits(int nbits, int nones, double index)
	double s;

	if(nbits == 0)

	s = sizeofset[nbits-1][nones];
	if(s <= index) {
		fprintf(fout, "1");
		printbits(nbits-1, nones-1, index-s);
	} else {
		fprintf(fout, "0");
		printbits(nbits-1, nones, index);

	FILE *fin;
	int nbits, nones;
	double index;

	fin = fopen("", "r");
	fout = fopen("kimbits.out", "w");
	assert(fin != NULL && fout != NULL);

	fscanf(fin, "%d %d %lf", &nbits, &nones, &index);
	printbits(nbits, nones, index-1);
	fprintf(fout, "\n");


Back to top