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

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

Задачи, которые не успели написать, разберу кратко. Задавайте вопросы.

233A - Идеальная перестановка

Идея: Gerald Реализация: tunyash Разбор: fdoer

Эту задачу можно было решать разными способами, например, таким: рассмотрим перестановку p, в которой pi = i, то есть просто последовательность чисел от 1 до n. Очевидно, для неё условие ppi = i выполняется всегда. Осталось только преобразовать её таким образом, чтобы выполнялось и второе условие: pi ≠ i. Для этого поменяем местами каждые два соседних элемента, т.е. для каждого k: k * 2 ≤ n поменяем местами значения p2k - 1 и p2k. Нетрудно убедиться, что для полученной перестановки оба условия выполняются всегда.

233B - Неквадратное уравнение

Идея: tunyash Реализация: tunyash, Gerald Разбор: fdoer

Для начала найдем диапазон значений, которые может принимать s(x). Так как из уравнения x2 ≤ n, а по условию n ≤ 1018, x ≤ 109, иначе говоря, десятичная запись любого решения не длиннее 10 цифр. Значит, максимальное значение smax = s(9999999999) = 10·9 = 90 (на самом деле это грубая оценка, smax даже меньше, но нам достаточно и её).

Переберем значение s(x): 0 ≤ s(x) ≤ 90. Получаем обычное квадратное уравнение относительно переменной x. Осталось решить его и проверить равенство того значения s(x), что мы зафиксировали, сумме цифр в разрядах полученного корня. Если корень нашелся и равенство выполнено, обновим ответ.

Пожалуй, самое важное в этой задаче — аккуратно и без ошибок вычислений считать дискриминант.

Подчеркну, что для решения задач div2.A и div2.B не требовалось знание массивов.

232A - Циклы

Идея: tunyash, fdoer Реализация: tunyash Разбор: tunyash

