USACO February 2006 Problem 'bdsum' Analysis

by Bruce Merry

The key observation is that each value in the initial row contributes a fixed multiple of itself to the final number, and that these contributions are determined by Pascal's triangle. For example, for N = 4 the initial row A B C D E gives a total of

1*A + 4*B + 6*C + 4*D + 1*E

This makes it easy to compute the sum for a given set of inputs without working through the intermediate rows.

For the size of test-data used, an exhaustive search is sufficient, although there are also pruning strategies that can be used.

Romania's Emanuel Furtuna submitted this solution:

var ok:array[1..10] of boolean;
    a:array[0..10,0..10] of longint;
    pos,st:array[1..10] of longint;
    i,j,k,l,m,n,sum:longint;

procedure calc(k:longint);
    var i,j:longint;
begin
    fillchar(a, sizeof(a), 0);
    a[n,k]:=1;
    for i:=n-1 downto 1 do
         for j:=1 to i do
             a[i,j]:=a[i+1,j]+a[i+1,j+1];
    pos[k]:=a[1,1];
end;

procedure back(k,s:longint);
    var i:longint;
begin
    if s>sum then exit;
    if k=n+1 then begin
         if s=sum then begin
              for i:=1 to n-1 do write(st[i],' ');
              writeln(st[n]);
              close(input); close(output);
              halt(0);
         end;
    end else
        for i:=1 to n do
        if ok[i] then begin
             st[k]:=i; ok[i]:=false;
             back(k+1,s+pos[k]*i);
             ok[i]:=true;
        end;
end;

begin
    assign(input,'bds.in'); reset(input);
    assign(output,'bds.out'); rewrite(output);
    readln(n,sum);
    for i:=1 to n do calc(i);
    fillchar(ok, sizeof(ok), true);
    back(1,0);
    close(input); close(output);
end.