6 этап X Открытого Кубка по программированию - Гран-При Европы

13 лет назад, # |

+10

J - втупую. Пусть мы хотим разбить дерево на куски размера X. Тогда нетрудно заметить, что ребро соединяет разные куски тогда и только тогда, когда размеры поддеревьев, на которые оно разбивает всё дерево, кратны X. Для каждого ребра найдём размеры поддеревьев, которые оно соединяет и проверим, делятся ли они на X. Если хороших рёбер ровно n/X - 1, то разбить на куски по X можно, иначе - нет. Ну и заметим, что обход по дереву нужен только один, потом уже по этой информации пересчитываем ответ для всех X.

→ Ответить

13 лет назад, # ^ |

← Rev. 7 →

Кому втупую, а кто сначала долго не мог победить ML2, хотя по всем расчётам выходило не более 100 Мб, а потом - TL3, когда на вроде бы худшем тесте (цепочка длиной 2042040) работало 4 с.
OpenCup - хитрый турнир, тут что ни контест, то чудеса :)

UPD. Короче, с пояснениями ниже всё стало более-менее понятно. Но если такие проблемы возникали у пишущих на C (уже даже не на C++!), то я боюсь представить, как пришлось оптимизировать решения командам, пишущим на Java.

→ Ответить

oversolver

13 лет назад, # ^ |

вроде бы худший - 2882880

→ Ответить

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

← Rev. 3 →

Ну, в справедливость TL ещё как-то можно поверить. Но непроход по памяти таки остаётся загадкой. Собственно, вот, например, код. Откуда там 256 Мб?
Или я неправильно понимаю, что при вызове функции на стеке выделяется память только под локальные переменные и адрес возврата?

→ Ответить

13 лет назад, # ^ |

Ещё как минимум там будет адрес текущей команды. Плюс возможно наличие промежуточных переменных, которые явно не объявлены. Плюс я не уверен в том, что на проверяющем сервере адреса 4-битные. В сумме может и накопиться на 256мб.

→ Ответить

13 лет назад, # ^ |

Считали с поправкой на возможную восьмибайтовость адресов. Но вот промежуточные переменные - они, видимо, всё и испортили.
Интересно, кстати, а можно ли было бы отключить их создание посредством каких-нибудь директив препроцессору? И сильно ли это ухудшило бы время работы?

→ Ответить

Lepetrandr

13 лет назад, # ^ |

Решение будет получать TLE, даже если избавиться от dfs'а. Там вся веселуха с кэшем во время обхода дерева. Если делать обход на каждый делитель (хоть dfs'ом, хоть обычным проходом по массиву, как у меня) - TLE. Stigius не зря отметил, что в его решении обход дерева выполняется единожды. И если принять во внимание кэш, то худший тест - это совсем не цепочка. При обходе цепочки 1->2->3... обращения к памяти как раз последовательны. А вот если перенумеровать ее вершины случайным образом, то время заметно возрастет.

→ Ответить

Urbanowicz

13 лет назад, # ^ |

Три миллиона вызовов malloc отберут около 50 мегабайт под свои нужды.

→ Ответить

13 лет назад, # ^ |

← Rev. 6 →

дубль

→ Ответить

13 лет назад, # ^ |

Не знаю. У нас проблем не было. Просто мне кажется, у кого-то не оптимальное решение. Насколько я понял обсуждается решение за N*количество делителей. А можно за N + сумма числа делителей у чисел от 1 до N. И это вроде бы даже просто N. Заходит спокойно.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Я сдал за O(N + D²), где D - число делителей N → Ответить

13 лет назад, # ^ |

Ну видимо это тоже самое, только мы много лишнего считали.

→ Ответить

Jacob

13 лет назад, # ^ |

+20

Для того, чтобы удовлетворить любопытных читателей, я всё-таки напишу здесь решение за O(N+D²):

1) Сгенерим N чисел: a[i] = 1 + количество узлов во всех потомках i-го узла (совсем все, а не только непосредственные)

