Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

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

337A - Пазлы

В первую очередь, упорядочим числа f[i] по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из f[k] фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие n пазлов, равных или превосходящих f[k] по размеру, то есть пазлы размеров f[k], f[k+1], ..., f[k+n-1] (это не совсем правильно, если среди f[i] встречаются повторяющиеся числа и выполняется f[k]=f[k-1], но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется f[k+n-1]-f[k].

Чтобы выбрать оптимальное f[k], переберем значение k от 1 до m-n и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом:

read(n, m, f[1..m])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
  best = min(best, f[k+n-1] - f[k])
print best

337B - Бытовая задача

Допустим, что ширина и высота монитора равны W и H соответственно. Так как W:H = a:b, мы имеем H=W*b/a. Аналогично, ширина и высота картинки фильма w и h удовлетворяют соотношению h=w*d/c. Представим себе, что Манао растягивает (или, наоборот, сужает) картинку фильма до тех пор, пока она не упрется в стенки экрана по горизонтали или вертикали. Рассмотрим три случая: соотношение горизонтали и вертикали монитора меньше, больше и равно соответствующему соотношению картинки фильма.

В первом случае (a/b < c/d) картинка заполнит всю горизонталь экрана, и процесс растяжения остановится. Таким образом, новая ширина картинки будет равняться W, то есть картинка увеличилась в W/w раз. Соответственно, её новая высота равна h*W/w = w*c/d * W/w = W*d/c. Нас интересует, какая часть вертикали экрана осталась незанятой, то есть (высота экрана - новая высота картинки) / (высота экрана) = (W*b/a - W*d/c) / (W*b/a) = (bc-ad)/bc.

Во втором случае (a/b > c/d) картинка первой заполнит вертикаль. В этом случае, её высота будет равна H, а ширина — w*H/h = w * W*b/a / (w*d/c) = W*b/a * c/d. Часть горизонтали, оставшася незанятой, равна (W - W*b/a * c/d)/W = (ad-bc)/ad.

В третьем случае картинка заполнит экран полностью, поэтому ответом задачи будет 0.

Для того, чтобы вывести ответ в виде несократимой дроби, нужно найти наибольший общий делитель его числителя и знаменателя. Сделать это можно с помощью алгоритма Евклида, или просто циклом перебрать все числа от 1 до q и выбрать наибольшее, делящее их обоих. Так как q не превосходит произведения двух чисел из входных данных, а значения этих чисел ограничены 1000-ей, в худшем случае придется рассмотреть лишь миллион чисел.

337C - Викторина

Допустим, что Манао в процессе игры удвоил свой счет (за счёт ответа на k последовательных вопросов) ровно X раз. Тогда меньше всего очков Манао наберет, если эти удвоения произойдут в самом начале игры — то есть он ответит подряд на первые X*k вопросов, а потом ни разу не сможет ответить на k последовательных вопросов. Правильность этого утверждения основывается на том, что в любом другом сценарии с X удвоениями можно сдвинуть все удвоения в начало и этим не увеличить счет. Таким образом, для X=1 Манао наберет как минимум k*2+m-k очков: ответит на k последовательных вопросов, затем счет удвоится, а затем Манао ответит ещё на m-k вопросов. Для X=2 минимальный возможный счет равен (k*2+k)*2+m-2*k, для X=3((k*2+k)*2+k)*2+m-3*k. В общем случае мы получаем формулу (2^1+2^2+...+2^X)*k + m-X*k = (2^(X+1)-2)*k + m-X*k.

Из сделанного выше наблюдения становится понятно, что счет монотонно растет с увеличением X, поэтому нужно лишь найти наименьшее подходящее значение X. Оно должно удовлетворять неравенствам X*k <= n и X + (n - n mod k) / k * (k-1) + n mod k >= m. Поподробнее о втором неравенстве: на первые X*k вопросов Манао ответил, таким образом осталось ещё n-X*k. Теперь он может отвечать максимум на k-1 вопрос из каждых k. Если бы n-X*k делилось на k (что есть то же самое, что n делится на k), неравенство имело бы вид X*k + (n-X*k) / k * (k-1) >= m, но из-за остатка формула получается более сложной: X*k + (n - X*k - (n - X*k) mod k) / k * (k-1) + (n - X*k) mod k >= m. Упрощая все что можно, получаем из неё формулу, приведенную выше. Таким образом, минимальный X равен max(0, m - (n - n mod k) / k * (k-1) - n mod k). Для вычисления счета, соответствующего найденному значению X, нужно использовать бинарное возведение в степень. Таким образом, итоговая сложность решения — O(log(n)).

337D - Книга Зла

Очевидно, что на языке теории графов перед нами стоит следующая задача — дано дерево из n вершин, m из которых помечены; найти количество вершин, расстояние от которых до каждой из помеченных вершин не превосходит d.

Давайте подвесим дерево за какую-либо вершину r, то есть будем рассматривать его как корневое дерево с корнем в r. Перефразируем условие, налагаемое на искомые вершины: нам нужно посчитать количество таких вершин v, что максимальное расстояние от v до какой-либо помеченной вершины не больше d.

Для любой внутренней вершины v, наиболее отдаленная от неё вершина находится или в поддереве v, или за его пределами — во втором случае путь от v до наиболее отдаленной помеченной вершины проходит через родителя вершины v. Используя данное наблюдение, можно быстро пересчитывать расстояния до наиболее отдаленных помеченных вершин при переходе от некоторой вершины к её ребенку.

Для начала давайте посчитаем расстояние от каждой вершины v до самой далекой от неё помеченной вершины в поддереве v. Будем называть это расстояние distDown[v]. Посчитать значения distDown[] можно с помощью поиска в глубину: для листьев дерева это расстояние или равно 0 (когда сам лист является помеченной вершиной), или условно минус бесконечности (когда лист не является помеченной вершиной), а для каждой внутренней вершины v distDown[v]=max(distDown[child1], distDown[child2], ..., distDown[childK])+1, где childi — дети вершины v.

Теперь будем считать расстояния от каждой вершины до наиболее отдаленной от неё помеченной вершины вне её поддерева. Будем называть это расстояние distUp[v]. Для вычисления значений distUp[] мы опять-таки используем поиск в глубину. Для корня дерева distUp[r] условно равно минус бесконечности, а для любой другой вершины v есть два случая — или наиболее отдаленная от неё помеченная вершина находится в поддереве родителя p вершины v, или ещё "дальше", то есть путь к ней проходит через родителя p. В первом случае расстояние от v до такой вершины равно max(distDown[sibling1], ..., distDown[siblingK])+2, где siblingi — это братья (другие дети родителя) вершины v. Во втором случае оно равно distUp[p]+1. Таким образом, distUp[v] равен максимуму из этих двух величин. Надо заметить, что для обеспечения линейной работы этого поиска в глубину в первом случае нужно найти максимальное max1 и второе максимальное max2 среди значений distDown[sibling1], ..., distDown[siblingK]. Затем, если distDown[v] < max1, тогда max(distDown[sibling1], ..., distDown[siblingK])=max1, в противном же случае, при distDown[v] = max1, мы имеем max(distDown[sibling1], ..., distDown[siblingK])=max2.

Имея значения distDown[] и distUp[], ответ найти просто: это количество таких v, что distDown[v] <= d && distUp[v] <= d.

Для иллюстрации этой идеи можете посмотреть 4302127.

337E - Дерево делителей

Для начала покажем, что единственные вершины в оптимальном дереве делителей, которые могут не содержать одного из значений a[i], это листья и корень. Допустим, у нас есть некоторая внутренняя вершина, не являющася корнем, в которой записано число X, не равное ни одному из a[i]. Тогда можно исключить эту вершину из дерева, а её сыновей "прицепить" к её родителю без нарушения какого-либо из свойств дерева.

Таким образом, наше дерево состоит из корня, прицепленных к нему или друг к другу в некотором порядке вершин с числами a[i] и идущих из них листьев, содержащих числа из их разложений на простые множители. Исключениями из этого наблюдения является ситуация, когда в корне записано одно из чисел a[i], и ситуация когда среди a[i] встречаются простые числа. Также заметим, что в общем случае количество листьев в дереве будет равнятся сумме показателей степеней простых чисел в разложении на простые множители тех a[i], которые являются детьми корня.

Так как N <= 8, можно попытаться перебрать все возможные деревья, удовлетворяющие сделанным наблюдениям. Упорядочим числа a[i] по убыванию и рекурсивно будем выбирать для каждого из них, к какой из уже имеющихся вершин добавить сына с соответствующим числом. Понятно, что чтобы добавить число X к некоторой вершине v, произведение X и чисел в сыновьях v должно делить число в самой вершине v. Для первого из чисел a[i] у нас есть выбор — сделать его корнем дерева, или сделать сыном корня (в котором будет записана условная бесконечность, делящаяся на любые числа). Для каждого следующего числа выбор заключается в том, сделать его сыном корня (если таковой присутствует как отдельная от вершина) или вершины, содержащей одно из предыдущих чисел. В сумме мы рассматриваем O(N!) вариантов.

Для иллюстрации этой идеи можете посмотреть 4302171.

338D - Таблица НОД

Наблюдение 1. Если последовательность a встречается в таблице G, то она обязательно должна встречаться в строке i = LCM(a[1], ..., a[k]). Докажем это утверждение. Понятно, что теоретически она может встречаться только в строках, номера которых кратны i, так как номер строки должен делиться на каждое из чисел a[index]. Рассмотрим некоторую строку с номером i*x, где x>1. Строки i и i*x отличаются только в таких элементах j, что i*x и j делятся на степень p^q некоторого простого числа, на которое не делится i (соответственно G(i*x, j) делится на p^q). Но ни один из a[index] на такое p^q делиться не может, потому что тогда бы и i делилось на p^q. Соответственно, если искомая подстрока находится в i*x-ой строке, то она не может содержать индекса j. Раз она может содержать только те индексы, где элементы в строках i и i*x совпадают, достаточно проверять лишь i-ую строку. Отсюда ясно, что если i > n, ответ задачи "NO".

Наблюдение 2. Искомый индекс j должен удовлетворять следующую систему линейных уравнений по модулю:

j = 0 (mod a[1])
j + 1 = 0 (mod a[2])
...
j + l = 0 (mod a[l + 1])
...
j + k - 1 = 0 (mod a[k])

<=>

{j = -l (mod a[l + 1])}

Иными словами, j + l должно делиться на a[l+1] для каждого l=0..k-1.

Согласно Китайской теореме об остатках, у такой системы есть решение тогда и только тогда, когда для каждой пары индексов x, y (0 <= x, y <= k-1) мы имеем -x = -y (mod GCD(a[x+1], a[y+1])). Положим L = LCM(a[1], ..., a[k]). Если у системы есть решение, тогда оно единственно в интервале [0, L), а все остальные решения конгруэнтны ему по модулю L. Допустим, мы вычислили минимальное неотрицательное j, удовлетворяющее данной системе. Тогда, если последовательность a встречается в таблице G, она обязательно будет начинаться с j-ого элемента строки i. Понятно, что теоретически она может начинаться с любого индекса вида j+x*L, x>=0, но i = L, поэтому G(i, j+X*L) = GCD(i, j+X*i) = GCD(i, j). Поэтому достаточно проверить, совпадают ли k последовательных элементов, начинающихся с j-ой позиции i-ой строки, с последовательностью a. Также понятно, что если j > m-k+1, то ответ задачи "NO".

Наконец, рассмотрим как можно найти решение системы линейных уравнений по модулю (и заодно проверить её решаемость, так как предложенная ранее проверка в лоб будет работать слишком долго). Для этого можно использовать следующий вспомогательный метод, которой для данных значений r1, m1, r2, m2 находит минимальное число X такое, что X = r1 (mod m1) и X = r2 (mod m2), или определяет что его не существует. Пусть X = m1*x + r1, тогда мы имеем m1*x + r1 = r2 (mod m2). Это можно представить в виде Диофантового уравнения m1*x + m2*y = r2-r1, решение которого является делом техники. Наименьший неотрицательный x, если таковой существует, даёт нам искомое X = m1*x + r1. Теперь этот метод можно использовать, чтобы найти минимальное решение X1, удовлетворяющее первые два уравнения. Теперь можно считать, что у нас уже k-1 уравнение, в котором вместо двух первых есть новое уравнение j = X1 (mod LCM(a[1], a[2])), и повторить эту же процедуру снова. Используя этот метод k-1 раз, мы получим итоговое решение для всей системы.

Заметим также, что предложенное решение не требует имплементации длинной арифметики:

— Процесс подсчета LCM(a[1], ..., a[k]) можно реализовать так, чтобы при каждом умножении проверять, не станет ли результат больше n, а в таком случае сразу выводить "NO";

— К моменту решения системы уравнений, нам уже известно что L <= n <= 10^12, поэтому все промежуточные модули также будут в этих пределах;

— Расширенный алгоритм Эвклида находит решения в тех же пределах, что и входные числа, поэтому также будет оперировать числами до 10^12.

Итоговая сложность алгоритма — O(k logn).

338E - Оптимизировать!

Оформление задачи представляет собой небольшой эксперимент, хотя я и не буду претендовать на абсолютную новизну такой идеи. Условие нужно понять из псевдокода очень медленного решения. Заключается оно в следующем: даны массивы A[1..N] и B[1..L] и число H. Нужно посчитать, сколько (непрерывных) подмассивов S массива A длины L имеют свойство — можно так перемешать элементы массива B, что каждая из сумм S[i]+B[i] (1<=i<=L) будет не меньше H.

Понятно, что задачу для каждого отдельного подмассива можно решать за время O(NlogN), если упорядочить массив B, а для каждого подмассива S упорядочить его в обратном направлении и проверить что требуемое условие выполняется. Более общая идея решения, которую можно имплементировать с такой же асимптотической сложностью — для каждого из чисел B[i], нам нужно сопоставить ему наименьшее из чисел S[j] такое, что B[i]+S[j]>=H. Заметим, что числа B[i] можно обрабатывать в любом порядке. Также заметим, что S и B можно поменять местами, то есть искать наименьшую пару для каждого S[i] в массиве B. И последнее — если S и B упорядочены заранее, то обработка сегмента производится за O(N).

При рассмотрении каждого подмассива по отдельности лучшей асимптотики не достичь, поэтому попробуем решать задачу для нескольких подмассивов одновременно. Допустим, что массив B уже упорядочен по возрастанию. Возьмем некоторое число X < L и рассмотрим некоторый подмассив A[i..i+X-1]. Давайте обработаем все числа из этого подмассива — то есть для каждого из них найдём наименьшее B[j], которое в сумме с ним не меньше H, и уберём элемент B[j] из массива B. Эту обработку можно выполнить за время O(N), если изначально иметь упорядоченный массив элементов A и соответствующих индексов: из такого массива мы можем получить элементы сегмента A[i..i+X-1] в порядке возрастания, а мы уже знаем, что имея их в таком виде и имея упорядоченный массив B, задачу можно решить за линейное время.

Теперь мы можем найти ответ для каждого подмассива S длины L, левый край которого находится в интервале [i-Y, i], за время O(YlogY), где Y=L-X. Для этого просто возьмём те Y элементов, которые входят в S и не входят в A[i..i+X-1], и обработаем их на остатке чисел из массива B. Если для каждого из этих элементов нашлась пара, то подмассив S имеет нужное свойство, в противном случае нет. Более того, хотя для каждого отдельного сегмента нам обязательно нужно O(YlogY) времени, здесь также можно воспользоваться тем, что сегменты пересекаются и получить амортизированную сложность O(Y) на сегмент. Заметим, что для обработки остатка сегмента за время O(Y) нам нужно лишь иметь его элементы в упорядоченном состоянии. Для самого левого сегмента, который мы будем обрабатывать, честно упорядочим его элементы, а для каждого следующего (который отличается от предыдущего ровно в двух элементах) нужно лишь O(Y) операций, чтобы обновить упорядоченный массив элементов. Таким образом, мы получаем сложность O(YlogY + Y^2) для обработки всех Y сегментов в сумме, что даёт O(Y) на один сегмент в среднем.

Вернемся к общей картине. Чтобы рассмотреть все подмассивы длины L, нам нужно использовать вышеуказанный алгоритм для каждого из сегментов A[Y..Y+X-1], A[2Y+1..2Y+X], A[3Y+2..3Y+X-1], .... Таким образом, мы O(N/Y) раз запускаем алгоритм со сложностью O(N+Y^2). Получается, что нам надо выбрать Y, минимизирующий N*N/Y + N*Y, откуда мы имеем Y=~sqrt(N). Итоговая сложность алгоритма получается O(Nsqrt(N)). Тем не менее, отдельно надо рассмотреть случай L < sqrt(N), потому что Y = L - X < L. Здесь задачу можно решать за время O(NL) подобной прошлому подходу идеей: упорядочив самый левый подмассив длины L, для получения упорядоченной версии каждого следующего требуется лишь O(L) операций.

Имплементацию этой идеи вы можете увидеть в 4302344.

P.S. Условие "задачи", которую решает Манао, на самом деле содержит текст одной грузинской сказки. Вы можете скопировать (почти) его отсюда и попробовать понять смысл переведенного текста :)

