Недавно на Codeshef была подобная задача. После раунда я погуглил и оказалось, что ответ равен N × (1 + 1 / 2 + ... + 1 / N)

Помогите найти неправильную логику в рассуждении: Если не знать что задача баян, то можно посчитать МО по ее определению для дискретного случая: MX = sum(x, p), где x — величина, p — ее вероятность. Тогда напишем dp[i][j] — вероятность того что мы на i билетов соберем j призов. При этом мы знаем что dp[0][0] = 1; p = 1 / n — вероятность приза в каждом билете q = 1 - p — вероятность его отсутствия

переходы:

dp[i][0] = dp[i-1][0] * q;

dp[i][j] = dp[i-1][j-1] * p + dp[i-1][j] * q; для j = 1..n-1

dp[i][n] = dp[i-1][n-1] * p ;

Что я упустил? PS: проблема в том, что такая логика даже для n = 2 дает ответ 4.0

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

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

Посчитаем динамикой по поддеревьям самый выгодный путь вниз для каждой вершины. Теперь осталось перебрать все вершины и найти самый выгодный маршрут (либо строго вниз от зафиксированной вершины, либо сначала вверх до зафиксированной вершины, а потом вниз).

Код

заведем массив cnt[10^5], cnt[i] — сколько было чисел i и массив mx[500], mx[i] — максимальное из чисел левее, делящихся на i.

теперь будем идти слева направо и поддерживать эти массивы.

пусти мы стоим в позиции idx и val == a[idx];

тогда если val <= 500, то возьмем ответ из mx[val], иначе пойдем семимильными шагами

for(int j = val; j <= 1e5; j += val) if(cnt[j] > 0) ans = max(ans, j);

теперь осталось обновить массивы. ну так и делаем cnt[val]++;

for(int i = 1; i <= 500; i++) if(val % i == 0) mx[i] = max(mx[i], val);

Можно завести массив множеств индексов sorted_sets[10^5], и для каждого элемента a[i] занести его индекс во все sorted_sets[d], где a[i] % d == 0.

Теперь для i-го элемента индексы кратного слева и справа хранятся в sorted_sets[a[i]], достаточно взять из него наибольший индекс, меньше i (или i, если такого нет), и наименьший индекс, больше i (или также i).

Такое решение работает за O(N * sqrt(maxA) + N * logN) с достаточно несложной реализацией.

Вроде как есть решение за NK, где K — максимальное число делителей чисел от 1 до 10⁵. Изначально предпосчитаем все делители всех чисел за , где A = 10⁵. Идем сначала слева направо и поддерживаем массив index[x], самое правое число делящееся на x. Пересчитывается это очень просто, пробегаемся по делителям текущего числа и обновляем массив. Аналогично пробегаем справа налево. Код.

Раунд длится 1:20. Да, правила TCM/Time.

У меня возникло ощущение, что заходило любое работающее решение, там какие-то тесты в стиле американских полуфиналов или SWERC :)

У меня есть наивное решение за O(N² * log(N)) — рассматривая запрос, подорвем все, что взрывается сразу; если от этого еще что-то сдетонирует — подорвем его; если от этого что-то еще сдетонирует — опять подорвем его... И так будем итерировать, пока что-нибудь взрывается.

Upd. С помощью sparse table из него даже можно сделать чистый квадрат :)

То ли у ребят с Яндекса весьма мощные сервера, то ли тесты ни о чем — в системе это решение работает за 1.3 секунды. При том что мое с контеста работает за 1.8 :)

Ну а локально у меня такой брут немного не укладывается в ТЛ — на одном худшем тесте из 100000 точек отработал за 1 час 51 минуту 55.167 секунд.

Шутки в сторону, вроде бы можно так:

За O(N * log(N)) сожмем все пути вправо; за O(N * log(N)) сожмем все пути влево. Теперь на запросы можно отвечать наивным итерированием, примерно так же, как и в описанном выше решении за квадрат. Так как теперь каждое расширение в запросе может быть только большим (перепрыгивающим через середину отрезка и расширяющим его с другой стороны), то всего их будет мало. Это должно дать нам что-то вроде O(N * log²(N)). Если дописать сюда update'ы полученными результатами и random_shuffle порядка запросов, то есть вероятность, что это работает даже лучше:)

P.S. Ну да, опять можно прикрутить sparse table — и убрать в начальной идее один логарифм.

Нормальное решение можно почитать, например, здесь.

Делаем ровно то, что написано в условии. Просят посчитать (A * B)^N * N, значит посчитаем. Чтобы не было проблем с TL, запишем это как A * B * A * B * ... * A * B = A * (B * A)^{N * N - 1} * B, чтобы возводимая в степень матрица была маленькой; дальше быстрое возведение в степень, умножение матриц по определению и т.д. — сразу делаем все необходимые вычисления по модулю 6, в конце считаем ответ.