Заметим, что для каждого делителя n нас интересует количество чисел среди a[i], делящихся на этот делитель.
2) Рассмотрим b[i] = gcd(a[i], N). Как ни странно, он является делителем N. И что самое главное - для любого общего делителя N и a[i] (назовём его k) выполнено условие b[i] % k = 0

3) Посчитаем все различные b[i] (совсем по тупому - будем хранить, сколько раз встретился каждый элемент). Заметим, что различных чисел b[i] не больше, чем делителей N.

4) Научимся для фиксированного делителя N находить описанную перед п. 2 величину. Для этого просто переберём все различные значения b[i] и для тех, которые делятся на выбранный делитель возьмём посчитанное количество их вхождений в b.

Первые три шага - за O(N), последний - за O(D^2).

→ Ответить

13 лет назад, # ^ |

Еще один вопрос, может ли получиться так, что количество "хороших" ребер будет больше чем n / X - 1?

Можно ли в таком случае разбить дерево на куски размера X?

→ Ответить

13 лет назад, # ^ |

Если мы разрежем дерево по хорошему ребру на два, то нетрудно заметить, что в полученных поддеревьях все хорошие рёбра также останутся хорошими. Таким образом, если мы разрежем по всем хорошим рёбрам, то у нас получатся компоненты, каждая размера, кратного X. Поскольку всего вершин n, то таких компонент может быть не более n/X, т.е. хороших рёбер n/X - 1. Собственно, поэтому при равенстве и есть разбиение ровно по X.

→ Ответить

Egor	13 лет назад, # ^ \| +5 А вот мое решение → Ответить

Narg	13 лет назад, # ^ \| 0 На яве в человеческом решении проблема было только в трёх миллионах = new ArrrayList<Integer>(); На списках вошло без проблем. → Ответить

13 лет назад, # |

Может кто рассказать решения интересных задач? Т.е. A, B, I.

→ Ответить

Lepetrandr

13 лет назад, # ^ |

Любую последовательность целых чисел можно разбить на последовательные куски, числа внутри каждого из которых образуют свою арифметическую прогрессию. Причем каждый такой кусок будет пересекаться с соседними ровно одним крайним числом. Разве этого не достаточно чтобы свести задачу к баяну "найдите наибольший прямоугольник состоящий из единичек на 01-матрице" за O(NM)?

→ Ответить

13 лет назад, # ^ |

Это сведение сразу провёл. А вот с этим баяном ни разу не встречался, потому чего с ним дальше делать, с ходу не придумал.

→ Ответить

vitar

13 лет назад, # ^ |

А могу.

будем считать клетку матрицы хорошей, если она находится строго внутри некоторой прогрессии как по горизонтали, так и по вертикали. Т.е. a[i][j] == (a[i-1][j] + a[i+1][j]) / 2 == (a[i][j-1] + a[i][j+1]) / 2. Составим матрицу в которой еденичками будут помечены все хорошие клетки и ноликами плохие. Решим стандартную задачу о поиске максимальной подматрицы только из едениц перебирая все нерасширяемые подматрицы из единиц. Очевидно, что все перебраные в процессе матрицы нам подходят. Но помимо них нам возможно подходят и несколько более расширенные матрицы. А именно мы к каждой матрице из единиц возможно можем с каждой стороны дописать ещё по строке(столбцу). Но не более одной. Иначе нашу матрицу из единиц можно расширить. Проверим для каждой нерасширяемой матрицы 2^4 вариантов дописывания строк по бокам. Из всех выберем максимальный.

По крайней мере это наше решение.

→ Ответить

mr146

13 лет назад, # ^ |

В. Рассмотрим 2 крайних пути из первой вершины запроса в вершину N - то есть по самый левый и самый правый. В силу условий достижимости из и до крайних вершин (1 и N) делаем вывод, что вторая вершина должна быть достижима из первой, а для этого достаточно чтобы вторая вершина лежала внутри многоугольника с границами-путями, которые мы рассмотрели. А для этого достаточно посмотреть, что поднявшись на сколько-то вверх и сдвинувшись на сколько-то вправо из второй вершины мы пересечем наши пути. Мы это делали аналогом двоичного подъема из первой вершины. Как-то так.

→ Ответить

