2

Цитирую полный текст задачи:

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.

Формат входного файла

Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.

Формат выходного файла

Выведите M чисел – толщину носкового покрытия в каждой точке.

На первый взгляд, задача кажется весьма простой. Но, используя те поверхностные идеи для ее решения, она часто не проходит по времени (1 секунда). Собственно, был бы очень рад послушать ваши идеи алгоритмов для ее решения.

P.S. Авторы дают небольшую подсказку: использовать сортировку.

8
  • Вопрос недавно обсуждался в немного другой формулировке (отрезки на прямой). Всё просто: превратите каждый носок в два «события»: левый край носка (условно: +1 носок) и правый (условно: -1 носок). Отсортируйте по координате, и пройдитесь по отсортированному массиву, подсчитывая максимум суммы и запоминая, где он встретился.
    – VladD
    Commented 4 окт. 2014 в 11:20
  • 1
    Раз цели Васька «сугубо корыстные», пускай он раскошелится на биткоин-кошелёк XXXXXXX, и его задача скоро решится : ) А вообще недавно был похожий вопрос.
    – Sergiks
    Commented 4 окт. 2014 в 11:20
  • А, вам не нужен максимум. Ну тогда пройдитесь и подсчитайте текущую сумму в каждой точке «события», далее подсчёт количества в произвольной точке сводится к двоичному поиску по событиям. Или если M может быть большим, одновременный проход по двум массивам (как при merge sort'е).
    – VladD
    Commented 4 окт. 2014 в 11:22
  • @sergiks: О, точно, я пытался его найти (похожий вопрос).
    – VladD
    Commented 4 окт. 2014 в 11:25
  • @VladD, не до конца понятно, что за "события" вы имеете ввиду. Координаты, вы имеете ввиду, середины отрезка? Да, в задаче не просят искать никаких максимумов - только количества перечечений отрезков(носков) с точками M.
    – Heisenberg
    Commented 4 окт. 2014 в 11:41

1 ответ 1

1

Интереса некорыстного ради сделал на JS. При максимальных параметрах считает меньше секунды на стареньком макбуке.

  1. старый вариант;
  2. новый целочисленный вариант.

Алгоритм для целочисленных координат:

  1. адреса 1..10000 это всего 14 бит. Сдвигаем их на 3 влево. А 3 новых младших бита будут обозначать тип "события":
    • 001 — начало;
    • 010 — конец;
    • 100 — контрольная точка (КТ).
  2. создаём один массив чисел bin, где будут и события начала/конца (Н/К), и КТ
  3. копируем в него события Н/К в новом виде
  4. копируем в него КТ в новом виде
  5. сортируем как числа по возрастанию
  6. двигаясь от начала меняем счётчик в зависимости от встреченных событий для Н/К (биты 0 или 1 установлены)
  7. по достижении контрольных точек (бит 2 установлен) снимаем текущее показание счётчика.

    Отрезки считаю как [..) — начало входит, конец не участвует.

Старый алгоритм:

  1. координаты концов носков умножить на -1 — так удобнее в данной постановке задачи, где координаты начал всегда положительны;
  2. отсортировать «события» по возрастанию абсолютного значения (игнорируя знаки);
  3. контрольные точки тоже отсортировать по возрастанию;
  4. инициализируем в 0 текущее значение суммы (С): к ней будет +1 или -1, в зависимости от знака очередного начала/конца носка;
  5. два «курсора» указателя - на текущее «событие» носков (может, начало, может, конец), и текущую ожидаемую контрольную точку (К.Т.);
  6. делаем шаг в носках. Смотрим, не перешагнули ли уже одну или несколько К.Т.;
  7. если перешагнули - эти К.Т. получают текущее значение суммы, и курсор К.Т. сдвигается дальше;
  8. обновляем сумму С на текущее "событие" (+- 1);
  9. следующий шаг в носках (go to 6).

Upd. в Хроме отсутствует ф-я Math.sign(). Обновил ссылку, работает в Chrome.

Upd. 2. невежественно пропустил краевые эффекты. Теперь учёл начала/концы интервалов согласно практике [...) — начало отрезка входит в измерение, конец — нет. И добавил график для наглядности.

график

7
  • @sergiks, пробежавжись по вашему новому коду, обнаружил, что с такими, например, параметрами ваш алгоритм будет работать неверно: socks = [1,5,1,5,1,5,1,6,1,7]; points = [5,6,7];
    – AseN
    Commented 4 окт. 2014 в 21:58
  • @0xFFh почему же неверно? 2,1,0 – корректно: я считаю, что начала отрезков попадают в подсчет, а концы - нет. !скрин
    – Sergiks
    Commented 4 окт. 2014 в 22:12
  • @sergiks, дело как раз в том, что это отрезки. А у отрезков концы и начала включены в множество точек. --- Ради интереса тут погуглил, нашел условия этой задачи с тестом: informatics.mccme.ru/mod/statements/… --- Да и, к тому же, если немного видоизменить параметры: socks = [1,5,1,5,1,5,1,6,1,7]; points = [1,5,6,7]; То ответ будет противоречить вашему высказыванию выше( в адрес включения концов отрезков ). Думаю, искать ошибки так можно бесконечно, поэтому пора бы закругляться либо мне, либо вам.
    – AseN
    Commented 4 окт. 2014 в 22:30
  • @0xFFh, Согласно правилам форума, вопросы не должны сводиться к решению либо завершению учебных заданий за учащихся. Пожалуйста, уточните, что вы сделали сами и что не получилось. Ваша ссылка доступна только зарегистрированным участникам дистанционных курсов, коими, видимо, вы с @Heisenberg являетесь. Она не продиндексирована ни Яндексом ни Google. Зато эта задача находится в других местах, как задача с дист. курса, размещённая учениками, неспособными её решить самостоятельно.
    – Sergiks
    Commented 5 окт. 2014 в 6:45
  • 1
    тёрки и сублимация на Хэшкоде
    – etki
    Commented 5 окт. 2014 в 9:04

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.