Эвристический подход для теста Поиск частоты заказов

В статье Пример как писать тесты в Yandex.Contest были даны рекомендации для успешного прохождения тестов компании Яндекс. Один из тестов — поиск наибольшего числа заказов для заданной площади прямоугольника, мы решали простым перебором всех заказов, что увеличивает сложность поиска решения в геометрической прогрессии. Но есть более изящное решение. Однако такие решения приходят не сразу — задача прорабатывается на подкорке некоторое время (несколько дней), а потом вдруг, когда едешь в метро или гуляешь с собакой, бац и решение готово почти мгновенно.

Эврика №1

Итак в чем тут «эврика»? Все заказы имеют координаты x и y. Тогда запишем их в 3-х мерный массив int[][][], где первый индекс будет x, второй — y, а значение — список номеров заказов в этой точке карты (одномерный массив int[]). Да, еще чтобы не создавать пустое место, определим минимальные значения координат у заказов и вычтем их из x и y — то есть сделаем «отстройку от пустоты».

Таким образом, перебирая точки внутри прямоугольника (алгоритм поиска его сторон дан в решении задачи в вышеуказанной статье) мы обращаемся напрямую по координатам в этом массиве к списку номеров заказов и если там пусто, то пропускаем точку, а иначе берем длину списка номеров заказов и суммируем с текущей суммой заказов внутри текущего прямоугольника.

Эврика №2

Но это не все. Теперь мы можем начать вычиcлять нужные значения внутри прямоугольника не перебирая все точки внутри, а всего лишь вычитая все точки одного ребра и прибавляя все точки противоположного (если первый прямоугольник уже просчитан). Например, если мы двигаем прямоугольник скажем вверх по оси Y, тогда мы делаем перебор всех точек на нижнем его ребре (горизонтальном), и вычитаем их из общей суммы заказов внутри предыдущего прямоугольника, и берем ребро нового прямоугольника — на уровне y+dy+1 (противоположное горизонтальное) и все точки с него прибавляем к результату. Где dy — размер прямоугольника по оси Y, а y — текущий уровень просчета. Таким образом, мы значительно уменьшаем число подсчетов. Понятно что если мы двигаем прямоугольник по оси X, скажем слева направо, то так же обрабатываем его вертикальные стороны.

Эврика №3

Ну это не эврика конечно, но все же. Мы можем начать использовать промежуточные результаты, полученные при первом проходе (снизу вверх). Тогда дальше нам нет надобности просчитывать все положения каждый раз, мы опять будем использовать подход с вычитанием и сложением точек противоположных ребер, но уже двигаясь горизонтально — например слева направо. Это не сильно улучшит алгоритм — но можно поиграться еще с длинами сторон и выбирать направление первого прохода в зависимости от того какая из сторон прямоугольника меньше — вертикальная или горизонтальная.

Выводы

Вообще это извечная борьба скорости исполнения с используемой памятью — чем больше используется памяти, тем быстрее решается задача и тем меньше вычислений. По-сути это тривиальный кэш ))