13 лет назад, # ^ |

I. По инвертируем ребра. Задача стала такой: найти анти-клику максимального веса.

Построим сеть: из истока ребра в первую долю пропускной способностью IQ, ребра которые есть в инветированном графе пропускной способностью +inf, ребра из второй доли в сток пропускной способностью IQ. Найдем в графе макс поток. Утверждается, что если посмотреть на мин. разрез то станет очевидно, что он - минимальная сумма людей которых мы не возьмем.

Кстати, простые потоки проходили или я Диница не зря сразу писал?

→ Ответить

NALP	13 лет назад, # ^ \| 0 прошло масштабированием → Ответить

ilyakor

13 лет назад, # ^ |

Прошёл простой поток с bfs. Пробовать совсем простой с dfs у нас наглости не хватило :)

→ Ответить

13 лет назад, # ^ |

Еще одна вариация на тему А.

Будем считать клетку хорошей, если она левый верхний угол маттрицы 3*3, которая хорошая.

Надо найти квадрат из единиц максимизируя (w+2)*(h+2). Переберем верх. Будем перебирать низ, параллельно насчитываю битовую маску тех, которые единички во всей полоске. Осталось найти самую длинную подстроку из 1 в полоске, что делается предподсчетом всего для масок от 0 до 2: 16 - 1. Это получает ТЛ14. Заметим, что длина которую мы считаем только уменьшается при добавлении новых строк. Значит если она слишком маленькая даже если останется такой же до конца, то надо сделать break. С таким отсечением по ответу зашлою

→ Ответить

13 лет назад, # |

← Rev. 2 →

Как решать задачу E, написал корневую декомпозицию, получаю WA4?

UPD В дорешке зашло.

→ Ответить

13 лет назад, # ^ |

Если коротко: нам нужно находить изменения при удалении/добавлении плеера. Эти изменения - это те норы, до которых он достаёт за вычетом тех, которые достают соседи. Соседей находить легко, если держать все плееры в сете. Находить количество сусликов, которые попадают в отрезок - бинпоиском.

→ Ответить

hydrastuff

13 лет назад, # ^ |

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

Пусть хотим удалить плеер стоящий в x, найдем ближайщий от него плеер слева и справа, пусть их координаты x1, x2, тогда наш плеер затронет норы на отрезке

[max(x1+L+1, x-L), min(x2-L-1,x+L)]

Номер норы по X, можно искать бинпоиском. Добавление аналогично.

→ Ответить

13 лет назад, # ^ |

+13

а мы писали дерево отрезков с прибавлением на отрезке, с минимумом и количеством минимумов. Нужно просто уметь считать кол-во нулей во всем дереве. Будем в дереве поддерживать, сколько плееров покрывают нору.

→ Ответить

Jokser

13 лет назад, # ^ |

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

→ Ответить

13 лет назад, # ^ |

я бы не рискнул такое решение писать, большой шанс получить ТЛ, а потом заниматься неассимптотической оптимизацией

→ Ответить

Jokser

13 лет назад, # ^ |

-6

13 секунд же TL был. А операции простые - итерации, да суммирование. Я вообще сначала порывался квадрат загнать :)

→ Ответить

13 лет назад, # ^ |

все же 500000 пугают:)

→ Ответить

AlexanderBolshakov

13 лет назад, # ^ |

А я тебя остановил :)

→ Ответить

13 лет назад, # |

← Rev. 2 →

Красивое решение

UPD не туда.

→ Ответить

Jokser

13 лет назад, # |

Как решать F и G ?

→ Ответить

13 лет назад, # ^ |

Посчитать динамику d[i][j] - куда придем из сида i, если сделать 2^j шагов и h[i][j] - хэш битовой последовательности, которую мы получим, если начнем в сиде i и выпишем 2^j битов.

Дальше, для каждого сида посчитать хэш, если сделать n шагов и сравнить с данным.

→ Ответить

fetetriste

13 лет назад, # ^ |

Надо заметить, что лучше поменять индексы местами: массивы 17 × 10⁶ и 10⁶ × 17 весьма отличаются друг от друга. Особенно если это массивы массивов в яве >.<