Будем добавлять ребра в порядке сортировки сначала по вершине в меньшим номером, затем с большим (просто два for'a). Если добавление ребра вызывает переполнение кол-ва циклов, не добавляем его. Считать количество циклов, которые добавятся можно за O(n) (могут появиться только циклы, содержащие добавленное ребро, следовательно достаточно перебрать третью вершину). Очевидно, что это найдет какой-то ответ, потому что, добавив два ребра из вершины мы всегда можем получить 1 треугольник. Тогда получается, что ответ всегда есть. Можно довольно просто доказать, что мы уложимся в 100. Асимптотика решения O(n3).

Доказательство

  • Первыми несколькими шагами алгоритма мы сгенерируем полный граф. Потому что каждое ребро можно будет добавить
  • Полученное количество треугольников — C(p, 3) для какого-то p. C(p, 3) ≤ k при этом p максимально.
  • Для данных ограничений p ≤ 85.
  • После первой фазы алгоритма, если из некоторой вершины мы добавляем u ребер, то количество треугольников увеличивается на C(u, 2).
  • Получается, мы представляем маленькое число  ≤ C(85, 2) в виде суммы C(i, 2).
  • Первое число, которое мы вычтем, будет отличаться от нашего не более чем на C(85, 1) = 85, поскольку C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
  • Второе число — не более чем на C(14, 1) = 14.
  • Далее можно применять данную оценку аналогично.
  • Для всех возможных k данный алгоритм укладывается в 90 вершин.

Может быть есть что-то более красивое, но вообще на контесте можно было остановиться пункте на пятом и забить.

232B - Таблица

Идея: tunyash, Skird Реализация: tunyash Разбор: tunyash

  • Пусть si — количество точек в столбце i.

  • На картинке изображены два соседних квадрата n × n, A — количество вершин в левой части рисунка (это один столбец), B — количество точек в средней области и C — количество точек в правой области (это тоже один столбец). По условию, имеем:
  • Следовательно A = C.
  • Таким образом
  • Разделим столбцы на классы эквивалентности по признаку . Для всех a и b из одного класса sa = sb.
  • cnta — количество столбцов в классе с .
  • Существует (Cnk)cnta способов нарисовать по x точек в каждом из столбцов этого класса независимо от других классов.
  • dp[i][j] — количество способов заполнить классы 1, ... i таким образом, что .
  • cnti принимает и . Посчитаем (Cna)cnti для всех a и cnti и будем использовать при подсчете дп. Получаем сложность O(n2·k).

232C - Графы Доу

Идея: tunyash, Gerald Реализация: tunyash, Gerald Разбор: tunyash

Будем рекурсивно разворачивать граф, сводя задачу к поиску кратч. пути в графаз меньших порядков. Заметим, что вершина |D(n - 1)| + 1 — точка сочленения (кроме случаев n ≤ 2, но для них описанные ниже равенства так же выполняются).

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

Пусть dist(a, b, n) — длина кратчайшего пути между a и b в графе порядка n.

dist(a, b, n) = min(dist(a, |D(n - 1)|, n - 1), dist(a, 1, n - 1)) + dist(b - |D(n - 1)|, 1, n - 2) + 1

Красным обозначены ребра, синим — пути. Записанная формула обозначает, что мы можем пойти из вершины a по пути 1 в вершину 1, затем по прямому ребру в вершину |D(n - 1)| + 1 и по пути 3 в вершину b, либо пойти по пути 2, попасть в вершину |D(n - 1)|, пройти по ребру в вершину |D(n - 1)| + 1, а затем по пути 3 в вершину b. Если обе вершины лежат в меньшей половине графа — то

dist(a, b, n) = dist(a - |D(n - 1)|, b - |D(n - 1)|, n - 2)

Если они лежат в большей половине, то нужно дополнительно разобрать случай прохождения пути через точку сочленения, то есть

dist(a, b, n) = min(dist(a, b, n - 1), min(dist(1, a, n - 1), dist(|D(n - 1)|, a, n - 1)) + min(dist(1, b, n - 1), dist(|D(n - 1)|, b, n - 1) + 2)

Если искомый путь проходит через точку сочленения, то для каждой вершины мы можем пройти либо в вершину 1, либо в вершину |D(n - 1)| + 1, а затем по прямому ребру в вершину |D(n - 1)| + 1. Если путь не проходит через точку сочленения, то рассмотрим его в графе меньшего порядка.

Можно заметить, что для каждого k будет не более 4 различных запусков dist(i, j, n).

Как это понять? Во первых, если отбросить запросы, где либо a = 1, либо b = |D(n)|, все запросы получаются из первого последовательным отнятием от изначальной пары (ai, bi) одинаковых чисел Фибоначчи (по построению D(i) — числа Фибоначчи). Получается, таких запросов будет O(n). Запросы вида (1, a) и (a, |D(n)|) можно рассмотреть отдельно, они хорошо выражаются из самих себя. Учитывая то, что все другие запросы получаются друг из друга прибавлением или отнятием чисел Фибоначчи, запросы этого вида тоже будут получаться друг из друга таким образом. Таким образом, у нас будет не более O(1) серий по O(n) запросов. Это не совсем строго, но, вроде, понятно. Это довольно нетривиальный момент, рекомендую задавать вопросы, если непонятно.

Получим асимптотику на запрос (логарифм возникает из соображения о том, что размеры графов в зависимости от порядка растут экспоненциально). Важно было запускать алгоритм не для данного n, а для наименьшего n, такого, что max(a, b) ≤ D(n - 1)

232D - Забор

Идея: tunyash, Gerald Реализация: fdoer Разбор: fdoer

В разборе этой задачи подразумевается, что читатель имеет представление о суффиксных массивах и о быстром нахождении lcp (наибольшего общего префикса) двух суффиксов строки. Об этом можно почитать, например, на e-maxx.ru.

Итак, пусть d и d' — массивы такие, что di = hi - hi + 1, d'i =  - di для любого 1 ≤ i ≤ (n - 1). Тогда мы можем переформулировать условие, при котором два куска забора считаются подходящими, следующим образом:

  • куски не пересекаются, то есть, нет ни одной доски, такой, что она содержится в обоих кусках забора;
  • куски имеют одинаковую ширину;
  • для любого i (0 ≤ i ≤ r1 - l1 - 1) выполняется dl1 + i = d'l2 + i (если ширина забора — 1, это выполняется всегда).

Отсюда возникает следующая идея: для ответа на запрос нам достаточно узнать, сколько подотрезков массива d' длины (r - l) совпадают с отрезком массива d, соответствующим этому запросу, и при этом не пересекаются с ним ни в каком индексе. Построим суффиксный массив sa на последовательности-конкатенации массивов d и d', между которыми поставим еще разделитель — число, которого ни в одном из этих массивов нет. Запомним также для каждого суффикса di его позицию posi в суффиксном массиве. При поступлении нового запроса на отрезке l...r все куски забора, подходящие по второму и третьему условиям, будут началами суффиксов, лежащих в суффиксном массиве подряд на позициях boundleft...boundright, причем boundleft ≤ posl ≤ boundright и lcp(boundleft...boundright) ≥ (r - l). Поэтому границы этого отрезка можно найти с помощью бинарного поиска. В зависимости от реализации функции lcp для отрезка значения bound мы определим за или за .

Теперь осталось найти число позиций из saboundleft...boundright, удовлетворяющих еще и первому условию, т.е. таких, которые соответствуют суффиксам d', префикс длины r - l которых не пересекается по индексам с отрезком (l...r - 1). Иными словами, количество i (boundleft ≤ i ≤ boundright) таких, что либо n + 1 ≤ sai ≤ n + l - (r - l) - 1, либо sai ≥ n + r (суффиксы d' начинаются в конкатенации с позиции n + 1, т.к. в массиве d (n - 1) элемент, а на n-ном месте расположен разделитель). Это тоже классическая задача поиска количества чисел из заданного диапазона на заданном отрезке массива, она может быть решена за на запрос.

Её можно решать, например, offline с помощью метода scanline и любой структуры данных, поддерживающей запросы суммы на отрезке и увеличения в точке, либо online с помощью персистентных/двумерных структур вроде дерева отрезков.

Таким образом, вкратце алгоритм выглядит примерно так:

  • построение массивов d и d'. Построение на конкатенации суффиксного массива.
  • препроцессинг для вычисления lcp на отрезке

Для каждого запроса:

  • определение промежутка (boundleft...boundright) с помощью двух бинарных поисков, обращающихся к lcp на отрезке.
  • запрос на число суффиксов, которые лежат в суффиксном массиве на этом промежутке и которые соответствуют подотрезкам, не пересекающимся с отрезком запроса.

Если массив строить за , запрос lcp выполнять за O(1) с предподсчетом за (с RMQ на разреженных таблицах), а числа из диапазона искать за на запрос, итоговая асимптотика получается . Однако решения, выполняющие запрос lcp за логарифм с использованием, например, дерева отрезков, тоже укладывались в ограничения.

232E - Быстрая Черепаха

Идея: tunyash Реализация: tunyash, KAN Разбор: tunyash

Выберем центральный столбец на поле. Посчитаем для каждой клетки слева доступные на столбце, для каждой клетки справа те из которых доступна данная. Это простая динамика с битсетами, она полностью аналогична динамике в классической задачи о черепашке, для правой половины доски. ( — логическое или, в данном случае имеется в виду побитовое или для масок) для левой. Динамика считаем маску доступных клеток на центральном столбце.

С помощью этих данных мы получим ответы на все запросы, точки которых лежат по разные стороны от выбранного столбца за n/32 на запрос (просто сделаем and битсетов). На картинке кружочками обведены две клетки, через которые может проходить путь между точками запроса.

Далее запустимся от двух половинок доски, выполняя тот же алгоритм. Получается время работы .

Запросы можно выполнять онлайн, храня для каждой клетки битсетов — множеств доступных клеток на столбцах, выбираемых центральными.

Альтернативное решение от mrNobody. Оно оказалось быстрее и проще авторского, но, к сожалению, он не смог сдать его на контесте.

  • Будем считать динамику range[i][j][k] — самую верхнюю и самую нижнюю клетку столбца k, доступную из клетки (i, j). Ее можно считать аналогично динамике из авторского решения.
  • Кроме того посчитаем динамику able[i][j][k] — доступна ли хотя бы одна клетка столбца k из клетки (i, j) при движении влево и вверх.
  • Обе эти динамики можно посчитать за O(n·m2) времени и памяти (потом будет понятно, что на памяти можно сэкономить).
  • Рассмотрим запрос (x1, y1) (x2, y2). Утверждается, что путь из (x1, y1) (x2, y2) существует тогда и только тогда, когда и верно able[x2][y2][y1].

  • Действительно, рассмотрим три пути. 1 — из (x1, y1) в самую верхнюю доступную клетку столбца y2. 2 — из (x1, y1) в самую нижнюю доступную клетку столбца y2 и 3 — из (x2, y2) в одну из клеток столбца y1. Если эта клетка расположена ниже (x1, y1), то путь 3 пересекает путь 2, а значит мы можем пройти по пути два до точки пересечения, а затем по пути 3 до точки (x2, y2).
  • Случай пересечения путей 1 и 3 аналогичен.
  • Мы получили решение за O(n·m2 + q) времени и такое же количество памяти, однако можно заметить, что хранить все состояния динамики не обязательно, достаточно только q из них. Пользуясь этим, можно сократить используемую память до O(nm + q).
Разбор задач Codeforces Round 144 (Div. 1)
Разбор задач Codeforces Round 144 (Div. 2)
  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

В "Неквадратном уравнении" достаточно просто перебрать все числа от корня из N — 100 до корня из N.

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

    я перебирал от корня из n и до тех пор пока позволяло время работы

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

    У меня бинпоиск прошёл:) Функция не строго монотонная, но скачет не сильно.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      а как ты с бинпоиском сделал.... в конце что нужно проверять перед тем как l,r- присваевать значения

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

    Я туплю, до меня не доходит, почему это верно. Объясните, пожалуйста

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

