2. Комбинаторные объекты

Разбор задачи 592. Головоломка

Переключать более одного раза столбец или строку нет смысла. Если будет выбрано некоторое подмножество столбцов, которые нужно переключить, тогда для каждой строки можно легко определить, стоит ли ее переключать. Если количество минусов в строке больше количества плюсов, то строку переключаем, иначе – не переключаем.

var b:array[1..20] of boolean; { флаги для переключений столбцов }
    n,i,mmin:integer;
    t:array[1..20] of string;
procedure gen(i:integer);
var j,k,s,sm:integer;
begin
  if i>n then
  begin
    { обработка полученного подмножества }
    sm:=0; { считаем число минусов в таблице }
    for j:=1 to n do
    begin
      s:=0; { считаем число минусов в строке в зависимости от переключений столбцов }
      for k:=1 to n do
        if b[k] xor (t[j][k]='-') then
          inc(s);
      if s>n-s then { количество минусов больше плюсов }
        s:=n-s; { переключаем }
      sm:=sm+s;
    end;
    if sm<mmin then { результат улучшился? }
      mmin:=sm;
    exit;
  end;
  b[i]:=false; 
  gen(i+1); 
  b[i]:=true; 
  gen(i+1); 
end;
begin
  readln(n);
  for i:=1 to n do
    readln(t[i]);
  mmin:=n*n; { минимальное количество минусов }
  gen(1);
  writeln(mmin);
end.

Время работы данного решения равно `O(N^2*2^N)`, и при `N=20` потребуется более `4*10^8` операций и, следовательно, программа не пройдет ограничения по времени. Чтобы ускорить вычисления, определение количества минусов можно сделать не при обработке подмножества, а в процессе рекурсии.

var b:array[1..20] of boolean; { флаги для переключений столбцов }
    n,i,mmin:integer;
    t:array[1..20] of string;
    s:array[1..20] of integer; { количество минусов в первых i столбцах }
procedure gen(i:integer);
var j,k,sm:integer;
    ss:array [1..20] of integer; { для сохранения массива s }
begin
  if i>n then
  begin
    { обработка полученного подмножества }
    sm:=0; { считаем число минусов в таблице }
    for j:=1 to n do
    begin
      if s[j]>n-s[j] then
        sm:=sm+n-s[j]
      else
        sm:=sm+s[j];
    end;
    if sm<mmin then { результат улучшился? }
      mmin:=sm;
    exit;
  end;
  for j:=1 to n do
  begin
    ss[j]:=s[j]; { сохраняем количество минусов }
    if t[j][i]='-' then
      inc(s[j]); 
  end;
  b[i]:=false;
  gen(i+1);
  for j:=1 to n do
  begin
    s[j]:=ss[j]; { восстанавливаем количество минусов }
    if t[j][i]='+' then
      inc(s[j]);
  end;
  b[i]:=true;
  gen(i+1);
  for j:=1 to n do
    s[j]:=ss[j]; { восстанавливаем количество минусов }
end;
begin
  readln(n);
  for i:=1 to n do
    readln(t[i]);
  mmin:=n*n; { минимальное количество минусов }
  gen(1);
  writeln(mmin);
end.

Время работы данного решения равно `O(N*2^N)`. Дополнительно уменьшить время работы можно, выключив проверку выхода за границы массива с помощью комментария {$R-} в начале программы.