Разбор задач Codeforces Round 196 (Div. 2)
Разбор задач Codeforces Round 196 (Div. 1)
  • Проголосовать: нравится
  • +171
  • Проголосовать: не нравится

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

"В третьем случае картинка заполнит экран полностью, поэтому ответом задачи будет 0." Ответ 0/1

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

    Логически ответ 0. Форма, в которой его надо вывести — "0/1".

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

Общая идея по 338E - Оптимизировать! понятно, но решение с деревом отрезков попроще наверное будет: Давайте закинем все Bi со значением 1, а все Ai первого интервала со значением -1. Тогда остается только проверить что не существует префикс с отрицательной суммой, а это можно сделать деревом отрезков. Переходы по интервалам A делаются двумя обновлениями дерева.

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

Последнюю задачу можно решить проще.

Понятно, что A[i..i + len - 1] и B[0..len - 1] должны идти один в отсортированном порядке: один по возрастанию, другой по убыванию. Давайте упорядочим B по возрастанию.

Как теперь для данного подмассива A проверить, что он подходит для массива B? Будем говорить, что два числа можно спарить, если их сумма больше h. Утверждается следующее: в подмассиве A должно быть не меньше одного элемента, который можно спарить с B[0], не меньше двух, которые можно спарить с B[1], не меньше трёх, которые можно спарить с B[2] и так далее — это необходимое и достаточное условие, чтобы массивы подходили друг другу.