В ней самое сложное — понять условие:) Организаторы хотят записать результаты бросков как число в k-ичной системе счисления, и поделить все возможные числа между N участниками поровну. Так как всего таких чисел kⁱ, то нас спрашивают — при каком минимальном i число kⁱ делится на N. Понятно, что если kⁱ все еще не делится на N для какого-то достаточно большого i, то оно никогда не будет делиться, поэтому достаточно проверить первые несколько степеней. Вроде бы при таких ограничениях худший тест это 536870912 2, где ответ 29, но лучше перебирать с запасом.

Можно поймать минус на том, что для n=1 ответ всегда 0.

Я не понял — это действительно кому-то интересно, или тебя заплюсовали за тонкий юмор? :)

На всякий случай — я записал скринкаст раунда 4. Регулярно это делать не планирую, я не Petr, не Egor и не tourist, и не (ставим сюда имя любого другого классного участника, для которого это имело бы смысл), но ведь один раз попробовать можно:) Пусть будет, если это кому-то интересно.

По понятным причинам, я не могу выложить сам скринкаст до окончания раунда. Если в Петрозаводске будет возможность — выложу оттуда. Иначе придется подождать еще несколько недель, пока я вернусь.

Upd. Спасибо добрым людям, которые мне только что объяснили — можно уже сейчас выложить на Youtube, а потом только снять ограничения конфиденциальности :)

Не знаю, можно ли проще. У меня такое:

Воспользуемся тем наблюдением, что перед нами одна из модификаций транспортной задачи; только цены выброшены:) Очевидная часть — поскольку из параметров у нас только ограничения на пропускные способности, то существование решения можно проверить, пустив поток. В левую долю столбцы, в правую строки, клетки заменяем ребрами.

Теперь, видимо, менее очевидная часть — ведь нам еще нужно научиться проверять, единственное ли решение. Как мы знаем, все множество решений связно по перераспределениям, поэтому если мы нашли какое-то решение (потоком), то либо можно получить из него какое-то другое валидное решение, сделав одно перераспределение, либо же решение единственное.

Понятно, что перераспределять достаточно единичку. Если можно перераспределить больше, то можно перераспределить и единичку. Нам нужно найти цикл (по аналогии с любой вариацией метода потенциалов), по которому можно перебросить эту единицу. Это должна быть последовательность "делаем в клетке +1 — движемся по строке — делаем -1 — движемся по столбцу — делаем +1 — движемся по строке...", которая начинается и заканчивается в одной и той же клетке; либо же аналогичная последовательность, в которой + и — поменяли местами.

Наивно искать такую последовательность слишком долго. Но можно вспомнить, что каждому такому циклу отвечает цикл в двудольном графе из строк и столбцов. Предположим, что перед движением по строке у нас +, перед движением по столбцу -. Тогда у нас есть дуга из строки в столбец, если на их пересечении можно уменьшить число, и дуга из столбца в строку, если на их пересечении можно увеличить число. Теперь для проверки достаточно найти нетривиальный цикл в полученном двудольном графе. Так как в нем О(N * M) ребер, то с этим проблем не возникает. Ну и если бы нужно было показать, что решение не единственное, построив две различные валидные матрицы, то надо взять полученную потоком матрицу, и сделать в ней перераспределение по найденному нами циклу.

Уникальность можно проверить вот так:

int fixedRow = 0;
int fixedCol = 0;
for (int i = 0; i < n; i++) {
	if (rs[i] == 0 || rs[i] == 9 * m) {
		fixedRow++;
	}
}

for (int i = 0; i < m; i++) {
	if (cs[i] == 0 || cs[i] == 9 * n) {
		fixedCol++;
	}
}

out.println((fixedRow >= n - 1 && fixedCol >= m - 1) || fixedRow == n
		|| fixedCol == m ? "Unique" : "Multiple");

Если доска из 4 строк:

Белые выигрывают, если суммарное количество единичных ходов нечетно, либо если количество столбцов, где доступны двойные ходы, нечетно.

Если строк не 4:

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

"Бесполезные" столбцы выбрасываем. В них не имеет смысл ходить, пока есть другие ходы, потому что любой ход в нем создал бы "плохой" столбец (кроме случая с 5 строками и двойного хода, но такой ход тоже не имеет смысла). Если остались только "бесполезные" столбцы, то тот игрок, чей сейчас ход, проиграл. Это эквивалентно отсутствию "бесполезных" столбцов.

Далее совершаем ходы каждым игроком по очереди согласно такой стратегии:

