USACO NOV06 Problem 'rndnum' Analysis

by rho

First note that you only need to count the number of round numbers not exceeding Start-1 and subtract that from the number of round numbers not exceeding Finish. So we are only concerned with counting the number of round numbers not exceeding some number X. Since X can be up to a two billion, we cannot count round numbers one by one.

Consider X in binary. Let N be the number of digits in X.

Let A(x,y) be the number of binary strings with x '0's and y '1's that begin with 0. Let B(x,y) be the number of binary strings with x '0's and y '1's that begin with 1. Let C(x,y) be the number of binary strings with x '0's and y '1's that begin with 0 where each string represents a number not exceeding the number represented by the last x+y digits of X. Let D(x,y) be the number of binary strings with x '0's and y '1's that begin with 1 where each string represents a number not exceeding the number represented by the last x+y digits of X.

We update A, B, C, D using dynamic programming bottom up for each x+y=k, incrementing k until k = N.

The desired result is the sum of all D(x,y) where x+y = N and x>=y, plus the sum of all B(x,y) with x+y=y.

Do this procedure for both Finish and Start-1 and subtract to get answer.

Here is Bruce Merry's solution (which might differ from above explanation):

#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

static int choose[64][64];

static int rndnum(int b, int z, unsigned int top) {
    int ans = 0;

    if (z > b || top == 0) return 0;
    if (top >= (1U << b)) {
        for (int j = max(z, 0); j <= b; j++)
            ans += choose[b][j];
        return ans;
    }

    ans += rndnum(b - 1, z - 1, top);
    unsigned int h = 1U << (b - 1);
    if (top > h && b > z)
        ans += rndnum(b - 1, z, top - h);
    return ans;
}

static int rndnumrange(int b, int z, unsigned int start, unsigned int end) {
    if (start >= end) return 0;
    return rndnum(b, z, end) - rndnum(b, z, start);
}

int main() {
    for (int i = 0; i < 64; i++) {
        choose[i][0] = choose[i][i] = 1;
        for (int j = 1; j < i; j++)
            choose[i][j] = choose[i - 1][j - 1] + choose[i - 1][j];
    }

    ifstream in("rndnum.in");
    ofstream out("rndnum.out");
    unsigned int f, l;
    int ans = 0;
    in >> f >> l;
    for (int i = 1; i <= 31; i++) {
        unsigned int f1 = max(f, 1U << (i - 1));
        ans += rndnumrange(i, (i + 1) / 2, f1, l + 1);
    }
    out << ans << "\n";
    return 0;
}