ivan.popelyshev's blog

By ivan.popelyshev, 12 years ago, In Russian

Условие задачи

Есть N ≤ 1018 пар (Pi, Wi) сгенерированных по следующему алгоритму:
  • Pi = ((A*Pi-1 + B) mod M) + 1
  • Wi = ((C*Wi-1 + D) mod K) + 1
  • Где  M, K ≤ 107, P1, W1, A, B, C, D заданы.
  • Требуется найти:
  1. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≤ Pi и  Wj < Wi либо  Pj < Pi и  Wj ≤ Wi
  2. Количество пар  (Pi, Wi)  таких что не существует пары (Pj, Wj) такой что Pj ≥ Pi и  Wj > Wi либо  Pj > Pi и  Wj ≥ Wi 
Разберемся с первой частью, вторая делается аналогично.
Заметим, что если все Pi одинаковы, то ответ это количество минимумов.
Переходим к двумерной задаче: для каждого P < M будем хранить текущий минимум minp и количество найденных пар вида (P, minp)
Если посчитать эти величины, то ответ ищется просто: для каждого p надо проверить что нет такого p0 < p что minp0 ≤ minp , и в этом случае прибавить к ответу количество  пар вида (P, minp). Это делается за один проход.

Как же искать этот minp ?

Понятно, что через max(M, K) элементов обе последовательности зациклятся. Обработаем этот кусок, выкинем его и рассмотрим циклы, осталось обработать N1 = N - max(M, K) пар.
Получившиеся циклы:
p0, p1, p2, p3,  ... pA - 1
w0, w1, w2, w3, ... wB - 1
Для фиксированного pi важно знать минимум и количеством минимумов тех  w, что попадают в пару вместе с фиксированным pi:
Для p0 они имеют индексы 0, A%B, (2 * A)%B, ...
Для p1 это 1, (A + 1)%B, (2 * A + 1)%B, ...
Для p2 это 2,  (A + 2)%B,  (2 * A + 2)%B,  ... 
Для p(A - 1) это (A - 1)%B,  (2 * A - 1)%B, ... 
Все индексы меньше N1

Вот тут можно поступить по-разному
  • Разбить цикл из w на орбиты элементов которые идут через A и на каждой использовать RMQ. Это  O(max(M, K) * logN) по времени. Можно улучшить до O( max(M, K) ) используя RMQ за O(1) два раза, ведь последовательности могут иметь длины N1 / A и  N1 / A.
  • Cчитать минимум и количество минимумов среди элементов w проиндексированных (i + j * A)%B , 0 ≤ j < 2k для каждого k, и использовать на этом двоичный подъём, "перемножая" массив как при быстром возведении в степень. Это  O(max(M, K) * logN) по времени
В обоих случаях получается и и O(max(M, K)) по памяти. 

Лично я выбрал второе, макстест на Java работал за 17 секунд, но на их 20 тестах программа уложилась в 2 минуты. К тому же можно было запускать это сразу на нескольких компах/ядрах.


Если вы считаете что можете объяснить это лучше и проще, пожалуйста, оставьте свои объяснения в комментариях.
  • Vote: I like it
  • +70
  • Vote: I do not like it