Всем привет!
Сегодня в 20:00 по Москве состоится очередной TopCoder SRM
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Название |
---|
Что же, многие сегодня будут праздновать, мои поздравления! Но можно успеть и матч написать, и погулять на славу (т.к. в Украине традиционно празднование=пьянка)
P.S. Кстати, ты еще первую сессию не сдал - рано тебе день студента отмечать.
ой, заглючило
Как решать 500 ?
Странно, у меня на систестах решение упало по времени на "-1000 999", хотя тест "1000 -999" проходило успешно.
А на моем компе оба теста проходят моментально(мой косяк). Какой-то особый фейл?Вот это раунд! Я за все время не придумал, как решать 500, и чувствую себя дибилом.
Тоже сначала вспомнил о Четности. Потом вспомнил, что до сих пор не знаю решения четности.
Потом начал вручную выводить какие-то факты, ничего не придумал.
Теперь, когда прочел решение, стало еще более стыдно за себя)
Зато буду знать на будущее. Странное, что такую боянистую идею знали (или решили на ходу) так мало кодеров.
Интересно, много ли кодеров сразу после начала челенджей побежали искать тех, у кого в 250 не учтен 1 корнеркейс:) Мне показалось, что очень много:)
И много ли таких, кто зафейлил 250 на чем-то другом)
Думаю, все кто корнеркейс заметили его искать)
Да челлендж фаза была лотереей: кто попал в того кто не учел, тот получил 50. Мне такое не по душе :)
Дело в том, что мои 248.39 и ~170 место превратились в 177.85 и ~450 место
И рейтинг даже увеличился, прикольно
Это спровоцировало аж 3 челленжа.
По идее можно было просто генерировать подходящие нам числа, многие так решали.
То есть выписать все числа, которые могут быть в ответе и из них лексикографически делать новые и проверять на делимость, очередью например.
Изначально в очередь кидаем все разрешенные цифры ( кроме нуля), запоминаем остатки.
Теперь, пока очередь не пуста, вынимаем состояние из очереди, пробуем перейти в новое - допистаь в конец какую-то из разрешенных цифр.
Берём минимальное число, для него считаем кол-во способов покрасить решёточку (кубической динамикой). Умножаем ответ на это число способов.
a[n1][n2-i]*(кол-во способов закрасить верхнюю строчку) * (кол-во способов выбрать выкинутые столбцы) * (кол-во способов расположить по ним остальные числа)
Каждый из множителей легко считается.
А что делать с тем, что при расположении по столбцам каких-то чисел могут выкинуться еще строчки?
Для каждой строки мы перебираем кол-во столбцов, в которых X пока не встречался, и в которые мы просто обязаны этот X поставить.
Общая идея такова: сначала как и в написанных выше решениях рассматривается максимальный элемент, тогда задача сводится к подсчету числа способов расставить числа от 0 до P в фигуре типа уголка, так чтобы максимум в каждой строке и столбце был P.
Найдем это число при помощи формулы включений и исключений.
Пусть уголок имеет размерности как на рисунке.
Тогда посчитаем число способов расставить числа от 0 до P, так чтобы какие-то i строк были плохими (т.е. максимум в строке < P), и какие-то j столбцов были плохие.Таких способов понятно F(i,j)=Pc1*(P+1)c2, где c1=i*a+j*b-i*j, c2=x*a+y*b-x*y-c1 (в этих i cтроках и j столбцах должны стоять числа меньше P, а в остальных клетках могут стоять числа от 0 до P, с1, с2 - количества клеток этих двух видов). Но тогда ответ это просто сумма этих выражений по всем возможным выборкам i строк и j столбцов, при этом F(i,j) входит со знаком "+", если сумма i и j четна и с "-" в противном случае. Но понятно, что выборок i строк и j столбцов ровно C(x,i)*C(y,j), где С(n,k)-биномиальный коэффициент.
Все, таким образом для уголка можно посчитать ответ за O(n2*log(P)) просто пройдя двумя циклами по i и по j и добавив или отняв F(i,j)*C(x,i)*C(y,j). Также понятно, что общая сложность O(n3*log(P)) так как различных элементов в строках и столбцах O(n).
Исходный код: http://pastebin.com/rFnZ5tPh
С учетом последних результатов Egor'а (CF93,CF94,TC524), похоже, что в его плагине появилась кнопка "Solve" =)
А есть ещё кто-то, кому именно на этот раунд не пришло по e-mail напоминание (хотя всегда приходило)?..
UPD (написан после первых трёх ответов).
Ну так, видимо, причину меньшего кол-ва участников надо искать в первую очередь в этом.