Комментарии
|
+11
Мы просто генерили рендомные строки по 10 символов, пока не нашлись 2 с одинаковым хешом. |
|
+8
Вообще довольно интересно, как искать количество решений системы, если эта система не по простому модулю. Может кто-то знает как это делать в общем случае? |
|
0
Так тоже пробовал, но на одном из семплов это не работает. Вторая система получается несовместна, хотя первая имеет решение. |
|
+8
Я вообще сильно удивился, когда прошло :) Действительно идея неверна, сам себя счелленжил в дорешивании тестом: N=2, Qfrom[] = {0,0}, Qto[] = {1,1}, output = {9,1}. Получается, что тесты на ТС совсем неполные. |
|
+13
Чтобы посчитать количество решений по модулю 4, можно просто предположить что это система по модулю 2 (просто взять все коэффициенты по модулю 2). После этого найти количество решений системы и возвести полученное число в квадрат. Я правда, не совсем понял почему это верно, но зашло в дорешивании, на контесте подбирал нужную степень двойки на которую нужно домножить, но так и не подобрал, потому как набажил в коде нахождения ранга матрицы :) |
|
+30
Расскажу как решать F. На контесте не сдали, забыли закомментить отладочный вывод за 3 минуты до конца и получили ВА1, но в дорешивании прошло. Идея такая: Найдем k такое, что pk ≤ n < pk + 1. Заметим, что количества апельсинов на дереве равно pm - a[m - 1]pm - 1 - … - a[0]p0. При этом a[i] равно либо 0, либо 1. Тогда если два дерева дают в сумме n то это один из трех случаев:
Рассмотрим каждый из них отдельно.
Складывая ответы для всех трех случаев получаем окончательный ответ. Вот код на JAVA: http://pastebin.com/y8JXFUg9 |
|
+17
7-ой — это я :) |
|
0
Да, действительно, было 2 отправки в 4:59:10 и 4:59:50.
И вторая из них была последней успешной отправкой на контесте. К сожалению, не я отвечал за тестирующую систему, поэтому не знаю причины, по которой она не успела загрузить сабмит. |
|
+4
Отправка была за 10 секунд до конца контеста и тестирующая система не успела загрузить себе решение (поскольку ее выключили почти сразу после контеста). В итоге решение было протестировано позже (примерно в 20 часов), когда систему снова включили. Решение оказалось правильным. |
|
0
На контесте немного не успел отдебагать, но в дорешивании сдал за O(n3*log(P)), где P - максимальный элемент в матрице. Общая идея такова: сначала как и в написанных выше решениях рассматривается максимальный элемент, тогда задача сводится к подсчету числа способов расставить числа от 0 до P в фигуре типа уголка, так чтобы максимум в каждой строке и столбце был P. Найдем это число при помощи формулы включений и исключений. Пусть уголок имеет размерности как на рисунке.
Таких способов понятно 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 |
|
0
Вообще, эта задача была этим летом на сборах в Петрозаводске в контесте команды Тавриды. При этом, были следующие ограничения: N<=450000, количество запросов <= 600000, TL 4 секунды. Вроде как ничего, кроме персистентного дерева с ответом за logN на запрос, не проходило. Авторское решение совпадает с решением из поста Malinovsky239.
|
|
+3
Я занял 31 место. Но пока еще не получил загранпаспорт, поэтому если дата онсайта не изменится, то я точно не поеду. В общем, можете считать, что у вас 33 место :)
|
|
+10
Следует рассмотреть 2 случая, когда количество сторон четно и нечетно. В любом случае, если многоугольник описанный, то точки касания делят стороны на 2 части. Обозначим стороны a[i]. Пусть сторона a[i] делится на кусочки x[i] и x[i + 1] (нетрудно видеть, что соседние кусочки на соседних сторонах равны). Тогда если n - количество сторон нечетно, то x[1] выражается через a[i]. Если n четно, то из системы x[i]+x[i+1]=a[i], для i от 1 до n, x[n+1]=x[1], можно найти, что x[1]<a[1], x[1]>-a[2]+a[1],x[1]<a[3]-a[2]+a[1], и так далее. Тогда, выберем любое x[1] подходящее ограничениям. После выбора x[1] выразим все остальные кусочки. Если x[i]<0 или x[i]>a[i] то тогда ответ NO. Иначе, если радиус окружности вписанной в многоугольник равна R, то тогда единственное условие на то, что такая вписанная окружность существует, это 2*arctan(x[1]/R)+2*arctan(x[2]/R)+...+2*arctan(x[n]/R)=2*Pi (слева сумма углов из под которых видны стороны многоугольника из центра). Далее нетрудно понять, что слева функция монотонна и искать искомый радиус следует бинпоиском. А зная радиус и точки касания уже легко восстановить координаты вершин многоугольника. |
|
+10
Очевидно, что потолок 10^600*100!, так как всего перестановок 100! и каждая оценивается 10^600 - это число примерно равно 10^760, мы брали 720 знаков и оно прошло.
|
|
0
Если произведение p1*p2*...*pn намного больше максимально возможного абсолютного значения определителя, например как минимум в 3 раза, то понятно что не может быть такого, что этот определитель больше чем (p1*p2*...*pn)/2 поэтому и берем его как отрицательный. Возможно проще на примере, если у нас матрица из одного элемента, например (-5), а модуль 101, то наше значение по модулю 101 - это 96, понятно, что такого быть не может, поэтому ответ 96-101.
|
|
+10
Можно сдать, используя китайскую теорему об остатках. Вычислим наш определитель по 100 простым модулям, каждый порядка 10^9. После этого наш определитель однозначно восстанавливается. Например можно использовать алгоритм Гарнера. А для вычисления определителя по модулю просто делаем обычного Гаусса, где вместо делений обратные элементы. Единственная трудность, ответ может быть отрицательным, но ее тоже легко обойти, если X - определитель по модулю p1*p2*...*pn, где pi - это наши простые модули, то он отрицательный только тогда, когда X+X >= p1*p2*...*pn и тогда ответ это (X-p1*p2*...*pn). |
|
+5
Я считал общее количество наборов людей для которых выполнено условие того, что всего людей S+x, из них m[2] групп по 2 человека с днями рождения в один день, ..., m[s] групп по s человек с днями рождения в один день. Тогда людей с уникальными днями рождения x. Если на время забыть про дни, когда все родились, то имеем размещение с повторением (вроде оно так называется). При этом общая формула для количества таких размещений людей n!/((n1)!*(n2)!*...*(nk)!), где n-общее число людей, а n1,n2,...,nk - размеры различных классов еквивалентности. Подставляя в эту формулу наши данные, то есть m[2] классов по 2,..., m[s] классов по s, и один класс из x человек - те у которых уникальные дни рождения (этих людей мы рассматриваем отдельно от остальных), получаем такое выражение
(S+x)!/((2!)^m[2]*(3!)^m[3]*...*(s!)^m[s]*x!) Это общее количество вариантов распределений на группы, без учета дней, в которые родились люди. После этого нужно учесть дни. Для P групп нужно выбрать по дню - это A(d,P). И для оставшихся x людей нужно выбрать x дней - это A(d-P,x). Вот откуда взялась эта формула и x! в знаменателе числителя. |
|
+5
Врядли можно свести к парадоксу о днях рождениях, но тут можно сделать по-другому. Просто посчитаем вероятность того, что у нас будет S+x работников в фирме, где S=m[2]*2+...+m[s]*s, а x изменяется от 0 до d-P, где P=m[2]+...+m[s]. Нетрудно видеть, что других возможностей для количества работников в фирме нет.
Тогда вероятность p[x] для количества работников S+x равна (S+x)!/((2!)^m[2]*(3!)^m[3]*...*(s!)^m[s]*x!)*A(d, P)*A(d-P,x)/d^(S+x) где A(n,k) = n!/(n-k)!. После этого чтобы найти ответ достаточно сравнить соседние p[x] и p[x+1] и первое x такое, что p[x+1]/p[x]<1. А отношение p[x+1]/p[x] легко посчитать, оно равно ((S+x+1)*(d-P-x))/(d*(x+1)). Собственно говоря, реализация очень простая, но до решения догадаться не так просто. |
|
Можно решить динамическим программированием за O(L1*L2*L3) - где L1, L2, L3 - размеры множеств. Пусть D[i][j][k] - максимальное число комплектов которые можно выбрать, если можно брать только комплекты, в которых первый элемент принадлежит первым i элементам первого множества, второй - первым j элементам второго множества, третий - первым k элементам третьего множества. Тогда D[0][0][0] = 0, а пересчет динамики такой, если p1 <= a[i] + b[j] + c[k] <= p2, то D[i][j][k] = max(D[i - 1][j - 1][k - 1] + 1, D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1]), иначе D[i][j][k] = max(D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1]), где a - первое множество, b - второе, c - третье. Ответ на задачу D[L1][L2][L3]. Вроде правильно :) |
|
+1
Я тоже думал, что сдвинули, по крайней мере таймер показывал что остается 15 минут до старта, а потом когда сумел зайти в контест, оказалось, что он уже 5 минут как идет :)
|
|
+6
Но в любом случае это как-то неправильно.
На самом деле сайт достаточно часто виснет, за первые пять минут я даже не смог открыть условия задач, аналогичная ситуация наблюдалась в последние секунды контеста и сразу после него, на сайт просто не заходило, причем я пробовал с разных браузеров (Opera, IE, FireFox). Поэтому я думаю, что проблема все-таки не в таймере из браузере. |
|
+4
Странно получилось, за 2 секунды до конца отправил решение задачи C, но оно, как выяснилось не отправилось, при этом никаких уведомлений об этом не было. А потом, когда отправил в дорешивании, оказалось, что решение правильное... Обидно, что из-за багов системы не сдаются задачи... |