Давайте делать следующую штуку: по очереди обрабатываем элементы A. Пусть обрабатываем элемент x из A. Найдём, с какими элементами из B мы его можем спарить: это будет какой-то суффикс B[j..], позицию j можно найти бинпоиском h - x в B. Заведём дерево отрезков, в котором будем хранить для каждого элемента B, со сколькими A - шками его можно спарить. Тогда для очередного приходящего элемента x нужно просто увеличить значение на суффиксе на 1.

Будем двигать окошко в A, добавляя правый элемент и убирая левый (аналогично — уменьшение на суффиксе). Теперь осталось отвечать на запрос: правда ли, что первый элемент в дереве отрезков не меньше 1, второй не меньше 2 и т. д. Для этого изначально вычтем из первой ячейки 1, из второй 2, из третьей 3 и т. д., и построим дерево минимумов. Если к текущему моменту значение минимума на всём дереве не меньше нуля, то текущий подмассив A подходит, иначе нет. Пишется совсем просто — единственный запрос изменения на отрезке к дереву отрезков, даже запроса минимума не надо.

UPD: aropan выше то же самое говорит.

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

    Вот так часто и бывает — придумаешь задачу, принесешь на соревнование, а потом тебя научат её решать :)

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

Problem D(Book of Evil), I find two marked node(node a, node b) that the distance between them is longest.Then count the shortest distances from these two node. Last, for a node c, if shortest[a][c] <= d && shortest[b][c] <= d, we add 1 to ans.

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

    Could you please explain why this works?

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

      This is similar to the diameter-finding algorithm in a tree. Suppose there are nodes for which dist(a,c) < dist(c,e) and dist(b,c) < dist(c,e), where A, B and E are marked, and dist(a, b) >= dist(b, e), and dist(a, b) >= dist(a, e).

      Let's root the tree at A. We have two cases:

      1) dist(a, lca(c,e)) >= dist(a, lca(c,b))

      • dist(c,e) > dist(c,b) ->
      • dist(a, e) + 2*dist(a, lca(c,b)) > dist(a,b) + 2*dist(a, lca(c,e)).
      • dist(a, e) > dist(a, b).

      Contradiction: in this case A->E is longer than A->B.

      2) dist(a, lca(c,e)) < dist(a, lca(c,b))

      dist(c, e) > dist(a, c) -> dist(a, e) > 2*dist(a, lca(c,e))

      • dist(b, e) = dist(a, b) + dist(a, e) — 2*dist(a, lca(b,e))
      • Then we have lca(b, e) = lca(b, c), so
      • dist(b,e) > dist(a, b) + dist(a, e) — 2*dist(a, lca(c,e))
      • dist(b,e) > dist(a, b).

      Contradiction. B->E is longer than A->B.

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

        Thanks for the explanation. However it took much time from me to understand the formulas. Let me supplement it with a picture.

        C and E must lie inside the circles. Otherwise they would form a new diameter (with A or B). If they lie inside, they cannot form longer distances. C will always be farther from A or B than from E.

        UPD: In fact non-marked vertice C may lie outside the circle, as our diameter is formed by marked vertices only. However E inside the circle is sufficient. Image updated.

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

          Yes, that's the intuitive idea, but the circle is not exactly as drawn. For instance, take the midpoint of A-B and extend E to the same height as B. That is still a valid configuration. Another way to see it: if A and B are equivalent, shouldn't the valid region be symmetric with respect to the midpoint?

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

            The circle touches the midpoint only accidentally. It is drawn as follows: let D be lca(E, B). D is the circle's center and its radius is distance DB. Why B? Because B is closer. Actually I should also draw another circle with radius DA, but since it's bigger (in this case), I skipped it. I draw a circle based on the closer point — A or B, because this one is smaller.

            Of course there are other cases, but for E starting at this point — I think the circle is correct. Am I missing something?

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