А где задача "Таблица"?

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

как доказывается что в С найдётся ответ причём быстро? я добавлял рёбра оба фора 1..n у меня TL

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

I believe there is an error in the DIV2 B problem. The range of s(x) should be 0 <= s(x) <= 81 because: sqrt( 10 ^18 ) = 10^9. So the biggest value s(x) will be when x = 10^9-1: s(x) = 9*9 = 81.

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Задача B интересна приколом разбиения на две динамики.

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

For Div 2 A, there is no answer when n is odd, not only when n = 1.

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

    Yes, you are right. Thank you.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    deleted: sorry misunderstanding

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

    why is it -1 for all odd numbers?

    i can make something like this when n=3

    3 1 2 here P1=3 P2=1 P3=2

    we know Pp1=1 so by comparing p1=2 Pp2=2 so p2=3 and p3=1

    so every condition is getting satisfied. why is it -1 then?

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

      $$$P_{P_{i}}=i$$$, so $$$P_{P_{1}}=1$$$ but in your case $$$P_{1}=3$$$ so $$$P_{P_{1}}=P_{3}=2\ne{1}$$$ , hence the condition is false. Every node in this array forms a cycle with another node, so it will never be possible to solve it for odd $$$n$$$.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

in doe graphs problem. 1 6 1 13 for this input answer 2 but i dont understand.can someone explain me.pleas write path from 1 to 13

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Чекер как-то странно работает: в задании В на числе 10000006999999929 программа, запущенная в студии, дает правильный результат, а на сайте дает -1.

