В четверг, 2 февраля, в 16:00 MSK стартует отборочный тур турнира ICL'2012. Тур закончится 16 февраля, так же в 16:00 MSK.
В течение отбора планируется выложить три блока по 5 задач. Правила почти соответствуют правилам ACM, однако за неверную попытку дается не 20, а 300 минут штрафа.
Сайт контеста: http://icl.ru/turnir/
Заинтересовавшихся милости просим =)
UPD Второй блок задач отборочного тура будет опубликован в четверг, 9 февраля, в 16:00 MSK. Желаю всем участникам успешных попыток.
UPD Третий блок задач отборочного тура будет опубликован во вторник, 14 февраля, в 16:00 MSK. Финишная прямая =)
UPD В связи с возможным увеличением квот, а также необходимостью пересчитать таблицу результатов без учета попыток с ошибками компиляции, объявление результатов отбора переносится на пятницу, 24 февраля.
Немножечко не понял, получается каждый может зарегистрироваться в любую команду? и как вообще посмотреть кто в твоей тиме?
p.s. спасибо большое за объявление
один аккаунт на команду надо заводить
Апну тему :)
Когда следует ждать появления остальных задач? Будет ли предварительно выслано какое-нибудь оповещение?
P.S. Samara SAU — клёвое название =)
P.P.S. Зачем нужен столбец "баллы"? На что он вообще влияет?
Правила: команды, не решившие ни одной задачи, будут ранжироваться по набранным ими баллам; Несколько подробнее о том, как подсчитываются баллы за задачу. Каждый тест для задачи оценивается в определенное количество баллов. Общая сумма баллов за задачу равна 1000. Сумма баллов за пройденные решением тесты — и есть баллы, получаемые за задачу. При этом, если команда сделала несколько попыток, то будет выбрано решение, набравшее наибольшее количество баллов. Однако, если команда посылала решение на задачу более одного раза, каждая такая "лишняя" попытка будет снимать 10 баллов. При этом баллы за задачу не могут быть отрицательными.
Интересно, зачем понадобилось ранжировать команды, не решившие ни одной задачи.
Нуууу... наверное это педантичность =)
Всего планируется три блока задач. Обычно оповещение выставляется на сайте за два-три дня до появления блока. Ориентировочно новых задач можно ожидать в четверг, 9 февраля, но они возможны и на день-два раньше.
Спасибо за up =)
Может ли кто-нибудь поведать решение задачи H? Вроде бы уже можно.
Пусть Xij — индикаторная случайная величина события "j занял место выше чем i".
Тогда место, занятое i — это случайная величина, равная сумме Xij для всех j (индексируем места с нуля). Матожидание суммы — сумма матожиданий. Матожидание индикаторной СВ — вероятность события.
Осталось найти, чему равна вероятность события "j занял место выше чем i". Можно вывести, что она равна a[j]/(a[i]+a[j]).
Расскажите, пожалуйста, как решать I, J, не осилил.
Не знаю, как решать I нормально.
Мы научились получать почти правильную позицию — когда все на своих местах, кроме последних двух клеток. Если N и M нечетные, из такой позиции получить правильную вроде нельзя. Если же хотя бы одно из них четное, получить правильную вроде всегда можно, но не очень понятно, как именно. Можно придумать, как все же делать это. А можно просто до посинения рандомшафлить исходную матрицу, пока применение нашего алгоритма не приведет к правильному состоянию. Если решение существует, из случайного состояния мы придем в правильное с вероятностью 1/2. Значит вероятность того, что мы не найдем решение сделав несколько шафлов, мала. Если за секунду решение не успели найти — что ж, пожалуй, его не существует.
Немного слов, чтобы решение стало "нормальным". Да, если N и M нечетные, то последние две клетки поменять нельзя, ибо циклический сдвиг строки/столбца не будет менять четность перестановки. В противном случае возможно несколько вариантов действий. Во-первых, если N четно, то за O(N) операций можно поменять местами два произвольных элемента (аналогично для M). Во-вторых, как предложил romanandreev, можно сдвинуть один раз вдоль четной размерности, чтобы четность изменилась, и проделать операции над матрицей заново. Можно посчитать четность начальной перестановки и сразу выполнить сдвиг, если нужно. В любом случае, после этого последние два элемента встанут требуемым образом в силу четности перестановки (при условии, что остальные элементы переставляются циклическими сдвигами длины 3, как написал SkyHawk)
Сначала приводится к правильному виду верхний левый прямоугольник (n-1)х(m-1), затем последний столбец. А затем я научился из последовательности ...abc... получать ...cab... Если надо — выложу код, сложно объяснить это на пальцах. Могу только сказать, что для обмена используется нижняя правая угловая клетка построенного прямоугольника (n-1)x(m-1). С помощью таких перестановок, повторяя их циклически, выстраиваем всю нижнюю строку (если её длинна четна). Если нечётна — придётся повозиться, если решение вообще существует. А решение не существует только если n и m нечётны и начальная перестановка нечётна (т.к. любая допустимая операция над строкой/столбцом нечетной длины не меняет четность всей перестановки — доказывать не пробовал, но вроде как правда)
Задача J Разобьем первую последовательность на отрезки вида [A0000,A9999], т.е. на каждом таком отрезке "пробегаются" только последние 4 цифры. Аналогично разобьем и вторую последовательность на отрезки [B9999, B0000]. Предположим, что эти отрезки лежат ровно друг под другом (если запишем последовательности одну над другой), и рассмотрим одну пару противолежащих отрезков. Теперь распишем наше скалярное произведение для такой пары отрезков и запомним "поведение" как раз последних четырех цифр. Это "поведение" на всех парах отрезков будет одинаково, и в итоге каждую пару отрезков мы сможем посчитать за O(1), узнав лишь произведение и сумму первых цифр. Итого в одном тесте считаем по 100000 отрезков длины 10000, тестов 100. Это общая идея, точные формулы приводить смысла нет, они легко выводятся.
Во-первых, начнём с такого приёма: числа, стоящие в вершинах прямоугольного треугольника (катеты параллельны сторонам квадрата) можно циклически сдвинуть, не изменяя расположение остальных чисел. Пусть а — имеет координаты x, y; b — z, y; c — z, w. Сначала a сдвигаем до строки z, потом c -смещаем до столбца y, потом c — смещаем до строки x, а горизонталь с a и b сдвигаем горизонтально, чтобы b имело координаты z, w; a — z, y.
Таким образом, сначала на своё место ставим 1, потом 2 и т.д. Останавливаемся, когда расставили всё кроме 2 последних строк. Начинаем расставлять числа теперь слева направо. Итак, мы получим либо правильную позицию, либо почти правильную позицию — там два соседних элемента будут не на своём месте: последний и элемент над ним. Итак, как справится со второй ситуацией? Пусть N или M чётное. Не умаляя общности, пусть N — чётное. Сначала сдвинем последний столбец на один вниз. Объяснить, я думаю лучше на примере квадрата 4 на 4.
Сдвинем циклически 12, 7 и 4, так, чтобы 4 встала на своё место. Потом циклически меняем 8, 12 и 7 — чтобы 7 и 8 встали на свои места. Т.е. мы сдвинули число на две позиции вниз, подвинув наверх 2 числа. Т.к. N- чётное, то это число мы положим в нужную позицию. Если M — чётное, а N — нет, то циклически сдвигаем a[n,m], a[n-1,m] и a[n,m-1], так, чтобы a[n-1,m] встало на нужное место. Далее делаем также как со столбцами, но только на горизонтали :-) Если N и M — нечётные, то этого сделать нельзя, но чёткого доказательства у нас нет.
Расскажите пожалуйста, как решить O (про Олимпиаду 2080) и L (дана z-функция построить строку).
O. Подвесим дерево за что-нибудь. Тогда ответом на запрос из вершин a,b,c будет одна из вершин: LCA(a,b), LCA(a,c), LCA(b,c). Найдем ответ для всех трех, выберем лучшую.
ну, еще можно заметить, что ответ всегда самый нижний LCA из этих трех.
O:Подвесим за одну вершину.
найдем попарные LCA вершин. Заметим, что в общем случае
На рисунке 3 нижних точки — запрос, заметим, что средняя точка второго ряда подходящая.
Ну, оказывается всегда одно из таких LCA — ответ.
PS: чтобы считать расстояние, для каждой вершины храним расстояние от корня. Тогда ответ
s(a)-s(lca(ab))+s(b)-s(lca(abc))+s(c)-s(lca(abc))+s(lca(ab))-s(lca(abc))
Уфф, какая-то ужасная формула, непонятно, откуда берется, намного удобнее вот так:
Ну там сумма 4 расстояний, каждое из которых — по одному пути из корня.
Специально подобные не приводил, думал понятнее будет, ну да, в таком виде по красивей будет пожалуй)
Спасибо. А правильно ли понимаю, что отсюда: «N городов, пронумерованных от 1 до N, которые соединены N-1 двусторонней дорогой, причем из каждого города можно попасть в каждый.» надо было сделать вывод что граф представляет собой дерево?
Да
Задача про z-функцию совсем простая, уж за квадрат-то.
Сделаем вначале последовательность {1,2,3,4,...,n}. Потом пройдемся по значениям z-функции и проставим в строке соответствующие элементы. Это можно делать, потому что эти равенства обязаны выполняться. Потом просто найдем z-функцию получившейся последовательности и проверим, совпадает ли она с данной.
Также ответ будет -1, если на какой-то позиции z[i] больше, чем количество оставшихся символов (n-i).
Расскажите, пожалуйста, как решать С :)
Мм. А какие проблемы могут быть с этой задачей у красного участника?
Правда ли, что задачу надо было сдавать используя вещественную арифметику, то есть промоделировать окружность и пересекать настоящие отрезки, построенные, как хорды этой окружности или, например, вывести какие-нибудь формулы с синусами? Я просто получал много WA на разных тестах и решил, что это из-за точности и есть какой-то очень хитроумный пример, когда три точки пересекаются просто невероятно близко. Это заставило меня думать о решении в целых числах, но придумать, как проверить пересекаются ли три хорды в одной точке я не смог, это возможно?
С вещественной арифметикой и отрезками сдавали. Вроде и не придумаешь при таких ограничениях тест с очень-очень близкими точками пересечения.
Кажется, это горе от ума.
> промоделировать окружность и пересекать настоящие отрезки, построенные, как хорды этой окружности
Вот именно так мы ее и сдавали, все сравнения делались с точностью 10 - 9.
Вещество.
У нас были некоторые проблемы с точностью из-за того, что мы складывали точки в set (один из худших случаев — когда все хорды пересекают одну горизонтальную (или вертикальную) и все точки будут отстоять от нее на +- eps и не совсем корректно сортиться). Потом мы стали засовывать точки в самописную хэш-таблицу (не надо сортить) и проблемы исчезли.
Чем хеш-таблица была для вас лучше в этом плане, чем set?
ну, с ней решение зашло:) set же работал некорректно.
мб, конечно, стоило просто написать нормальный компаратор, но не совсем понятно как он должен работать.
Вот так написали и все зашло
ок, значит я не умею писать компараторы.
Заранее извиняюсь за излишнюю занудность :) Но очень хотелось бы сказать про умение писать компараторы, что при проверке равенства двух вещественных чисел всё же правильно писать "<= eps", чтобы код оставался работающим при становлении eps нулем.
У нас был set и точки со стандартным компаратором, в котором все проверяется с eps.
У сета могут опять таки возникнуть проблемы, если какие-нибудь две совершенно разные точки пересечения имеют оочень похожие X (координата, по которой сравнивается в первую очередь), что их eps-окрестности пересекаются даже при очень маленьком eps. В итоге при разных попытках вычисления этих точек они будут попадать в совершенно разные места set'а. Ну это было чисто теоретическое предположение, которое побудило избавиться от компаратора вообще.
Удобно воспользоваться теоремой о пересечении хорд, а так же теоремой об угле пересечения хорд. Будем добавлять хорды по одной, считать число точек пересечений с предыдущими и прибавлять к ответу. Координаты точки пересечения находим как одно из расстояний до концов хорды, посчитав углы в каком-нибудь треугольнике, образованном концами хорд и точкой их пересечения. Для этого используем теорему о синусах, причём нужны синусы только дискретных углов, поэтому я посчитал их предварительно в long double — вероятно, излишняя осторожность. Соответственно для каждой добавляемой хорды находим точки пересечения с остальными, кладём всё в массив, сортируем, считаем число различных. С eps = 1e-12 зашло сразу.
Да, я математик %)
Теорема синусов и углы, между хордами — это не труЪ математика. Вот применение синусальной теоремы Чевы — вот это круто. Кстати, через эту теорему решается много задач, где можно прочитать в Прасолове "Задачи по планиметрии", в самом конце там написан приём решения задач такого рода: дан треугольник. Дано куча углов, найти какой-то. А счёт в углах не поможет. Или надо доказать, что такие-такие диагонали n-угольника (чаще у которого углы хорошие) пересекаются в одной точке.
Согласен, крутая теорема. Правда не очень понимаю, как её приложить к данной задаче.
Просто критерий того, что три хорды пересекаются в одной точке, с помощью синусальной Чевы, а не обычной Чевы — записывается на раз-два.
Ааа, для трёх хорд — здорово! Красивое решение, спасибо =)
http://ilib.mccme.ru/djvu/bib-kvant/izum.djvu?djvuopts&page=10
Если я не ошибаюсь, это оно. Очень подробно =)
На вид офигенная книжка, пойду ей упарываться. Спасибо.
Купил, у самого времени нет почитать =)
Мне вот J интересна. Hohol ее как-то решил, но не знаю, в каком он был состоянии, потому что он уже ничего не помнит и не может ее рассказать.
Я щаз опять попытался описать свое решение, ниасилил и опять забил. Наркомания.
Пусть s(a) — сумма цифр, p(a) — произведение. Рассмотрим s(a)*p(b) + s(a+1)*p(b-1) + ... + s(a+d)*p(b-d). Обозначим c(a,b,d).
Если у всех b, b-1, ..., b-d старший разряд одинаковый (и в каждом числе одинаковое кол-во цифр), то c(a,b,d) = (старший разряд b)*c(a,b без старшего разряда,d). Нужно дополнительно учесть случай, когда у (b-d) без старшего разряда значищих цифр становится меньше чем у b без старшего разряда. И когда b без старшего разряда и b-d без старшего разряда имеют лидирующие нули.
Если у всех a, a+1, ..., a+d старший разряд одинаковый (и в каждом числе одинаковое кол-во цифр), то с(a,b,d) = (старший разряд a)*(p(b) + ... + b(b-d)) + c(a без старшего разряда,b,d) Подсчет p(b) + ... p(b-d) также сводится к вынесению старшего разряда.
В противном случае можно разбить на пары отрезков [a,...,a1] и [b,...,b1], [a1+1, ...a2] и[b1-1,...,b2] и т.д. так чтобы старшие разряды на каждом отрезке были одинаковыми.
Подзадачи удобно хранить в С++ в map. Откуда брались общие подзадачи можно понять из примера разбиения:
a = 531 b = 760 d = что-нибудь большое. Отрезки: [531...599] [600..699] [700..799] ... и [760..692] [691..592] [591..492] ...
кто ты >_<
А какое у тебя было решение? Что-то похожее?
Да, похожее. Только я разбивал втупую на отрезки длины 10000. Проще разбивать, но асимптотика получилась не очень хорошая, и пришлось немного попихать.
Задачи неплохие, жаль, что почти не было времени их порешать. Хочется сказать спасибо авторам задач и особое огромное спасибо тому человеку с железной логикой, который додумался вывалить третий блок задач вечером 14 февраля. Помоги ему, Господи.
Когда еще, как не вечером 14 февраля, ты можешь доказать свою преданность олимпиадному программированию?
А по-моему неплохой способ отметить день рождения ENIAC =)
Вот уж от кого, а от главного критика codeforces положительного отзыва не ожидал. Спасибо :)
Как по-нормальному решается B?
https://oeis.org/
Читеры %) А я написал честное решение с теоремой Пойа (она таки пригодилась!) и недодлиннкой.
Ну правда, вы бы еще спросили, как решать D
Ну тут я догадался написать перебор и вывести формулку ручками — здесь это было несложно =)
о_О ЛОЛШТО???
Вы ручками вывели вот это, это, и, что особенно страшно, вот это?
Гм, да там как-то проще... Вот решение. Сейчас вспомню и опишу подробнее
Ну в общем проще посмотреть в код:
Вот блин! Кто бы думал, что такое может быть на oeis.org
пишем перебор для маленьких n, гуглим в oeis
а как нормально решать D?
я написал тупой перебор, потом методом пристального взгляда увидел нетривиальную закономерность и оно даже зашло.
вот оно: http://pastebin.com/aAfaBvED.
ради смеха прошу обратить внимание на строки 107 и 109:D
Вот. В принципе так же, только код несколько проще =)
Я решил эту задачу не используя OEIS вообще. Выводим первые 15 — 19 элементов последовательности и обнаруживаем закономерность — начиная с 5-ого все элементы A[i] имеют вид A[i] = X * A[j] + Y * A[k], где j, k — индексы, строго меньшие i, а X и Y — множители от 0 до 2 (включая обе границы). Отсюда получаем очевидное решение, в которое лишь ручками надо забить первые 4 элемента последовательности.
Впечатлило. Константы бинпоиском подбирали?
Не, там просто идет перебор некоторого параметра z чтобы все срослось. При больших n приращения z очень большие и решение тормозит. Но если два z для последовательных n поделить друг на друга, то они сходятся к тем числам, что вбиты в решение. Если перед тем как инкрементить, тупо домножать на них, то ускорение получается такое, что все заходит даже без прекалка.
Короче, магия тут чисто для скорости.
Метод Ленинского прищура работает! Я этим методом код дебажу иногда, а в идеале этот метод должен стать единственным методом дебага, это показатель мастерства.
Ай, не успел заслать G, люди, не подскажите, такое бы решение зашло? http://pastie.org/3395338
Нет. WA2, тест
Ну, больше интересовала временная составляющая, потому что я так и не смог посчитать, сколько она примерно работает, чисто ошибки в самом алгоритме, думаю, после первого же WA выявились бы сами.
Со временем работы всё в порядке — полигон показывает только wa.
Выиграть среди школьников оказалось несколько проще, чем отобраться среди студентов:))
Сегодня будут результаты?
Есть проблемы с отсечением CE. Но, думаю, на бОльшую часть приглашений это не влияет. Планируем выложить.
А чем было вызвано желание отсечь СЕ? А то это как-то нечестно, некоторые команды, выбирая время отправки задачи, опирались на текущие результаты других, и будет несправедливо, если эти результаты внезапно изменятся.
Что значит опирались на чужие результаты? :) Отсылали позже, чем это возможно? :)
Ну например тестили дольше, чем нужно) У нас, например, был выбор — написать последнюю задачу вечером, в зомбическом состоянии, или с утра. Вторая тактика принесла 3 минуты выигрыша и 3-е место в общем зачете =)
Давать 300 минут штрафа за CE тоже несправедливо. Это пять часов, полученные за промах мышкой при выборе языка или незнание, что long long отсутствует в MSVC7.
Согласен, но как-то неправильно делать rejudge после контеста. Нам то, надеюсь, это не сильно повредит, но вот если кто-то не отберётся из тех, кто должен, будет явно нечестно — по крайней мере во время контеста все находились в равных условиях, а теперь получается смена правил после окончания соревнования. Надеюсь, проблем с этим не возникнет.
А если не возникнет (i.e не будет таких, кто не прошел из-за этого) то получится что из реджадж зря:)
Я очень надеюсь на сознательность организаторов и расширение квоты таким образом, что пройдёт объединение множеств тех, кто отобрался до реджаджда, и тех, кто после.