Настройки поиска (Страница 2 из 9)

Я надеюсь, Сережа не будет против, если я выложу тест, который он мне показал в личке на КФ.

Структура простая: Join(1,2), Join(1,3), Join(1,4), ..., Join(1,N). Предполагается, что Join выглядит следующим образом:

Join(a,b) {
 A = root(a);
 B = root(b);
 if (rand() & 1) p[A] = B; else
 p[b] = A;
}

При такой реализации с вероятностью 1/2 при каждом Join'е у дерева, содержащего вершину 1, высота будет увеличиваться на 1. Ожидаемая высота через N операций будет N/2.

Интересно. А этот тест дает логарифм для произвольного рандсида?

Да ее вроде и за O(NlogN) решить можно, хотя тут и квадрата достаточно.

Сделаем бинпоиск по длине ответа. Теперь при фиксированной длине 2Х найдем все позиции начал К-четных строк такой длины. Понятно, что от цикличности можно избавиться просто записав исходную строку S как S+S. Рассмотрим подстроку из первых Х позиций. Найдем кол-во символов из первой половины, которые отличаются от второй половины. Теперь сдвинем эту строку на 1 вправо. Что мы получим?

Пусть были символы: 1234 5678, после сдвига станет 2345 6789. Как видно, символы 234 и 678 соответствуют друг другу как в изначальной строке, так и в сдвиге, значит нам нужно только удалить пару 1-5 и добавить 5-9, что делается за О(1). Таким образом, можно пройти по всей строке и за O(N) найти все позиции начал К-четных строк.

Теперь, когда мы знаем длину ответа, просто пройдем по всем позициям начала и выберем мин. лексикографическую строку за квадрат. Если сильно хочется O(NlogN), можно это суфф. массивом сделать.

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

По ссылке, которая указана в первом посте. Я так понимаю, это не та версия задачи, но в таком случае нужно указывать ссылку и на вторую версию.

Кстати, если уже сдали задачу каким-то другим методом, то баг в этом ищется просто: пишется рандомный генератор и сравниваются ответы двух методов на рандомных тестах до тех пор, пока программы не выдадут различный ответ.

Мультиребра это повторяющиеся ребра между одними и теми же вершинами. Другими словами, между одной парой вершин может быть несколько ребер с разным весом, а ваш алгоритм запоминает только последнее из них в порядке ввода.

Хм... Да, действительно. Не зря я пишу только алгоритм Крускала

Ну в коде есть баги вроде: не инициализируются переменные min и v. На первой итерации они нули, а что с ними будет дальше - не известно. Минимум же не всегда будет уменьшаться, поэтому на какой-то итерации оно просто оставит вершину v с предыдущего шага.

Алгоритм Прима предполагает что первое добавленное ребро будет минимальным в графе. Вершина 1 не обязательно инцидентна этому ребру, следовательно, она не обязательно должна быть добавлена первой в мин. остов.

Динамикой по вершине и длине пути. Пусть f(i,j) - количество путей из вершины s в вершину i длины j. Тогда f(i,j)=сумма f(w,j-1) по всем w из которых есть ребро в i.

Из простых соображений следует что количество счастливых билетов длины 2N с суммой цифр 2S равно квадрату количества чисел длины N с суммой S. Это позволяет свести исходную задачу к такой: есть N и S, нужно найти количество чисел из N цифр с суммой цифр S. Такая задача решается динамическим программированием. Кстати, формула правильная.

Если сумма нечетна, ответ 0. Иначе считаем количество чисел с N цифрами с суммой S/2 и возводим в квадрат.