Код:

http://pastebin.ru/d9YHTI8q

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Код убрал из предыдущего сообщения, так как форматтер работает плохо

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

      Посмотри на панель инструментов и врапни исходник кнопкой Block

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Код:

        #include <stdio.h>
        #include <math.h>
        #include <stdint.h>
        uint64_t sum(uint64_t x)
        {
        	uint64_t k,s1,s=0;
        	k=x;
        	while (k>0){
        		s1=k%10;
        		k-=s1;
        		s+=s1;
        		k/=10;
        	}
        	return s;
        }
        int main()
        {
        	int i;
        	double t;
        	uint64_t n,z=0,x=1;
        	scanf("%I64d",&n);
        	for (i=1;i<91;i++){
        		t=i*i+4*n;
        		t=sqrt(t);
        		t=t-i;
        		t/=2;
        		if(t-(int)t==0 && (t*t+sum(t)*t-n==0)) {z=1;break;} 
        	}
        	
        	if (z)printf("%d\n",(int)t); else printf("-1");
        
        	return 0;
        }
        
        
        
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Скорее всего проблема в использовании double там, где не надо. При работе с числами с плавающей точкой надо быть осторожным, поскольку вычисления не абсолютно точны. В частности, лучше не сравнивать double с 0, а вместо этого делать fabs(expr) <= eps, eps — константа порядка 10 - 610 - 9. Вообще, если есть возможность вести вычисления в целочисленных типах, то лучше ею воспользоваться.

    В этой задаче предлагаю сделать

    int x = sqrt(i*i+4*n) + 0.5;

    , и далее double не использовать вообще.

    P.S. Если локально код пишется под VS, то и на сервере лучше выбирать тот же компилятор, MS C++ — будет меньше сюрпризов.

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

