26 сентября в 11:00 MSD состоится очередной этап Открытого Кубка. Всем удачи!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
1)Считаем динамику f[i,j], i-номер начала, j-номер подстроки(1-9), сама функция это номер последнего символа подпоследовательности j в главной строке, если начинать искать подпоследовательность с i-того символа в главной подстроке. Ну, например строка asaafaa и подстрока aa. Тогда f[1,1]=3, f[2,1]=4, f[4,1]=6, f[7,1]=-1
2)Генерим все n! перестановок, с помощью нашего метода вычисляем, являются ли они нашей подпоследовательностью за n операций
3)Как-нибудь отсеиваем одинаковые строки(мне кажется, что можно хешами)
4)PROFIT!
надо считать динамику f[i][j][k] - то же самое, только считаем с k-го символа строчки j. Тогда пересчет происходит за O(1) и по времени проходит.
3) да, хешами проходит.
for i = 1 to n
t[i][1] = a[i]/sum;
for i = 1 to n
for j = 1 to n
if (i != j)
t[i][2] += a[i]/(sum-a[j])*t[j][1];
for i = 1 to n
for j = 1 to n
for k = 1 to n
if (i != j && i != k && j != k)
t[i][3] += a[i]/(sum-a[j]-a[k])*t[j]*t[k];
prob:= (a[winner1]/sum)*(a[winner2]/(sum-a[winner1]))*(a[winner3]/(sum-a[winner1]-a[winner2]))
f[winner1,1]:=f[winner1,1]+prob;
f[winner2,2]:=f[winner2,2]+prob;
f[winner3,3]:=f[winner3,3]+prob;
Задачу K можно было сдать читерно. Напишем жадное решение. Оно не будет проходить около 6 тестов из тестсета. Далее пишем перебор с прекращением работы после 7 секунд. Я не нешёл теста, которое бы повалило это решение.
Моё решение честное, но в нём 1200 строк.
Я слишком увлёкся вырожденным случаем, что совсем забыл про такие решения. Задача задумывалась как самая простая, поэтому неполнота тестов не так страшна.
Походу, я 59-м тестом хотел сделать 501 500 1000, но сделал 499 500 1000
Не могу понять, их надо искать, только по генерируему вектору или по всей плоскости?
А, вообще у меня не проходит 21 тест по времени.
Вся программа работает быстро. Но как только начинаю проверять сколько точек лежит на заданном луче сразу ТЛЕ. Спасибо.
Ну можно заметить, что оптимальная ломаная - это если мы проведем высоты из вершин треугольника, а потом соединим полученные основания высот. Тогда можно заметить, что если у нас есть любой треугольник, который удовлятворяет строгому неравенству треугольника, то можно провести в нем биссектрисы, а затем через вершины нашей ломаной провести прямые перпендикулярные биссектрисам. Тогда мы получим, что для любой ломаной, которая представляет собой невырожденный треугольник - ответ Yes. Все это видно на картинке
Тогда вероятность 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)).
Собственно говоря, реализация очень простая, но до решения догадаться не так просто.
посчитаем количество ситуаций, когда люди разбились на классы эквивалентности так, как нам надо. Выберем из d дней (p+x), в которые кто-то рождался. выбирать надо упорядоченным образом, то есть в первые x дней рождались по одному человеку, в следующие m2 дней по два, и т.д. Для определенности скажем, что люди рождались в дни a_1, ... , a_x, a_(x+1),... a_(p+x). Теперь если записать последовательно кто в какой день родился получится слово длиной S+x из символов a_1, ... a_(p+x). Причем символов a_1...a_x в нем 1, символов a_(x+1),...,a_(x+m2) по два, и так далее. Это и есть тот полиномиальный коэффициент.
Ну и все делим на общее количество слов d^(s+x). Вопрос откуда взялся (x!) ?
Если Стороны_Неотрицательны И (Правило_треугольника или Одна_сторона_нулевая_а_другие_равны)
Напечатать Нет
В авторском 222 строки :)
Но как я понял, можно сдать, если за логарифм считать хеши строк длины около 1000000 для каждой вершины. Это можно легко пересчитывать, имея хеши длины 1, 2, 4, 8, 16, ...
По-видимому, мы сами себе усложнили решение...
В нашем решении мы отдельно рассматривали компоненты связности с циклом и без цикла. Тогда в компонентах без цикла можно сразу посчитать все хеши (так как в таких компонентах всегда есть корень и это дерево), а в компонентах с циклом мы считали (n+1)-символьный хеш, при этом отдельно посчитали next[i][j] для элементов в цикле, а потом дфсами из элементов цикла считали оставшиеся части хешей.
В общем понятно теперь, как это можно было совсем быстро закодить. Спасибо :)
Этот новый символ можно сделать нулём, тогда этот частный случай исчезает сам собой. У нас так же и меньше 40 строк, да.
А без хешей там, видимо, даже авторы не умеют?
Мы вот так: http://pastie.org/1184542
http://ideone.com/O0yVK
А может кто-нибудь поскажет, как решать задачу B первого дивизиона (о k-простых последовательностях)? Спасибо.
Хотя не исключаю возможности решить ее динамикой.
У меня возникло ощущение, что недостаточно чётко было условие. Первый тип запроса - максимальное количество очков которое могло быть на промежутке времени [0, ti]. Хотя, возможно, ошибка и в моём решении.
http://pastebin.com/Cb5KNQJf
Да, нехорошо получилось. До меня только час назад дошло, что этот момент условия я забыл уточнить. Вроде кто читал, у них вопросов не возникало.
Я думал вы по другой причине не можете её сдать, после 3-х часов я увидел 2 минуса по E, посмотрел своё решение, нашёл у себя ошибку и сразу послал новые тесты.
Я не видел сабмиты участников, видел бы, послал бы клар. Постараюсь в дальнейшем не допускать таких ошибок.
Я английский вариант читал мельком, но подумал, что есть разница "for the first t seconds" и "on i second", но не спорю, надо было уточнить.
Решение через быстрое возведение матрицы не проходит, или вы не так решали?
На контесте МГУ была задача про карточки. В условии было: "В процессе игры счёт не должен опускаться ниже нуля". Многие не так поняли, было сначала много-много минусов, а потом много-много плюсов. Показалось, что я более-менне также написал.
мы не досмотрели это в условии
но с другой стороны если выходят максимум 2 из одной вершины то количество частей может быть различным в зависимости от проведения диагоналей
ответ формула
количество точек пересечения (каждые 4 различные вершины дают точку) +
количество диагоналей + 1
если линейная, то как бысто посчитать все произведения m*k
кол-во диагоналей+кол-во точек пересечения диагоналей+1
то есть
(n*(n-3))/2+(n*(n-1)*(n-2)*(n-3))/24+1
rez:=(n*n*n*n-6*n*n*n+23*n*n-42*n+24) div 24;
проходит на 100%
(n*(n-3))/2+(n*(n-1)*(n-2)*(n-3))/24+1
1 1 1 1
1 1 1
4 1
4 1 1
4 4 1
4 4 1 1
dp[free] - ответ в задаче для такой маски.
Пусть S(free) = множество всех непустых подмасок маски free.
Тогда
dp[free] = 1 / |S(free)| *
где P(x) - вероятность захватить множество x.
Крайние случаи:
dp[1] = 1,
dp[x] = 0, если нулевой бит x равен 0.
Ответ в задаче: dp[ (1 << n) - 1 ]
+ надо использовать алгоритм перебора всех масок длины n и всех подмасок каждой маски + O(3^n).