algoprog.kz

Условие задачи были дополнены после контеста. И тут разбор для задачи в том виде, в котором она сейчас.

Изначально задача задумывалась как самая простая халява. Потом решил добавить пару хитростей.

Давайте сначала рассмотрим задачу чуть проще. Представим что у нас нет подпериодов и надо посчитать OHLC для всего периода (от start до end).

Тут все просто, решается в один проход. Храним 4 переменных open, high, low, close. В условии не говорится, что все данные будут из промежутка от start до end, а значит те записи которые не в промежутке можно даже не рассматривать. Считываем очередную запись сверяем с high, low, если что меняем. Самую первую запись сохраняем в open, каждую следующую в close. Это было бы правильно если бы данные были изначально отсортированы, но в условии об этом ничего не говорится. Тут есть два варианта:

• сначала сортировать входные данные
  записей много, отсортировать не успеем.
• или хранить дату первой и последней записи тогда каждый раз будем сравниваться с этими датами, и в случае надобности сохранять в рассматриваемую цену в open или close

Рассмотрев все записи и выводим open, high, low, close.

Теперь вернемся к реальной задаче. Считывая каждую следующую запись, надо определить к какому подпериоду она относится. Возьмем d за длительность подпериода. Если группировка по month, тогда d = 86400×7×4 = 2419200 секунд. Подпериоды считаем начиная со start. Номер подпериода записи с датой date равен x = (date - start) / d.

В условии говорится, что в результате не получится более 10000 группировок. Для каждого подпериода надо хранить шесть восьми байтных чисел: open, high, low, close, opendate, closedate. Начало подпериода хранить не нужно, так-как его легко вычислить pstart = x*d + start.

Еще надо заметить, что ограничение по памяти 2МБ. 2MB = 210241024 = 2097152 байт. В условии говорится, что в результате должно получиться не более 10000 записей. Еще если считывать все входные данные в память, то можно получить Memory Limit. 10000082+1000086 ~= 2MB. Рассмотрев одну запись, она больше не понадобится нам на протяжении всей программы, а значит не зачем ее хранить.

В условии так же говорится, что считать надо с точностью до 4 знаков. На самом деле тут нет никаких вычислений, только сравнения. Так-что можно сравнивать как обычно, главное выводить не менее 4 знаков.

Чтобы решить данную задачу, нужно уметь быстро пересекать числовые отрезки. Можно использовать декартово дерево. При получении какого-то отрезка l, r будем находить концы которые входят в данный отрезок (и начала, и концы) и удалять. После чего найдем первый конец левее l и проверим его другой конец находится после l или нет. Если да, то значит есть пересечение и можно удалить эту точку. Далее повторим это и для перого конца правее r. В итоге мы будем поддерживать нужные отрезки. Доказательство: Когда мы удаляем все точки на отрезке l, r, может быть максимум две точки которые со своими парами пересекают l и r. Потому что до этого момента наши отрезки были непересекаемыми. Далее когда мы удаляем слева от l и справа от r мы избавляемся от случая когда есть эти пересечения. Еще один случай, это когда наш l и r лежит внутри какого-то отрезка. Тогда кол-во точек от l до r = 0. Потому что нет пересечений существующих отрезков. Т.е. последними проверками мы обходим и этот случай. ч.т.д.