Problem B: If the two ratios can be made exactly same, answer would be 0 and hence we can print 0/x, for any x>0 [as per problem statement:"p/q", where p is a non-negative integer, q is a positive integer and numbers p and q don't have a common divisor larger than 1.] but they accepted only 0/1. This is not fair. 0/x, for any x>0 is a proper reduced form. Wasted an an entire hour on this.

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

    0 divides by any number, so for any p>1, "0/p" has a common divisor larger than 1.

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

Sorry, Wrong Language :(

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

Why this entry is in Codeforces main page?

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

Решал D-шку и нужно было найти две самые удаленные вершины в графе. Нашёл в интернете это: сначала делаем обход из любой вершины, ищем самою дальнюю вершину от начальной, из неё снова обход, который определит две самые удаленные вершины. сложность O(N). Кто может объяснить почему это правильно???

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

    Это только для дерева работает. Для дерева доказывается несложно от противного.

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

Thanks for ur nice work.All the problems are interestring and easy to understand.

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

Вопрос для понимания в задаче DIv1B. Для одной вершины мы храним только 3 значения distUp[v], max1[v],max2[v]. distDoun[v] выражается через max1?

И еще нет ли авторского кода?

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

    Нет, храним мы в итоге только distUp[v] и distDown[v] (в принципе можно массив distUp[] вообще явно не хранить и передавать внутрь DFS-а). max1 и max2 нужны только локально. Вот код, соответствующий разбору: 4302127

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

Почему в задаче B-Div2 если a/b < c/d , то картинка заполнит всю горизонталь ?

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

The description of last problem solution is complicated.

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

ignore

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

Hello, int problem 337E, I wonder why the numbers should not be same?

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

    This is just for the sake of simplicity of the statement. I.e., if duplicate numbers are allowed, you can either ask for a tree that contains the numbers at least as many times as they are given in the input, or just ask to ignore the duplicates. The problem does not become more interesting in any case.

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

Edit: Got my mistake.

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

Спасибо за разбор задачи_)

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

337D — Book of Evil

I use a different idea. My idea:

1.Find two settlements a and b which are affected and dis(a,b) is maximum among all affected settlements.It can be easily done by diameter of tree.

  1. Evil has got a damage range d. So how many nodes can be visited from a by distance d and from b by distance d.Now the number of common nodes which can be visited from a and b by distance d is answer.It can be done easily by dfs and colouring.

my solution: http://codeforces.com/contest/337/submission/11410528

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

Is there a way to solve Div2 A(337A) using 2-D dp?
If yes, can someone explain it to me please?

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

In problem 337A how is the difference of greatest and smallest element obtained as F [k+n-1]-F[k]?

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

I really spent an hour finding the bug in my code in 2C and then I realized that it was 10e9+9 and not 10e9+7.

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

Didn't notice in Div2E(Divisor Tree) that $$$n \le 8.$$$ I misread it as $$$n \le 12$$$ and found an $$$O(4^n)$$$ solution. This approach doesn't seem to have been discussed in the comments. I never faced a problem before that required iterating over subsets of subsets of subsets, so I think it's worth a mention.

  • We start with the following easy observation copied from the editorial:

    In an optimal divisor tree only the root or a leaf can hold a value other than one of $$$a[i].$$$

    Hence, our tree consists of the root, vertices with numbers $$$a[i]$$$ tied to each other or to the root, and leaves, which are tied to vertices with numbers $$$a[i]$$$ and contain these numbers' prime factorizations.

  • Let's consider each subset of the set of $$$n$$$ numbers as a mask. Let, dp[up_mask][down_mask], where up_mask and down_mask are disjoint, be true if there exists a tree where the numbers corresponding to up_mask are direct children of the root and the numbers corresponding to down_mask lies in subtrees of the up_mask numbers.
  • Now, to evaluate dp[up_mask][down_mask], we split up_mask into two smaller sets,
    up_lsb = least significant bit of up_mask, and
    up_rest = up_mask ^ up_lsb.
    Then, we iterate over all possible ways to split down_mask into two partitions down_mask1 and down_mask2, and check if we can put down_mask1 under up_lsb and down_mask2 under up_rest by checking if both dp[up_lsb][down_mask1] and dp[up_rest][down_mask2] are true.
  • To get our final answer, we first set our answer ans as the sum of the exponents in prime factorizations of the given numbers.
    We then iterate over all subsets of $$$[(1 \lt\lt n) - 1]$$$ as up_mask and set down_mask = $$$[(1 \lt\lt n) - 1]\ \oplus$$$ up_mask. If dp[up_mask][down_mask] is true, then we consider it as a candidate answer and subtract the sum of exponents in prime factorizations of the down_mask numbers from ans.
  • Total states in the dp is $$$O(3^n)$$$ and considering transitions, time complexity becomes $$$O(4^n).$$$ And the memory complexity is $$$O(4^n)$$$ for dp. Here is a submission using this idea.
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In 337C Quiz
Can anyone please explain how X*k + (n-X*k) / k * (k-1) >= m= X + (n - n mod k) / k * (k-1) + n mod k >= m whereas I reduced it to X+(n/k)*(k-1)>=mwhich gives WA.
Thank you.

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

Hey guys,I tried this problem but somehow I am facing TLE on case#4.I am pretty sure that my code is having O(n) or O(V) time complexity.Please help me figure out where exactly am I going wrong. Link to my code:https://codeforces.com/contest/337/submission/80845068 Thanks in advance

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

In Div2-A Book of Evils. Can someone please explain why we use neg infinity and not positive infinity. because I'm confused by the fact that farthest marked node will be too far(i.e. positive inf).

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

Anyone solved 337A - Puzzles using graphs??

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

How can we use binary search to find x? Although I understood how does the formula work, it's true that most of the times binary search is easier to come up with than the formula.

Thanks.

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

Can Problem D ( Book Of Evil ) be solved using centroid decomposition ??

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

h*W/w = w*c/d * W/w = W*d/c this is from the tutorial but isn't this should be h*W/w = w*d/c* W/w = W*d/c

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

h*W/w = w*c/d * W/w = W*d/c should n't be this be h*W/w = w*d/c * W/w = W*d/c

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

If a/b > c/d how can we say that width will always fit first or if a/b < c/d the height will fit first. Can anyone tell?