→ Ответить

13 лет назад, # ^ |

Можно заметить, что двумерный массив необязателен и обойтись только O(M) памяти

→ Ответить

13 лет назад, # ^ |

-10

F. Жадность. Посортируем команды по убыванию d_i. По очереди сначала попробуем запихнуть куда-то 5· d_i, если не получилось то 3· d_i и 2· d_i. Каждый раз выбираем прищепки которых меньше всего, но достаточно для этих вещей. Это можно делать так: когда поюзали цвет объеденили его со следующим снмом. Тогда найти цвет = бин.поиск + максимум в множестве.

→ Ответить

dalex

13 лет назад, # |

Кто нибудь знает 8 тест в задаче K?

→ Ответить

13 лет назад, # ^ |

Может быть все точки лежат на одной прямой?

→ Ответить

dalex

13 лет назад, # ^ |

-8

Ох блин, я понял ошибку, это снова опечатка в одном символе

→ Ответить

13 лет назад, # ^ |

у нас был ВА, когда не учитывали, что два коллинеарных вектора компланарны с любым другим. из-за этого иногда был YES вместо NO

→ Ответить

kostya_by

13 лет назад, # |

Расскажите, плз, как решать Q.

→ Ответить

13 лет назад, # ^ |

Я затолкал обычный bfs с таким отсечением: не включаем фонарь, если слева и справа от него фонари выключены.

→ Ответить

kostya_by

13 лет назад, # ^ |

Можно по-подробнее?

→ Ответить

13 лет назад, # ^ |

Ну делаем поиск в ширину. Сначала в очередь кладём битмаску начального состояния. Потом все битмаски, которые получаются из неё за один ход, и т.д. Ну и с учётом отсечения, о котором написано выше.

→ Ответить

13 лет назад, # ^ |

странно, с такой же оптимизацие не зашло... поставил отсечение по итерациям-прошло

→ Ответить

Hohol

13 лет назад, # ^ |

Что такое отсечение по итерациям?

→ Ответить

13 лет назад, # ^ |

ну просто считаю итерации и смотрю, если количество итераций стало больше какой-то константы(в этой задаче например 10⁸) то прекращаю выполнение, несмотря на то, что алгоритм еще должен поработать

→ Ответить

13 лет назад, # ^ |

У меня была мысль отсекать по клоку, но я постеснялся. Видимо, зря:)

→ Ответить

13 лет назад, # ^ |

ф-я clock() вроде на ejudge'e 0 всегда возращает

→ Ответить

Vaness

13 лет назад, # ^ |

Ты неправ. сlock() на ejudge'e работает вполне нормально.

→ Ответить

13 лет назад, # ^ |

-14

Я не раз пихал с помощью клока. Например, вместо Гаусса какого-нибудь Зейделя.

→ Ответить

13 лет назад, # ^ |

Хм, а ответ-то ты какой тогда выводишь?

→ Ответить

13 лет назад, # ^ |

-14

Утверждается, что ноль хотя бы один раз поапдейтится за это время.

→ Ответить

13 лет назад, # ^ |

А что, bfs несколько раз обходит одну и ту же вершину???

→ Ответить

13 лет назад, # ^ |

-14

Я лично писал bfs с апдейтами

→ Ответить

13 лет назад, # ^ |

Можешь объяснить, что это значит, на примере задачи Q?

→ Ответить

13 лет назад, # ^ |

-13

Вот как он у меня был написан. Я прибавлял единицу в маске и делал этот переход равным единице. После этого я отнимал все лишние единице в маске и делал этот переход равным нулю.

→ Ответить

13 лет назад, # ^ |

================================

А почему бы просто сразу не делать единичный переход в итоговое состояние фонарей?

Но даже если так, всё равно не понимаю, зачем тебе ноль обходить несколько раз. Встретил ноль - и сделал break.

→ Ответить

13 лет назад, # ^ |

Я долго подбирал константу, не идем в те состояния в которых количество включенных лампочек больше чем изначальное количество включенных лампочек + 8

→ Ответить

tunyash

13 лет назад, # ^ |

