Блог пользователя nevidomy

Автор nevidomy, 14 лет назад, По-русски

Задача А.

Так как ограничения были не большими можно предложить много разных решений, например построить граф на N*4 вершины и пустить bfs. Быстрым же решением за O(1)  было: пронумеруем целочисленные точки лежащие на квадрате, к примеру так как показано на рисунке:


Тогда вычислить по координатам номер точки не сложно к примеру если точка имеет координату y==n  -> что её позиция n + x (если нумерация как на рисунке с нуля). Получается что мы преобразовали квадрат в прямую с тем осложнением что можно попасть из клетки N*4 – 1 в клетку 0, то есть у нас не прямая а круг, с отмеченными точками от 0 до 4*N-1 расстояние между смежными двумя точками 1, значит несложно взять разность индексов точек и узнать расстояние при движении по часовой и против часовой: (a-b+4*n)%(4*n) и (b-a + 4*n)%(4*n), ближайшее расстояние и будет ответом.

Задача B

При таких ограничениях на количество запросов нельзя было итеративно добавлять лестницы. Но задачу упрощал тот факт что контрольных ячеек в которых нужно было узнать количество камней было не больше 100, по этому можно было для каждой «интересно» ячейки просмотреть все запросы и посчитать сколько каждый из них добавлял камней, таким образом сложность: O(K*M) что вполне укладывалось в отведённые 2 секунды. Более быстрое решение за O(N+M+K) выглядит так: будем держать в памяти две величины: a – сколько нужно добавлять сейчас к ячейке, v – на сколько должна изменится, в текущей ячейке будем обновлять величину a и v так чтобы a равнялось количеству камней в ячейке после всех операций, а v – на сколько a увеличивается при переходе на следующую ячейку. Тогда задача сведётся к тому что нужно правильно обновлять a и v, что делать не очень сложно, к примеру если есть запрос (x,y,z) – то в ячейке x нужно к a добавить x а к v добавить 1, так как с каждой следующей ячейкой количество камней из за этого вопроса будет увеличиваться на 1. Аналогично после ячейки y уже нужно от v отнять 1 и забрать из a текущее количество камней вложенное запросом, сохранив все такие пары запросов в отдельном массиве можно за один проход посчитать всё.

Задача C

