CodeChef invites you to participate in the March 2012 CookOff.
Time: 2130 hrs 18th March 2012 to 0000 hrs, 19th March 2012 (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: COOK20
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Hiroto Sekido (LayCurse)
Problem Tester: Rajiv Kumar Aggarwal
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
Печальное пересечение с wildcard round–ом
и как же считать быстро сумму чисел Стирлинга второго рода в строке??
UPD ну, не во всей строке, а только первых n в ней. так что формула из википедии катит
Знание таких слов делает мысли предвзятыми :) Я придумал почти сразу, не зная, как это называется :)
Пусть g(n) — количество способов раскрасить последовательность длины m в не более чем n цветов так, чтобы на любом отрезке длины k цвета не повторялись. Это несложно считается как что-то типа n*(n-1)*..*(n-k-1)*(n-k)^(m-k). За O(n).
Пусть f(n) — ответ на задачу, если обязательно использовать каждый цвет хоть раз. Можно заметить, что f(n)=(g(n)-sum_{i=1}^{n-1}{f(i)*C_n^i*i!)/c!. Не знаю, как это сходу объяснить, наверно это не очень сложно понять :) Ответ на задачу — sum_{i=1}^{n}{f(i)}.
Итого, O(n*(n+k+*log m)).
спасибо, в editorial примерно то же самое) видимо на меня какой-то тупняк сегодня нашел, я же уже когда-то сдавал почти такую же задачу, причем мне кажется, что именно на codechef О_о UPD вот очень похожая задача. решение не совсем такое же, но суть та же.
как-то странно давать почти такую же задачу на том же ресурсе, не?:)
А откуда там логарифм берется? В разборе тоже логарифм есть, но я не вижу чтобы во внутреннем цикле что-то в степень возводилось.
там вроде деление в поле по модулю 10^9+9
UPD не, тут же еще возведение в степень M-K есть )
Ну так деление же на числа <=200, обратные к которым можно предпосчитать. Причем в разборе они так и написали, что "если предпосчитать обратные к этим числам, то сложность будет N^2*logM".
Ответ на правку: я говорил про внутренний цикл. Возводить в степень M-K нужно всего N раз.
Действительно.
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, пункт Explicit formula
офигеть. задача на гугление/знание формулы?
Если ты про задачу CIELGAME, то на возведение матрицы в степень, мне кажется. Я почти придумал, слишком много тупил над первыми 3 и контест закончился раньше.
не проходит же
Вань там это никак не проходит. Я больше часа пихал это.
Ух ты. А я сначала сделал
(быстрое возведение матрицы в степень), естественно, не прошло. Потом предподсчитал двоичные степени матрицы (она на самом деле одна), а в каждом тесте умножал только матрицу на вектор, получилось 
, что вообще могло бы и пройти, но чё-то и оно не запихалось.
блин, я не подумал что помимо предпосчета степеней двойки можно еще вектор, а не матрицу, умножать)
видимо компы у них действительно очень медленные...
UPD в прошлый раз я долго и упорно запихивал правильную асимптотику на эту задачу
Я помню Gerald мне как-то говорил, что его нетбук мощнее их сервера))
да уж)) кстати, у них вроде проверяющая система общая со spoj/как на spoj. теперь понятно, почему на spoj часто приходится пропихивать решения)
А как выглядит матрица? У меня не получилось придумать одну матрицу для всех n и k.
по-моему, верно, что ответ для (n, m, k) равен ответу для (n-k, m-k, 0) :) я на маленьких проверил))
так что я сначала тупо для каждого k заново строил матрицу, а потом построил ее уже только для k=0, но все равно не запихнул
Просто матрица получения следующей строки чисел Стирлинга из предыдущей. S(n, k) = S(n - 1, k - 1) + kS(n - 1, k). Соответственно, в матрице n × n на главной диагонали стоят единицы, а под ней — числа 1, 2, ..., n.
Ну и сначала в решении делается
while (n > 0 && m > 0 && k > 0) {n--; m--; k--;}, после чего разбираются два случая, когда нулю оказалось равно не k.а как доказать корректность этого while? я только для мелких заметил и поверил)
Вообще, можно вместо таблицы M × M считать, что у нас есть ограниченно растущая строка длины M: то число, которое встретилось первым, мы будем записывать как 0, то, которое встретилось вторым — как 1, и так далее.
Первые k + 1 шагов мы обязаны брать различные числа, то есть начало нашей строки имеет вид 0123...k. А дальше на каждом шаге у нас есть x ≥ k + 1 различных встречавшихся чисел, k + 1 последних брать нельзя, соответственно, x - (k + 1) вариантов взять одно из уже встречавшихся чисел. А ещё есть вариант взять новое число, если x < n, в этом случае мы будем обозначать его как x, а количество различных встречавшихся чисел станет x + 1.
Теперь заметим, что, если в этом рассуждении уменьшить k на единицу и уменьшить n на единицу, то начало строки станет на один символ короче (то есть m уменьшится на единицу), а больше ничего не изменится.
А что за числа Стирлинга вообще? ))
Спроси у Геры)))
число Стирлинга второго рода — dp[m][n] — ответ на эту задачу для n, m, k=0 :) я свел все к случаю k=0, но поискать в википедии не догадался (в oeis пошарился и подумал, что нормальной формулы нет)
It was my first Cook-off. I like the problems. But I was very slow with first 3 and I was out of time just before I was able to solve the forth one.
Я правильно понимаю, что в Ciel and Genjiko нужно решение быстрее чем за O(n3logn)?
видимо да, у меня был TL. поправь только в комменте асимптотику)
У меня квадрат на тест.
Думал со злости что-то разобью! Отослал на 3ю задачу решение, оно как всегда на фри паскаль не зашло по времени я переписал на жпс, отослал, получил СЕ, убрал uses math, зашел отсылать, отослал и сразу заметил что снова на фри сдал, быстро остановил загрузку, исправил язык и переслал. Но задача успела отослаться, в результате 2е решение прошло, а первое нет и я получил +20 к времени и -2 места которые СНОВА отделили меня от топ 10. :(
мне искренне жаль вас
PS. иногда, я так рад, что у меня небыстрый интернет
Самое обидное что уже в +100500й раз не в топ 10 изза какой-то мелочи.
CIELLAND решалась бинпоиском по ответу?
Нет. За O(3^n) динамикой по подмаскам.
может k*3^n, нет? можете подробнее
Да O(k * 3 ^ n) и еще предпосчет.
В общем предпосчитаем для каждого подмножества точек, каким минимальным расстоянием его можно покрыть одной прямой.
А дальше динамика dp[i][mask] — ответ для задачи с множеством точек mask и кол-вом прямых равным i
это как раз таки очевидно, как считать минимальное расстояние для подмножества точек?
Можно показать, что искомая прямая будет параллельна одной из сторон выпуклой оболочки.
Вот это вообще не очевидно)
согласен, и даже если это так, то как вычислисть прямую?
переберем все пары точек, и проведем через них прямую. Найдем самую удаленную слева от нее и справа , расстояние будет сумма расстояний пополам.
что-бы найти расстояния можно просто взять формулу (a*x+b*y+c)/sqrt(a*a+b*b) , то есть без модуля, и можно просто взять и от максимума этой функции отнять минимум.
Вычислим расстояние от этой прямой до самой далекой точки, назовем его d.
Возьмем прямую, через которую проходит ребро. Расстояние от этой прямой до самой далекой точки и будет равно 2d.
спасибо за объяснение, теперь все стало понятно
Ну почему. Проходит и бинпоиском с динамикой за O(2^n * n^2).
А у меня бинпоиск + динамика за O(2^n * n^2)
KADR опередил меня))
What computers do you use for testing the solutions?
My solution for problem Ciel Numbers I runs locally in 0.150 seconds, but I got TLE on the server.
Is there any way to run solution on the server, to learn, how much time does it work?
Нияз, там иногда решение которые работают 0,1 локально в 3 сек не влазят.
That's not good.
What should I do to be confident that my solution runs in time?
Sometimes I rewrite my solution on another language(today my solution(on fpc) got TL, but it got AC on gpc).
I remember that Gerald mentioned that his netbook is faster then testing machine.
Floyd's algorithms gets TLE with TL=1s and V=500.
it's very unconvinient to search the problems in "practice". Could you make a opportunity to classify the problems by the contests where their were in?
Just go to the address bar and delete the contest code (for ex: "/COOK20")
oh, thnx! :)
Well it is pretty simple to locate a problem from a particular contest in the practice area. Open the contest problem (like http://www.codechef.com/COOK20/problems/CIELLANDLAND) and remove the contest code that appears in the URL (like COOK20 or MARCH12 the URL now becomes http://www.codechef.com/problems/CIELLAND) and press enter with the new URL.