USACO DEC09 Problem 'bigdance' Analysis

by Rob Kolstad

The idea that a set is partitioned and then each of the partitions is treated equally (along with the statement "if [some condition] then the pieces are treated [just like their parents]") is a clue that this problem probably has a simple recursive solution.

Typical recursive functions look like this:

function recursename (piece_of_the_solution, depth) {	// depth sometimes doesn't appear
    if (this stopping or end condition is met) {
	tally and/or deal with it;
	return;
    }
    // optionally bookkeep that we're doing another level
    generate new pieces from the 'piece_of_the_solution';
    // invoke recursename with each of the pieces and depth + 1:
    for each piece {
	recursename (smaller piece, depth+1);
    }
    // optionally un-bookkeep that we're doing another level
}

Consider a realization of the generic recursive routine for this particular task:

dance (start, end) {	                  // No 'depth', but two defining parameters
    int len = end - start + 1;	          // Used to calculate the two sub-partition sizes
    if (len == 1) return;                 // Per the task -- lone cows are sent home
    if (len == 2) {                       // Duos are bookkept and consumed
        sum += start * end;
        return;
    }
    int lenfirst = (end - start + 2) / 2; // Compute the two partitions
    int lensecond = len - lenfirst;
    dance (start, start + lenfirst - 1);  // Recurse with partition 1 then partition 2
    dance (start + lenfirst, end);
}

And here is the complete solution:

#include <stdio.h>
int sum;
dance (start, end) {
    int len = end - start + 1;
    if (len == 1) return;
    if (len == 2) { sum += start * end; return; }
    int lenfirst = (end - start + 2) / 2;
    int lensecond = len - lenfirst;
    dance (start, start + lenfirst - 1);
    dance (start + lenfirst, end);
}

main () {
    FILE *fin = fopen ("bigdance.in", "r");
    FILE *fout = fopen ("bigdance.out", "w");
    int n;
    fscanf (fin, "%d", &n);
    dance (1, n);
    fprintf (fout, "%d\n", sum);
    exit (0);
}