Сначала посчитаем сколько есть массивов у которых каждый следующий элемент начиная с второго не меньше предыдущего. Чтобы сделать это быстро – возьмём листочек в клеточку высотой 1 клеточка и длиной N*2-1 клеточку, далее выберем N-1 клеточку и поставим в них крестики – теперь пусть этот листик кодирует массив, пусть количество пустых клеточек от начала массива до первого крестика будет равнялся количество 1 в массиве(они соответственно идут подряд и если есть хотя бы одна единица – то именно с 1 начинается масив), количество пустых клеточек от первого крестика до второго – количество двоек в массиве и так дальше, легко заметить что количество пустых клеточек будет равно N*2-1 – (N-1) = N. Получается что любой листочек кодирует массив который нам подходит и более того все возможные массивы можно закодировать с помощью такого листочка в клеточку. Всех различных листочков ровно C(N*2-1, N (биномиальный коэффициент из N*2-1 по N). Такое число можно вычислить по формуле с факториалами, единственная сложность – деление. Так как модуль был простым – можно было вычислить обратный элемент в поле по модулю и заменить деление умножением. Получим количество неубывающих последовательностей, соответсвенно есть столько же невозрастающих, осталось отнять те которые попадают и туда и туда, а это не что иное как массив у которого все числа одинаковые

Задача D

Задачка оказалась весьма сложной. Для начала если нет занятых клеточек – вычислить ответ очень даже не сложно – ответом будет сума манхэттенских расстояний, с учётом того, что в манхэттенском расстоянии можно сначала посчитать расстояния по одной координате потом по другой и потом просто просуммировать, ответ найти не сложно. Что же получается когда есть занятые клетки. Сначала посмотри на одну занятую клетку. Если клетка из которой ищутся расстояния не лежит на одной горизонтали или вертикале с занятой – то она абсолютно не влияет на сложность добраться до остальных клеток:


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


Все ячейки после за занятой начинают «запаздывать» на 2 по расстоянию, но более важно то что изменился фронт!! Теперь (с верхней стороны фронта) есть 2 ячейки для которых переход с предыдущего фронта единственен, и как следствие есть дальше встретится занятая ячейка на пути у «угла» фронта – появится новый отрезок запоздавших ячеек и угол фронта снова изменится, так как нас интересует только одна сторона его расширения (с другой стороны больше не может быть занятых ячеек по условию) можно сказать что он сместится от начальной ячейки:


Получается можно просчитать сколько ячеек будет «запаздывать», тем более что запоздание всегда равно двум. Для каждого направления можно выбрать каждую занятую клетку и проверить слева-справа есть ли дальше по этому направлению смежные ячейки и добавить суму запоздания всему отрезку который тормозит первая занятая ячейка. Получается это можно вычислить за квадрат количества занятых клеток, которых не больше min(N,M). Остальное – детали. Нужно вычислить суму манхэттенских расстояний с учетом существования занятых ячеек. Для этого можно сначала вычислить суму для поля, если бы там не было занято, потом для каждой занятой – посчитать расстояние до всех остальных – отнять дважды, так как сначала отнимает учтённые лишние расстояния когда мы выходили из этой ячейки и второй раз отнимаем все те расстояния которые были учтены для всех остальных ячеек в данную. Правда в таком случае дважды отнимутся расстояния между двумя занятыми ячейками – придется добавить их (сложность тоже квадрат). Всего получается решение за O(K^2) где K – количество занятых ячеек.

Задача E

Задача оказалась очень сложной как и планировалось. Для начала уберем все выколотые ячейки – посмотрим как изменяется фигура достижимых клеточек с ростом количества ходов. Сначала изменения не выглядят стабильными, но начиная с некоторого хода – мы увидим фигуру которая дальше не будет менять форму а только расширяться, очевидно  что фигура двухмерная а стало быть рост её «площади» функция квадратичная, действительно, несложная проверка показывает что с каждым новым ходом количество ячеек увеличивается на количество новых ячеек открытых ходом до этого + 28, получается после некоторого момента можно просто считать сумму арифметической прогрессии. С занятыми ячейками дела обстоят также. Вообще возможно несколько вариантов – либо занятые ячейки блокируют проникновения коня дальше, либо нет, в первом случае хватает bfs для поиска решения во втором история повторяется, со временем, когда фигура «уравновесится» - количество новых ячеек поддается тому же правилу “prev+28” . Причем из за ограничения на координаты выколотых клеток (-10 <=x,y <=10) это происходит достаточно быстро. Итак, хватало обычного bfs’а для уравновешивания фигуры, а далее – сума арифметической прогрессии.

Разбор задач Codeforces Beta Round 53
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
Задача B

Я кажется видел проходившие по тл решения сложности O(M*max(b[i]-a[i])+K), что, как я понял, не предполагалось... видимо надо было увеличить разницу b[i] и a[i]. Не понимаю почему вы так не сделали.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    По условию разница не фиксирована (может достигать N - 1), я несколько решений завалил тестом с N=M=10^5 и a[i] = 1, b[i] = 10^5 для всех i.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Блиииииииин... вот я налажал 1≤ai≤bi≤n,1≤ci≤1000... я прочитал бегло как ограничение на ai и bi 1000... а я думаю чё все ломают, а у меня неудачные взломы :(.. да ещё подумал чё-то как то не логично ограничивать их так. Блин :(
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А ты красным стал.. поздравляю!
14 лет назад, # |
Rev. 5   Проголосовать: нравится +4 Проголосовать: не нравится
the translation is a bit difficult to understand...= =
14 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
В задаче C число неубывающих массивов равно числу сочетаний с повторениями, а их C(n + k - 1, k) и т.к. в задаче k = n, получаем C(2n - 1, n)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача С. Объясните пожалуйста, зачем при подсчете С(a, b) (a = 2n - 1, b = n) выполняется выражение вида
res := fact(a) * REV(fact(a - b) * fact(b)), где REV(x) - это pow(x, mod - 2), почему нужно возводить в степень, да еще и в mod - 2??

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://e-maxx.ru/algo/reverse_element
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    вообще res = fact(a) / (fact(a - b) * fact(b)), но это равно fact(a) * REV(fact(a - b) * fact(b)). Покурите тут http://e-maxx.ru/algo/reverse_element
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      да я понял, что это одно и тоже:)просто непонятно почему)
      спасибо, почитаю)
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Это прямое следствие малой теоремы Ферма.

        a / b * (b * bp - 2) ≡ a / b(mod p)

        З.Ы. Хотя, коррекней писать b - 1

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
I can't clearly understand the solution to B here.
I submitted an O(M*K) in the contest which passed.