1. Хорошо бы избавиться от "плохих" столбцов. Если такой есть, походим там, если их несколько, походим в том, где расстояние между пешками минимально.

2. Если плохих столбцов нет, но есть хотя бы один хороший, то мы делаем победный ход в нем. А именно, такой, чтобы суммарное количество единичных ходов стало четным.

3. Если нет ни "хороших", ни "плохих" столбцов, то победитель определяется по четности количества оставшихся ходов.

C:

Пусть координаты введены так, что все прямые параллельны оси OY. Если фиксирован угол, под которым упадет тарелка, то искомая вероятность  –  ее ширина (назовем это диаметром при данном угле) в проекции на ось OY, деленная на D.

Ну чудно, отсюда уже следует нормальное решение  –  можно вращать многоугольник, поддерживая диаметр, ответ  –  матожидание диаметра, деленное на D.

Правда за 7 минут вряд ли пишется. Зато пишется "возьмем 20 000 углов, найдем диаметр при многоугольнике, повернутом на этот угол, добавим к ответу". Заходит.

В C как обычно хорошие тесты и заходит периметр выпуклой оболочки делить на π D , как нормально за 7 минут написать мне тоже интересно.

Как-то так

В D с точки зрения тестов тоже дела обстоят не очень. У меня зашло такое решение (писал уже в самом конце, придумать ничего лучше не успел):

Интуитивно кажется, что нам бы в идеале иметь цепочку чисел типа 1, 2, 3, ... как в первом примере, тогда мы сможем их все собрать и получить N очков. Соответственно первым шагом я перевел каждого монстра в ближайшее к его здоровью незанятое число, меньше чем само здоровье. Т.е. например массив 1, 2, 3, 6, 6 превращается в 1, 2, 3, 5, 6. Некоторые числа могут при этом превратиться в 0, их можно выкинуть сразу. Дальше для каждого оставшегося числа считал сколько понадобится ходов, чтобы "собрать" это число и получить за него очко. Это значение для числа равно 1 + (на сколько мы уменьшили число на прошлом шаге). Получаем значения стоимостей каждого возможного балла. Плюс добавляем ограничение для каждой стоимости, что мы можем ее собрать только в течение первых h ходов, где h — изначальное здоровье монстра, в противном случае этого монстра убьет волшебник. Получились пары значений (стоимость в ходах)-(максимальный ход, к которому надо успеть эти ходы сделать). Эти пары пихаем в подобие рюкзака, это дает ответ.

Я сам очень удивился, что это зашло, потому что ни подумать, ни проверить никак не успел. После контеста мне написал I_love_Tanya_Romanova и сказал, что у него похожее решение и она неправильное, его сокомандник показал контрпример. Это решение не учитывает, что нельзя пропускать ходы и на тесте:

2 2 3

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

У меня есть мысль, что это решение можно допилить, чтобы оно проверило такой случае и все-таки выдало правильный ответ, но по факту у нас зашли неправильные решения. Я не знаю, есть ли подобный тест в тестах контеста, было бы интересно узнать, не на нем ли остальные участники получали WA.

Правильно прочитать условие. Ключевая фраза — "остался без единой монеты". Т.е. у него в начале нет денег и в минус он уходить не может. Значит надо жадно посещать города в порядке возрастания b[i], если они не ухудшают баланс

И ещё задачу А.

C без бинпоиска вроде можно, там же ограничение на координаты (и на ответ соответственно) — 10⁵, так что можно просто таскать квадрат по всем сторонам и при возможности увеличивать его размер на единичку. Главное по каждой новой стороне тащить квадрат размера, на котором остановились в прошлый раз. Тогда независимо от того, как вы будете обходить стороны, квадрат не увеличится больше 10⁵ раз. Но с бинпоиском вроде должно быть проще.

Я в дорешивании сдал такое решение: делаем динамику, внутри перебираем сколько мы пропихаем путей в текущего сына i и сколько из этих i путей уже существует j. Остальные пути мы должны создать. Это конечно TL, но оказывается что j достаточно перебирать до 2. Получается куб.

Возможно, есть более простые/приятные решения, но можно так, с помощью дерева отрезков:

Построим дерево отрезков по числам, которое будет знать, сколько сейчас вхождений каждого числа в последовательность. Теперь достаточно заметить, что запрос дублирования на сколько-то увеличивает число вхождений крайних чисел, а для всех внутренних (таких, все вхождения которых покрыты этим запросом) соответствует умножению числа вхождений на 2. Запрос максимума, в свою очередь, можно разбить на аккуратное рассмотрение краев (чисел, которые частично покрыты запросом) и запрос к дереву отрезков на максимум по полностью покрытым числам.

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