У нас вообще тупой бфс зашел. Просто написали свою очередь и битсет.

→ Ответить

Hohol

13 лет назад, # ^ |

← Rev. 2 →

Простой бфс у меня получил ТЛ. Тогда я придумал следующую оптимизацию.

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

→ Ответить

daftcoder

13 лет назад, # |

← Rev. 2 →

Мне очень интересно, что за тактика была у команды Moscow SU Chapelnik: Shteiner, Panin, Blinov (div. 2), что в середине первого часа контеста они сделали три посылки по трём разным задачам в 0:41, 0:42 и 0:43.

Последняя успешная посылка была в 0:16. Затем во сколько-то одно бревно по Q, и три синхронные (но неудачные) посылки по разным задачам через 25 минут после предыдущего АС.

Может, конечно, два раза задачей ошиблись)

→ Ответить

13 лет назад, # ^ |

+10

Могу ответить.

Мой сокомандник писал H. Я его прервал, на 41й заслал простой фикс по Q. Потом он заслал Н не туда. Потом туда.

Стоит ли говорить, что все три сабмита были неудачными.

→ Ответить

daftcoder

13 лет назад, # ^ |

Ну да, об этом тоже думал. Но код чужих сабмитов (вроде?) никак не посмотреть.

Думал ещё, что может инет отвалился.

Поздравляю с победой в 2 диве! :)

→ Ответить

13 лет назад, # ^ |

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

Чужой код смотреть нельзя, но можно подать апелляцию, если что. Да, ещё стоит заметить, что мы писали из официального сектора, где уж точно по одному компу на команду. Ну и к тому же у нас код пишут только двое.

Спасибо)

→ Ответить

daftcoder

13 лет назад, # ^ |

Ну вот я примерно так и подумал, и решил, что нечего Снарку тут апелляцию писать)

→ Ответить

Creed

13 лет назад, # |

Кто-нибудь может рассказать как решать O и P?

→ Ответить

13 лет назад, # |

Решение задачи O разобрана выше, P решается в лоб, проверка на простоту для чисел до миллиона проверял решетом, а больших чисел в лоб.

→ Ответить

13 лет назад, # ^ |

Или блочное решето для вообще всех чисел. Кстати, интересно, как проверка в лоб могла заходить по времени.

→ Ответить

agul	13 лет назад, # ^ \| 0 А где O разобрана? → Ответить

13 лет назад, # ^ |

это задача J для див1 только у них ограничения по жестче.

→ Ответить

13 лет назад, # ^ |

влоб: просто перебираем отрезок, сумму на котором будем брать и смотрим: простая ли сумма?

→ Ответить

13 лет назад, # ^ |

да

→ Ответить

13 лет назад, # ^ |

+10

