Нахождение двух минимальных сумм чисел Опции

[andriano]

В приведенном мной объяснении многое описано не совсем так, как я бы делал на практике, да.

Логично.

А как быть с тестом, в ответе которого участвует большее количество элементов? Почти уверен, что можно составить тест, для которого понадобится и около 40.
Всегда рад

А я думаю, что невозможно больше 16. Об этом, кстати, S_lip писал.
Т.е. при заданных ограничениях первые 16 упорядоченного массива ВСЕГДА будут содержать минимум одну искомую группу.
Впрочем, возможно, я и ошибаюся. Просто я не могу придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.

[Michael_Rybak]

придумать алгоритм, который смог бы сгенерировать последовательность, не содержащую искомых групп, длиной больше 15.

сейчас попробуем.

[Michael_Rybak]

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум. мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.

[andriano]

выбрать не получилось.

видимо, можно доказать, что максимум - 14. примерно понимаю, как, могу довести до конца.

Жду с интересом.
PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук

но, возвращаясь к оценкам - 3^N, где N = скольки? Тебе ведь нужно перебрать все возможные выборки из данных 200 чисел, т.к. нас интересует минимум.

Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.

мне кажется, заоптимизировать это настолько, чтоб оно работало на всех тестах в пределах секунды - нереально.

Ну, можно начать с нескольких эвристик. Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.

[Michael_Rybak]

PS.: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384. 15 штук

Ну 15. Какая разница.

Не нужно. Сортируем по возрастанию и перебираем не более 16 первых.

Это не обязательно правильно.

Мне кажется, "тяжелые" для перебора случаи должны легко поддаваться жадному алгоритму.

Можешь написать и попросить ОП проверить на сайте.

[S_lip]

Michael_Rybak, спасибо за пример.
Вот исправленный код:

const
  MaxCount=200;
  MaxSum=100000;
type
  posanddif=record
    c,d:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  n:byte;
  u,d:array [1..(MaxSum div 2)] of longint;
  udn:longint;
  b:array [0..(MaxSum div 2)] of longint;
  pad:array [1..(MaxSum div 2)] of posanddif;
  pn:longint;
  f:text;
  i,j:longint;

procedure ProcessUD(uu,dd:longint);
var
  ii:longint;
begin
  if dd<=(MaxSum div 2) then begin
    if b[dd-uu]>0 then begin
      if u[b[dd-uu]]>uu then begin
        ii:=1;
        while (ii<=pn) and (pad[ii].c<>b[dd-uu]) do inc(ii);
        if ii>pn then begin
          inc(pn);
          pad[pn].c:=b[dd-uu];
          pad[pn].d:=u[b[dd-uu]]-uu;
        end else if pad[ii].d>u[b[dd-uu]]-uu then
          pad[ii].d:=u[b[dd-uu]]-uu;
      end;
    end else begin
      inc(udn);
      u[udn]:=uu;
      d[udn]:=dd;
      b[dd-uu]:=udn;
    end;
  end;
end;

begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do
    readln(f,a[i]);
  close(f);

  for i:= 0 to (MaxSum div 2) do b[i]:=0;
  udn:=1;
  i:=1;
  u[1]:=0;
  d[1]:=a[1];
  b[a[1]]:=a[1];

  for i:= 2 to n do begin

    pn:=0;
    j:=udn;

    ProcessUD(0,a[i]);

    for j:= 1 to j do begin
      ProcessUD(u[j],d[j]+a[i]);
      if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
      else ProcessUD(d[j],u[j]+a[i]);
    end;

    for j:= 1 to pn do begin
      dec(u[pad[j].c],pad[j].d);
      dec(d[pad[j].c],pad[j].d);
    end;

  end;
  writeln(u[b[0]]); //ответ
end.

Главное отличие - обходим все элементы, а также убрана медленная проверка в конце главного цикла и добавлен массив pad, который содержит позицию "с" и разницу "d" тех элементов, для которых мы нашли замену.
Этот пример также навел на мысль, что максимальное количество перебираемых чисел будет не 15 и не 16, а... 7502 (1 15000 15002 15004 ... 29998 29999). Поэтому нужно перебирать все n. Однако прога не справилась с примером из 200 чисел (1 200 202 204 ... 594 595). udn выходит за пределы 50000. Ошибка 201. Я потратил достаточно много времени, чтобы найти, где промах, но безуспешно.
Этот пример в 200 чисел прикреплен.

