USACO February 2006 Problem 'dna' Analysis

by Bruce Merry

This problem can (only?) be solved by brute force. Recurse through all permutations of the N strings (there are at most 5040 of them), then attempt to merge them from left to right. Store the shortest found string found so far and print it out at the end.

Here's a compact solution from China's Yilun Gong:

var
  b:array[1..7] of byte;
  used:array[1..7] of boolean;
  fp:text;
  a:array[1..7] of string;
  n,i,min:byte;
procedure work(t:byte);
  var
    ok:boolean;
    s:string;
    i,k,j,l,p,max:byte;
  begin
    if t=n+1 then begin
      s:=a[b[1]];
      for k:=2 to n do begin
        max:=0;l:=length(s);
        for j:=1 to length(a[b[k]]) do begin
          ok:=true;
          for p:=1 to j do
            if a[b[k]][p]<>s[l-j+p] then begin
              ok:=false;break;
            end;
          if ok then max:=j;
        end;
	s:=s+copy(a[b[k]],max+1,100);
      end;
      if length(s)<min then min:=length(s);
      exit;
    end;
    for i:=1 to n do
      if not used[i] then begin
        used[i]:=true;
        b[t]:=i;
	work(t+1);
	used[i]:=false;
      end;
  end;
begin
  assign(fp,'dna.in');reset(fp);
  readln(fp,n);
  for i:=1 to n do readln(fp,a[i]);
  close(fp);
  min:=255;
  fillchar(used,sizeof(used),false);
  work(1);
  assign(fp,'dna.out');rewrite(fp);
  writeln(fp,min);
  close(fp)
end.