Вопрос по 232C — Графы Доу Как я понял на каждой итерации по k, мы получаем всего 4 различных запроса и как-то должны их хранить, чтобы не опускаться в следующий раз глубже в рекурсию. Так вот сообственно вопрос: как это лучше делать, и сохраняем мы запросы вида d(i,j,n) где i и j отличны от 1 и |D(n)| ?

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

    Делаем массив из четырех элементов для каждого k и пробегаемся по нему при вызове dist(i, j, k).

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

      готов согласиться что у меня руки кривые((

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

I'm having trouble understanding this part:

  • So we have to present a small number that is less than C(85, 3) as sum of C(i, 2).
  • The first number we subtruct will differ C(85, 1) on some value not greater than C(85, 1) = 85, because C(n, k) - C(n - 1, k) = C(n - 1, k - 1).
  • The second number we subtruct will differ the number we have on some value not greater than C(14, 1) = 14. and so on.

Thank you.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Look, we have some full graph. We add one vertex with q edges starting form it. Is it clear, that we added Cq2 triangles to our graph? It it's not, you may check it with pen and paper. Number of vertexes in full part of our graph is p and Cp3 ≤ k. p is maximal possible value such that Cp3 ≤ k. Therefore k ≤ Cp + 13 and k - Cp3 ≤ (Cp + 13 - Cp3. k - Cp3 ≤ Cp2. Ok? We add new vertex with q edges. We will add Cq2 triangles to our graph and q is maximal. Therefore k - Cp3 - Cq2 ≤ Cq1 = q. We have x = Cp3 + Cq2 triangles in out graph and difference with k is no more than q ≤ p ≤ 85. If we will repeat adding vertex five or six time difference between k and number of triangles will become zero.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Please check the last case of problem c div 1. There are some mistakes with the formula.

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

Didn't understand editorial for "Quick Tortoise". Somebody please explain in detail.

  • »
    »
    12 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

    Basically, the simple way to solve this problem would be to precompute if it's possible to get from (x1,y1) to (x2,y2) for all possible (x1,y1) and (x2,y2). This would take O(n^4) time and space so with n as large as 500 it won't work.

    The idea for speeding this up is to use divide & conquer. The editorial splits the board by columns, and I did it by rows in my solution (and that is probably more cache-efficient, although that doesn't really matter) — either way will work fine.

    Imagine first that every query you get was such that (x1,y1) is in the top half of the board and (x2,y2) is in the bottom half of the board. Then you could answer each query by the following procedure: 1. find all the cells in the middle row of the board reachable from (x1,y1) 2. find all the cells in the middle row of the board from which you can reach (x2,y2) 3. you answer "Yes" iff the results of 1. and 2. intersect

    You can precompute the answers for 1 and 2 using dynamic programming. As O(n) cells of the middle row could be reachable from any cell, you could use O(n^3) time and space to compute the answers for 1 and 2. Using a bit set (the bitset class in C++ for example), you can reduce that to ~(n^3)/32 assuming you implement the bit set as an array of 32-bit ints. So for subproblem 1, for each cell, you store a bit set that indicates if you can reach a certain column of the middle row or not. You can compute each bit set via two bit set operations by the rules of the game.

    Now back to the original problem. If the query is not of the form discussed above, then it is either entirely in the top half of the board, or it is entirely in the bottom half of the board. Therefore, you build an almost-complete binary tree structure. At every node of this tree, you solve the same problem discussed above for a certain row-slice of the board. The depth of this tree is about lg(#rows). You can precompute this tree before any queries are processed.

    Then, for each query, you just walk down the tree to the appropriate row-slice of the board and look up the precomputed answers to subproblems 1 and 2 and return the answer. For implementation details of exactly this idea, you can look at my solution http://codeforces.me/contest/232/submission/2471344.

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

I didn't understand the analysis of the solution of "Table" problem. Can anyone help me and explain it in more details please?

»
2 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have a different weird solution for 233B: after looking for x for many different n values, I have noticed that the answer is always close to sqrt(n) so I just looked for a suitable x from sqrt(n)-100 to sqrt(n)+100

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for even ones can we write 1 2 3 4 as 4 3 2 1 it also satisfies the condition pi!=i and ppi=i why not writing