Сообщение отредактировано: S_lip - 31.12.2007 21:00

[Michael_Rybak]

на самом деле 15.

1 15000 15002 15004 ... 29998 29999- если ты имел ввиду все четные, начиная с 15000, то сразу же получится 15000+15006 = 15002+15004.

ночью посмотрю, где ошибка.

[S_lip]

15000+15006 = 15002+15004 = 30006
1+29998 = 29999

[Michael_Rybak]

А, теперь я понял, к чему этот пример был.

Отличная мысль.

andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.

[S_lip]

Спасибо большое всем, кто потратил свое время читая это все и пытался помочь...
Я нашел решение:

const
  MaxCount=200;
  MaxSum=100000;
type
  posanddif=record
    c,u:longint;
  end;
var
  a:array [1..MaxCount] of integer;
  n:byte;
  u,d,b:array [0..(MaxSum div 2)] of longint;
  udn:longint;
  pad:array [1..(MaxSum div 2)] of posanddif;
  pn:longint;
  f:text;
  i,j:longint;

procedure ProcessUD(uu,dd:longint);
begin
  if dd<=(MaxSum div 2) then begin
    if b[dd-uu]>0 then begin
      if u[b[dd-uu]]>uu then begin
        inc(pn);
        pad[pn].c:=b[dd-uu];
        pad[pn].u:=uu;
      end;
    end else begin
      inc(udn);
      u[udn]:=uu;
      d[udn]:=dd;
      b[dd-uu]:=udn;
    end;
  end;
end;

begin
  assign(f,'file.in');
  reset(f);
  readln(f,n);
  for i:= 1 to n do
    readln(f,a[i]);
  close(f);

  for i:= 0 to (MaxSum div 2) do b[i]:=0;
  udn:=0;
  i:=1;
  u[0]:=0;
  d[0]:=a[1];
  b[a[1]]:=a[1];

  for i:= 2 to n do begin

    pn:=0;
    j:=udn;

    ProcessUD(0,a[i]);

    for j:= 0 to j do begin
      ProcessUD(u[j],d[j]+a[i]);
      if u[j]+a[i]<d[j] then ProcessUD(u[j]+a[i],d[j])
      else ProcessUD(d[j],u[j]+a[i]);
    end;

    for j:= 1 to pn do begin
      if pad[j].u<u[pad[j].c] then begin
        dec(d[pad[j].c],u[pad[j].c]-pad[j].u);
        u[pad[j].c]:=pad[j].u;
      end;
    end;

  end;

  writeln(u[b[0]]);
end.

Ошибка 201 была из-за того, что элементы массивов u и d могу принимать значения от 0 до 50000. Т.е. всего 50001 значение. Изменение начала массивов на 0-ой элемент решило проблему. Также убрана ошибка в ProcessUD, долгий цикл "for ii:= 1 to pn" перенесен в конец главного цикла в виде проверки "if pad[j].u<u[pad[j].c]".
В тестере все примеры решены.

P.S.: С новым годом =)

Сообщение отредактировано: S_lip - 1.01.2008 18:34

[Michael_Rybak]

Отлично, поздравляю.

Приходи еще

[andriano]

andriano, видишь, этот тест показывает, что нельзя оставлять наименьших 16.

Спасибо, я заметил.
Кстати, к вопросу об эвристиках:
Решения вида a[n]=a[m] находятся (после сортировки) за O(N), вида a[n]=a[m]+a[k] за O(N*log(N)), a[n]+a[m]=a[k]+a[l] и a[n]=a[m]+a[k]+a[l] - за O(N^2*log(N)).
Правда:
1, 2, 4, 8, 16, 32, 64, 15000, 15128, 15256, ... 29848, 29975 содержит 125 чисел и находится только степенной эвристикой аналогичной тем, что приведены выше, O(N^7*log(N)).

В этой связи возникает еще одна интересная задача: подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения. Заодно интересно было бы оценить минимально необходимое количество тестов в этом наборе.

[Michael_Rybak]

подобрать набор тестов для проверки этой задачи, который бы отсекал все возможные частичные решения

Такая задача возникает всегда. Именно поэтому уровень тех, кто предлагает задачи на олимпиаду, должен как минимум не уступать уровню участников, а в идеале - быть на порядок выше. Как, кстати, и бывает на всероссийской олимпиаде школьников, где каждая задача проходит через семь кругов ада, прежде чем попасть на тур.