вот дерьмо, а не задача(

→ Ответить

13 лет назад, # ^ |

Ну сумму мы конечно за константу при этом считаем.

→ Ответить

13 лет назад, # ^ |

ну это то само собой, просто мы просидели весь контест и думали, что там что то более умное, так как мы думали в лоб не успеет, а это оказалось обычное безидейное хрень, которую просто надо было написать

→ Ответить

13 лет назад, # ^ |

Ну, миллиард за 7 секунд - относительно правдоподобно.

→ Ответить

13 лет назад, # ^ |

+13

==============

просто я не понимаю зачем такие огромные ограничения ставить 10⁹ итераций, неужели нельзя обойтись 10⁸ и ограничения на время 1сек

→ Ответить

agul	13 лет назад, # \| 0 Как подать апелляцию? Я захожу в раздел Appeals, делаю попытку, а потом пишу сообщение жюри, но мое сообщение все еще не прочитано. Все ли я делаю правильно? → Ответить

13 лет назад, # ^ |

+11

Вы не поверите, но то сообщение не прочитано, означает, что его еще не прочитали! Думаю если оно отображается, то рано или поздно жюри его увидит.

→ Ответить

agul	13 лет назад, # ^ \| 0 Я понимаю, что его не прочитали. Может быть, надо как-то не так отправлять сообщение, вот я к чему. → Ответить

13 лет назад, # |

кто-нибудь может объяснить, что за беда: сдаю этот код на О-МЛЕ2

→ Ответить

Creed

13 лет назад, # ^ |

ты функцию can вызываешь если та вершина куда идешь не предок текущей и возможно бесконечно много ходишь...

→ Ответить

13 лет назад, # ^ |

да ничего подобного, оказывается там временные переменные или че то такое: выше написано...

→ Ответить

alex.alex

13 лет назад, # ^ |

если запомнить дерево списком смежности то должно пройти МЛ

→ Ответить

13 лет назад, # ^ |

дело не в этом, там вообще куда меньше 256мб в этом коде(видимой памяти) и вообще я уже избавился от МЛЕ2, теперь ТЛЕ19 - наверное N*кол-во делителей числа не проходит в принципе(

→ Ответить

13 лет назад, # |

какого черта у меня дома работает Р за секунду, а на сервере ТЛ1 О_о

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Не заметил, что речь про первый. Может он не условия? Может файлы не убрал?

→ Ответить

13 лет назад, # ^ |

нене, уменьшая константу - WA5 становится. сейчас протестил один из кодов другой команды, прошедший на контесте - тоже выдает ТЛ1

→ Ответить

13 лет назад, # ^ |

видимо просто для дорешки оставлен слабенький серв

→ Ответить

grey_wind

13 лет назад, # ^ |

Первый тест - из условия. Если написать заглушку на него - будет TL5, ТL17 или что-то подобное. А может и зайдёт. Это удивительно и странно.

→ Ответить

agul	13 лет назад, # ^ \| +3 +1. У нас тоже так было. Причем один и тот же код сначала получает TL 17, а потом TL 1. → Ответить

kostya_by

13 лет назад, # ^ |

тоже долгое время было TL17. Немного ускорили Решето(переходили не j += i, а j +=i * 2) и зашло.

→ Ответить

13 лет назад, # |

а как считывать строку в М? там же 1000 тестов и длины строк до 10⁸/2 получается около 10¹⁰ символов

→ Ответить

13 лет назад, # ^ |

Я подозреваю, что там те же самые тесты, что и в D, т.е. их в сумме 50 мб. А вот в D пришлось писать хитрый ввод - я, например, читал fread'ом блоками по 1мб.

→ Ответить

e-maxx

13 лет назад, # ^ |

А какое решение в D?

→ Ответить

13 лет назад, # ^ |

Ну мы писали что-то такое, дописать не успели:

Будем считывать по одному символу, пока не увидим, что мы встретились. Это сделать легко, так как знаем, что суммарно подъемов и спусков N. После этого моделируем как левый пошел назад. Либо встретимся либо дойдем до начала. Иначе нам не нужно то что мы уже считали, а надо пойти вторым вперед пока не встретимся. Проверять встритились или нет так же как и в первый раз. Ну ко всему этому надо добавить рациональную арифметику заодно.

→ Ответить

Egor	13 лет назад, # ^ \| ← Rev. 2 → 0 Можно доказать, что вторая встреча будет до того, как второй дошел до корня, или ровно в этот момент → Ответить

13 лет назад, # ^ |

Если они первый раз встретились строго выше земли (а из условия это всегда так), то левый на обратном пути спустится до низу строго раньше, чем правый. Потому после первой встречи - точно такая же логика, как и до неё, только рассматриваем уже правого муравья вместо левого. Более того, в формулах возникает деление только на 4 и на 5. Поэтому если домножить всё на 400, то можно все расчёты вести просто в лонгах, делить только при выводе ответа.

Если делать всё аккуратно, проблем вроде никаких не возникает. У меня была мелкая опечатка в копипасте, потому сдал только в дорешивании.

→ Ответить

13 лет назад, # |

← Rev. 2 →

-45

Мне одному показалось, что ряд задач див2 сегодня были ненамного проще задач див1 и намного сложнее задач общей секции?

→ Ответить

13 лет назад, # ^ |

+37

Тебе одному.

→ Ответить

grey_wind

13 лет назад, # ^ |

Может, ты хотел сказать, "намного сложнее задач общей секции"?

→ Ответить

13 лет назад, # ^ |

-6

да, я описался

→ Ответить

goo.gl_SsAhv

13 лет назад, # |

Интересно как по человечески H решать, я думал думал, забил и вогнал квадрат с битовыми оптимизациями. Сейчас я знаю как сделть что-то вроде этого, но уже за "эн логарифм эн", а как правильно решалась задача?

→ Ответить

_jte_

13 лет назад, # ^ |

Если 1 символ, то ответ HM.
Иначе, выкидываем первый и последний символы.

Теперь смотрим, чего было налито больше, то и выводим. Если было равное число запросов на H и на М, то выводим не то, что стоит на последнем месте(учитывая, что последний сейчас - это предпоследний в начальной последовательности).

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-8

А зачем первый символ удалять? Последний понятно - потому что он полностью останется в чашке. Я лично сдал безо всякого удаления.

→ Ответить

shilov

13 лет назад, # ^ |

Моделировать процесс. Только объем чашки считать большим, например, 20e20)

→ Ответить

AlexanderBolshakov

13 лет назад, # ^ |

Я на контесте написал решение за О(N), но оно, скорее всего, тоже не человеческое. Код: http://pastie.org/private/n5b8pnrwcuib7xb1vzdzg. Формула такая: когда мы доливаем молоко или чай на k-ом по счету шаге (наливание чая и молока в пустой стакан считаем нулевым шагом), то мы прибавляем к числителю суммы (2^(n - k) - 1) * 2^k.

→ Ответить

13 лет назад, # ^ |

я вот так решил http://pastebin.com/fhsb0FLm

→ Ответить

13 лет назад, # |

можно посмотреть на код P, который проходит в дорешку?

→ Ответить

13 лет назад, # ^ |

-8

Не знаю про дорешку, на контесте у меня прошло n*n*logn. А на дорешке что, сервера более тормознутые?

→ Ответить

13 лет назад, # ^ |

да. я об этом написал чуть выше

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

прямо O(n² * logn) ? не O(n * n + n * loglogn) ли?

иначе полный бред с ограничениями, имхо

→ Ответить

13 лет назад, # ^ |

Бред с ограничениями. 1,5 лярда операций заходят в ТЛ.

→ Ответить

fdoer

13 лет назад, # ^ |

+11

вот, например:

https://ideone.com/6tzLg

→ Ответить

tyamgin

13 лет назад, # ^ |

Если решето поставить до 10^6, то проходит и в дорешку.

→ Ответить

yahooo

13 лет назад, # ^ |

у меня такой же вопрос по O?

→ Ответить

dalex

13 лет назад, # |

+18

Мы, конечно, сыграли контест очень плохо и сейчас этот пост заминусуют, но все же.

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

Если решето поставить до 10^6, то проходит и в дорешку.
А вот в D пришлось писать хитрый ввод - я, например, читал fread'ом блоками по 1мб.
Я долго подбирал константу
Решение будет получать TLE, даже если избавиться от dfs'а. Там вся веселуха с кэшем во время обхода дерева.

По-моему, такие контесты не нужны. Посмотрите на задачи с NEERC, на задачи этого саратовского четвертьфинала, на последние несколько контестов на Тимусе. И потом на этот. Неужели так увлекательно загонять шаманские оптимизации под 10 миллионов ввода и 15 секунд тайм-лимита?

Дискасс.

→ Ответить

yahooo

13 лет назад, # ^ |

на мой взгляд довольно смело с твой стороны это написать, ведь скорее всего многие так считают(и я тоже), но побоялись написать

→ Ответить

pkhaustov

13 лет назад, # ^ |

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

→ Ответить

MikeMirzayanov

13 лет назад, # ^ |

-18

Мне кажется, Олегу Христенко надо просто умножать текущие TL на 2-3. Все равно ограничения задраны так, что палево не пройдет, зато от контеста больше людей получат удовольствие.

Тем более, что для Java там вроде есть +0.5 сек., но при таких ограничениях впритык добиться равноценности TL для C++/Delphi и Java значительно сложнее.

→ Ответить