7.4. Дополнительные идеи

7.4.1. Отсечение по времени

В реальных олимпиадных задачах у вас всегда есть ограничение времени, превышать которое не стоит. Если ваша программа проработает больше отведённого времени, то вы получится \(0\) баллов за тест — ничего хуже в этом тесте быть не может :) Поэтому имеет смысл избегать такого результата всеми силами, в надежде, что, может быть, повезёт и получится что-то лучше. А именно:

  • В задачах на оптимизацию (т.е. когда надо найти объект с оптимальными параметрами) можно, когда вы видите, что время подходит к концу, просто вывести лучший найденный на данный момент объект и завершить работу. Если повезёт и он на самом деле будет оптимальным, то тест будет зачтён, иначе хуже, чем TL, все равно не будет.
  • В задачах на поиск объекта ничего не остаётся, как вывести, что решения не существует (естественно, ваша программа должна также завершаться сразу, как только нашла решение). Кстати, это далеко не всегда бывает неправильно, даже наоборот: в хорошем наборе тестов обязательно должны быть большие тесты с ответом «решения не существует», т.е. какие-то тесты так вы скорее всего пройдете. Если же вам требовалось (редкий случай) вывести все решения, то ничего не остаётся, как их все найденные на данный момент и вывести, и завершить работу (про вывод всех решений см. ниже).
  • В задачах на подсчёт числа объектов ничего не остаётся, как вывести, сколько вы уже насчитали. Конечно, скорее всего это будет неправильно (ваша программа работала секунду, насчитала, допустим 1432 объекта, и хочет работать ещё секунду… неужто она не найдёт ни одного объекта больше? :) а если найдёт, то, значит, \(1432\) — неверный ответ), но работать больше нельзя и ничего лучше тут, видимо, не придумаешь.

Соответственно, прямо в функции \(find\) вы можете проверить, сколько времени уже работает ваша программа, и если время приближается к ограничению по времени, то прервать перебор.

Примечание

Тестирование программы с отсечением по времени на компьютере жюри выглядит весьма эффектно, особенно если вы смотрите непосредственно в экран тестирующего компьютера, на котором пишется, сколько времени осталось: время приближается к TL, и все уже готовы увидеть TL, но нет — за доли секунды до TL ваша программа завершается, запускается чекер и вы видите WA — что ж, не повезло — или OK — ура, повезло.

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

Напишу только несколько замечаний:

  • Можно конечно использовать стандартные функции для получения текущего времени. Только проверьте, дают ли они результат с нужной точностью. Например, если у вас в задаче ограничение времени 1 секунда, то вам нужны функции, дающие время с точностью хотя бы до десятых долей секунды. Тут даже может оказаться, что стандартные функции вам дают например время в миллисекундах, но оно увеличивается скачками, т.е. точность вовсе не 1/1000 секунды.
  • Вместо стандартных функций для текущего времени есть разные функции для получения времени в виде какого-то условного числа, которое можно потом конвертировать, например, в секунды считая с некоторого момента. Под windows, например, есть функция getTickCount, она возвращает количество миллисекунд с момента включения компьютера, правда, увеличивается скачками по 10-16 миллисекунд (на разных компьютерах может быть по-разному). Такие функции могут работать быстрее.
  • Вообще смотреть на системное время — это не очень правильно, потому что реально тестирующая система смотрит на процессорное время, потраченное вашей программой. Правда, в хороших тестирующих системах нет другой нагрузки на процессор, кроме вашей программы, поэтому процессорное время примерно равно реальному прошедшему времени.
  • Но вообще, системные функции для определения времени могут работать относительно долго и ощутимо замедлять вашу программу. Поэтому каждый раз в функции \(find\) её вызывать — это может быть медленно. Тогда может иметь смысл завести ещё глобальную переменную \(nn\), которая будет считать, сколько раз вы вошли в \(find\), и только, например, каждый \(1000\)-ый раз проверять. Типа того:
var t:longint;
   nn:longint;

procedure find...
begin
if i>k...
end;
if (nn=1000) then begin
    if (gettickcount>t0+1000) then begin
        // вывести ответ и выйти из программы
    end;
    nn:=0;
end;
inc(nn);
...

...

begin
t0:=gettickcount;
nn:=0;
...
end.

(Я тут сбрасываю \(nn\) каждый раз заново на ноль. Вам может захотеться не сбрасывать, а проверять остаток от деления на 1000: if (nn mod 1000=0). Не надо так, деление — относительно долгая операция.)

На само деле, конечно, необходимая частота проверок сильно зависит от задачи: иногда может понадобиться и каждый \(100\,000\)-ый раз проверять и т.п.; каждый раз стоит подбирать константу заново, чтобы проверки были достаточно частыми, но не слишком частыми.

7.4.2. Перебор двумерного массива

Иногда объекты, которые мы перебираем, проще представлять в виде двумерного массива (а не одномерного, как было всегда раньше). Пусть, например, надо перебрать все способы заполнения матрицы \(N\times N\) нулями и единицами. Можно это написать так:

procedure find(i,j:integer); {i,j --- координаты клетки, которую перебираем}
begin
if i>n then begin {если кончилась вся матрица}
   check;
   exit;
end;
if j>n then begin {если кончилась текущая строка}
   find(i+1,1);   {то перейти к следующей}
   exit;
end;
a[i,j]:=0;
find(i,j+1);
a[i,j]:=1;
find(i,j+1);
end;

Осознайте этот пример.

7.4.3. Вариации порядка выбора элементов

(Это не то, что обсуждалось в разделе про эвристики.) Иногда имеет смысл заполнять элементы ответа не в том порядке, в котором приходит в голову, а продумать, в каком. Например, пусть наша задача — дано \(N^2\) чисел, проверить, можно ли из них составить магический квадрат (т.е. квадрат, в котором суммы всех строк равны и суммы всех столбцов равны). Можно, конечно, перебирать так, как написано в предыдущем пункте: т.е. выбирать значения для первой строки, потом для второй и т.д…Но можно поступить так: в \(find(1)\) перебираем значение клетки \((1,1)\), в \(find(2)\)\((1,2)\), …\(find(n)\)\((1,n)\), \(find(n+1)\)\((2,1)\) и внимание! \(find(n+2)\)\((3,1)\), \(find(n+3)\)\((4,1)\) и т.д., потом остаток второй строки, потом остаток второго столбца и т.д., в таблице ниже для \(N=5\) приведены номера, какая клетка какой по счету будет.

1 2 3 4 5
6 10 11 12 13
7 14 17 18 19
8 15 20 22 23
9 16 21 24 25

Смысл в том, что в этой задаче есть естественное отсечение: если мы заполнили очередную строку или столбец, то стоит сразу проверить, что его сумма равна сумме всех чисел, делённой на \(N\) (очевидно, что именно такая должна быть сумма каждой строки и каждого столбца). Поэтому стоит заполнять таблицу в таком порядке, чтобы проверять можно быть как можно быстрее. Если заполнять построчно, то проверять можно будет после первой строки (при глубине рекурсии \(N\)), после второй (\(2N\)), после третьей (\(3N\)), и т.д., зато в конце — на всей последней строке будем проверять суммы столбцов.

А если делать заполнять по очереди строки и столбцы (как описано два абзаца назад и показано в примере), то отсечения будут: после первой строки (на глубине \(N\)), после первого столбца (на глубине \(2N-1\), а не \(2N\) (!)), после второй строки (\(3N-2\), а не \(3N\)) и т.д. — т.е. отсечения будут раньше и программа будет работать быстрее.

Аналогичные идеи могут быть и в других задачах, хотя, наверное, весьма редко.