Now, I tried another approach using fenwick tree , complexity O(M log N + K log N) which passed too. Here's a link to see the code : http://pastebin.com/SAeFbdcG

Is this what is intended in the tutorial or a much simpler solution ?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm not that good at maths and although I knew little Fermat's theorem before, using it in that way was something new to me. 

But what if the module wasn't a primer number? In the contest I used dp to calculate the combination and my approach isn't depended by the module. I'm curious if there is a way (maybe involving math) different than this if the module isn't prime?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Theoretically you can use Chinese remainder theorem on prime factorization of module and then restore answer.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    Euler's totient theorem is a generalization of Fermat's one and works for any module. Also you can solve ax ≡ 1 (mod b) equation by solving its equivalent Diophantine equation ax + by = 1 with extended Euclidean algorithm.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    I didn't use any thing about prime module in my solution. For all prime numbers between 1 and 2n-1 I just computed their power in C(2n-1, n) and then multiplied the result with it. Computing the power was easy, like computing the number of first zero digits of n!. It ran in 130ms.
    Here is my code: http://pastebin.com/Xieb5PuP
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Не видел, чтобы кто-то написал здесь это раньше (может просто плохо посмотрел), но я в решении задачи C обошелся без обратного элемента в поле по модулю. Я просто использовал разложение на простые. Тем, кто знает факторизацию (даже самую примитивную) теоретических знаний хватит, чтобы реализовать решение.
Ну а идея, в общем-то, не оригинальна: посчитаем сколько раз каждый из простых множителей входит в разложение числителя, а затем аналогично для знаменателя. Причем, можно существенно ускорить работу программы если сразу же выполнить сокращение N! на K!. Для того, чтобы разделить числитель на знаменатель, необходимо степень вхождения каждого простого числа в числителе уменьшить на аналогичную степень в знаменателе. Далее просто выполним быстрое возведение в степень по модулю 109+7 для всех простых чисел, которые входят более одного раза в качестве множителей в число. Умножая результат на каждое из чисел полученных при возведении в степень мы и получим ответ. Главное нигде не забыть взятие по модулю.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне кажется, это написать все-таки сложнее
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Не думаю. Ограничения позволяют не использовать быстрое возведение в степень, а просто лобовое + факторизацию можно делать самую простую - до корня. Т.о. нужно лишь посчитать число вхождения каждого делителя в ответ (а делителей здесь будет не больше 6-ти) и просто перемножить с учётом взятия по модулю.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        да, решение представленное в разборе я написал минут за 7
        это же решение отняло бы минут 12
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Thanks for the tutorial. But I cant understand the explanation of problem C. The explanation is very confusing :(
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In problem D, i am facing a tough time in finding the sum of manhattan distances in O(max(n^2 ,m^2)). Can someone give me a hint? :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    The sum of Manhattan distances over all cells: = = .

    Now we need to subtract the sum of Manhattan distances with occupied cells. Suppose (x, y) is one of occupied cells, then . Since there are at most max(n, m) occupied cells, we can just sum over all (x, y).

    Finally, the pairs of occupied cells were subtracted twice and we need to add them back. It's O(max(n2, m2)) as well.

    And don't forget that the order of cells matters, so for example the sums in the second paragraph above need to be multiplied by 2.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Добрый вечер.

Быть может, не самый оригинальный вопрос, но всё же.

Не мог бы кто-нибудь дать пример рабочего *.hs кода для любой задачи последнего контеста. В первую очередь интересует, как необходимо реализовать ввод\вывод для прохождения тестов.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

14 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится
А почему бы не рассматривать задачу C, как:
Лента длиной 2*N клеточек, в которых ровно N крестиков.
Группировки свободных клеток означают количество цифр.
Таким образом для N=4:
1) Имеем ленту: OOOOOOOO
2) Расставляем крестики: OOXOXXOX
3) Имеем 2 единицы, 1 двойку, 0 троек и 1 четверку
4) Ответом будет число размещений крестов в ленте: C(2*n, n)

C(2*n, n) = (2*n)! / (n! * n!)  - Это максимальное число сочетаний (Cnk, случай 2*k = n)

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Только длину ленты и коилчество крестиков надо уменьшить на один. В твоем случае получается еще 0 пятерок (отсутствие О после последнего Х) - например если бы я расставил как

    ОХОХОХХО, получилось бы 1 единица, 1 двойка, 1 тройка, 0 четверок, и одна пятерка. Пятерки нам не нужны.

    И тогда получится правильная формула C(2n-1, n).