VIII OpenCup Udmurtia GP

14 лет назад, # |

Соревнование окончено. Кто-нибудь может подсказать как сдавалась задача U?

→ Ответить

14 лет назад, # ^ |

Ссылка на условия

→ Ответить

14 лет назад, # ^ |

Наше решение, которое было тяжело писать за полчаса до конца и на которое поэтому мы забили(вполне возможно, что неправильное):
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!

→ Ответить

14 лет назад, # ^ |

1) если f[i][j] втупую считать, то ловишь TL.
надо считать динамику f[i][j][k] - то же самое, только считаем с k-го символа строчки j. Тогда пересчет происходит за O(1) и по времени проходит.

3) да, хешами проходит.

→ Ответить

14 лет назад, # ^ |

Спасибо большое! Ваша идея стала логичным продолжением нашей:-) Но теперь мы получаем ВА 21 при использовании хешей... Вы дорешали эту задачу? Может знаете в чем может быть дело?

→ Ответить

14 лет назад, # ^ |

Я ещё не оптимизировал что-то в процедуре генерации, так что пока валится по времени) А какие и сколько у вас хешей? Может просто в большом тесте получаются одинаковые хеши у разных строк?

→ Ответить

14 лет назад, # ^ |

Хеши по формуле: сумма p^i*s[i]. Сохраняю их значения в лонг лонг. Видимо проблема и есть в коллизии... Но если сохранять получающиеся строки, то тле получаю уже на 3ем тесте.

→ Ответить

14 лет назад, # ^ |

Неудачные основания подобрал для хешей

→ Ответить

14 лет назад, # ^ |

А как их стоит подбирать? Я пробовал разные, иногда из-за этого падает еще раньше:-(

→ Ответить

14 лет назад, # ^ |

Считай два long long по разным модулям, раз падает ещё раньше при разных p значит слетает не по случайности, а потому что действительно маленький размер хешей)

→ Ответить

14 лет назад, # ^ |

у нас с p = 43 все зашло.

→ Ответить

14 лет назад, # ^ |

Первый дивизион может кто-нибудь выложить?

→ Ответить

hydrastuff

14 лет назад, # ^ |

и второй

→ Ответить

14 лет назад, # ^ |

кэп подсказывает: http://codeforces.me/blog/entry/690#comment-10984

→ Ответить

http://158.250.33.215/~ejudge/files/opencup/oc8/gp3/pa03nnn-r.pdf

14 лет назад, # ^ |

→ Ответить

14 лет назад, # |

Задача О не сдавалась за куб на паскале, хотя такое же решение проходило на с++ :)

→ Ответить

14 лет назад, # ^ |

Куб проходил на Java.

→ Ответить

14 лет назад, # ^ |

Расскажите, пожалуйста, как вы решали О? В чем неверна эта идея: a[] - квадраты кол-ва билетов, p[i][j] - шанс игрока i выиграть приз j, sum - сумма значений a[].
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];

→ Ответить

14 лет назад, # ^ |

Я писал просто цикл, перебирая победителя первого, второго и третьего и прибавляя к вероятности первого приза первому победителю, вероятности второго приза второму победителю и вероятности третьего третьему перемноженную вероятность. Плюс не перебираем людей с нулем камней и используем отдельные случаи для 0, 1 и 2 человек с камнями. То есть:

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;

→ Ответить

14 лет назад, # ^ |

Мы делали в точности то же самое, но словили по ней -10.

→ Ответить

14 лет назад, # ^ |

Да, писали мы на C++, получали WA10.

→ Ответить

14 лет назад, # ^ |

Спасибо, разобрался в своей ошибке:-) Нужно было вероятность получения третьего приза считать немного иначе, я умножал на общую вероятность получения игроком k второго приза. А нужно было умножать на вероятность получения второго приза игроком k при условии, что первый приз выиграл игрок j. Теперь вместо ВА 2, ТЛЕ 9... Пишу на С++

→ Ответить

14 лет назад, # ^ |

Всё, сдал:-) Рассмотрел случаи, когда игроки имеют ноль билетов и прошло)

→ Ответить

14 лет назад, # ^ |

Может быть вы использовали в паскале тип extended? Действия с ним медленнее, чем с double.

→ Ответить

14 лет назад, # ^ |

И так и так пробовал. А вы сдали на паскале?

→ Ответить

14 лет назад, # ^ |

Нет, я сдал на С++, просто предположил почему может быть замедление на паскале:-)

→ Ответить

14 лет назад, # |

Задачу K можно было сдать читерно. Напишем жадное решение. Оно не будет проходить около 6 тестов из тестсета. Далее пишем перебор с прекращением работы после 7 секунд. Я не нешёл теста, которое бы повалило это решение.

Моё решение честное, но в нём 1200 строк.

→ Ответить

volkhin

14 лет назад, # ^ |

А какое честное решение?

→ Ответить

14 лет назад, # ^ |

Перебор без выхода по времени.

→ Ответить

14 лет назад, # |

Интересна задача H

→ Ответить

Egor	14 лет назад, # ^ \| 0 валиндынми являются треугольники с углами не более 120 градусов и a, a, 0, где а > 0 → Ответить

volkhin

14 лет назад, # ^ |

Зачем ограничение в 120 градусов? Во всяком случае тесты проходит и без него.

→ Ответить

Egor	14 лет назад, # ^ \| 0 Значит в задаче были гениальные тесты :) По крайней мере у меня проверялось что c² < = a² + b² + ab :) → Ответить

14 лет назад, # ^ |

Я слишком увлёкся вырожденным случаем, что совсем забыл про такие решения. Задача задумывалась как самая простая, поэтому неполнота тестов не так страшна.

Походу, я 59-м тестом хотел сделать 501 500 1000, но сделал 499 500 1000

→ Ответить

14 лет назад, # ^ |

Земляк! Помоги разобраться с задачей I (Охота на зайцев).
Не могу понять, их надо искать, только по генерируему вектору или по всей плоскости?
А, вообще у меня не проходит 21 тест по времени.
Вся программа работает быстро. Но как только начинаю проверять сколько точек лежит на заданном луче сразу ТЛЕ. Спасибо.

→ Ответить

14 лет назад, # ^ |

Откуда 120 градусов? Наш тренер доказал, что любой невырожденный треугольник подойдёт.

→ Ответить

14 лет назад, # ^ |

а почему? мне показалось, что не более 90

→ Ответить

14 лет назад, # ^ |

+10

Ну можно заметить, что оптимальная ломаная - это если мы проведем высоты из вершин треугольника, а потом соединим полученные основания высот. Тогда можно заметить, что если у нас есть любой треугольник, который удовлятворяет строгому неравенству треугольника, то можно провести в нем биссектрисы, а затем через вершины нашей ломаной провести прямые перпендикулярные биссектрисам. Тогда мы получим, что для любой ломаной, которая представляет собой невырожденный треугольник - ответ Yes. Все это видно на картинке

→ Ответить

14 лет назад, # ^ |

Да, мы тоже склонялись к этому, но порисовав я не получал больше 90 грудусов...=(

→ Ответить

freopen

14 лет назад, # ^ |

Поправьте, если туплю. Во входном тесте 2 3 4 - это и есть больше 90 градусов. Однако, ответ Yes

→ Ответить

14 лет назад, # ^ |

А задачку J не подскажете, полконтеста пытался свести ее к парадоксу о днях рождениях, ответ для пар получил...а как для троек и четверок?

→ Ответить

sdya

14 лет назад, # ^ |

Врядли можно свести к парадоксу о днях рождениях, но тут можно сделать по-другому. Просто посчитаем вероятность того, что у нас будет 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)).
Собственно говоря, реализация очень простая, но до решения догадаться не так просто.

→ Ответить

14 лет назад, # ^ |

спасибо, надо осознать написанное

→ Ответить

14 лет назад, # ^ |

что-то я никак не могу понять, почему в знаменателе числителя(!) стоит (x!).
посчитаем количество ситуаций, когда люди разбились на классы эквивалентности так, как нам надо. Выберем из 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!) ?

→ Ответить

sdya

14 лет назад, # ^ |

Я считал общее количество наборов людей для которых выполнено условие того, что всего людей 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! в знаменателе числителя.

→ Ответить

14 лет назад, # ^ |

все понял, спасибо. В моем решении я выбрал дни для каждого из людей, у которых уникальные дни рождения, а потом еще перебирал их перестановки в (S+x)!.

→ Ответить

907th

14 лет назад, # ^ |

Верно, только почему-то не заходит простая проверка на невырожденность. Почему? И зачем в задаче отрицательные величины?

→ Ответить

14 лет назад, # ^ |

Простая проверка на невырожденность + случаи типа 0 a a заходит без проблем.

→ Ответить

saigono

14 лет назад, # ^ |

-8

Очень глупая задача.
Если Стороны_Неотрицательны И (Правило_треугольника или Одна_сторона_нулевая_а_другие_равны)

Напечатать Да

Иначе
Напечатать Нет

→ Ответить

14 лет назад, # ^ |

Я знаю, спасибо :)

→ Ответить

14 лет назад, # |

Интересно, как решать задачу D. Мы сдали хешами и в решении порядка 200 строк кода. Но судя по результатам, многие сдавали задачу довольно быстро, поэтому может быть есть другое решение?

→ Ответить

14 лет назад, # ^ |

В авторском 222 строки :)

Но как я понял, можно сдать, если за логарифм считать хеши строк длины около 1000000 для каждой вершины. Это можно легко пересчитывать, имея хеши длины 1, 2, 4, 8, 16, ...

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

Скорее всего все известные решения D используют хэши. Но хэши бывают разные. У меня вышло на 90 строк.

Решение такое. Каждой вершине сопоставим строку которая получается если идти из нее. Очевидно что вершины эквивалентны если равны строки. Чтобы не рассматривать отдельно конечные строки все вершины у которых исходящего ребра направим в дополнительную вершину, с новым символом и замкнутую на себя.

Можно показать что достаточно сравнить 10^10 символов строк. Оценим это сверху как 2^40. Осталось посчитать хеш от первых 2^40 символов строки. Делается это так. Посчитаем куда мы попадем из каждой вершины пойдя на 2^i шагов. После чего используя эту динамику насчитаем хеши для первых 2^i символов строки.

Для перехода формула такая. next[i][j]=next[next[i][j-1]][j-1] для хеша аналогично.

→ Ответить

14 лет назад, # ^ |

По-видимому, мы сами себе усложнили решение...

В нашем решении мы отдельно рассматривали компоненты связности с циклом и без цикла. Тогда в компонентах без цикла можно сразу посчитать все хеши (так как в таких компонентах всегда есть корень и это дерево), а в компонентах с циклом мы считали (n+1)-символьный хеш, при этом отдельно посчитали next[i][j] для элементов в цикле, а потом дфсами из элементов цикла считали оставшиеся части хешей.

В общем понятно теперь, как это можно было совсем быстро закодить. Спасибо :)

→ Ответить

fetetriste

14 лет назад, # ^ |

Чтобы не рассматривать отдельно конечные строки все вершины у которых исходящего ребра направим в дополнительную вершину, с новым символом и замкнутую на себя.
Этот новый символ можно сделать нулём, тогда этот частный случай исчезает сам собой. У нас так же и меньше 40 строк, да.

А без хешей там, видимо, даже авторы не умеют?

→ Ответить

14 лет назад, # ^ |

Умеем. Алгоритм Хопкрофта минимизации автомата, работает за O(n log n). Наше решение с хешами чистая линия, не считая хеш-таблиц.

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

90 строк это вместе с почти неиспользованным шаблоном и вводом-выводом. Основную часть занимает как раз вывод, там неприятно перенумеровать классы чтобы соблюдалось условие.

→ Ответить

fetetriste

14 лет назад, # ^ |

А как вы это делаете?
Мы вот так: http://pastie.org/1184542

→ Ответить

PavelKunyavskiy

14 лет назад, # ^ |

Писал под конец,как следствие первое что пришло в голову.

http://ideone.com/O0yVK

→ Ответить

14 лет назад, # |

Друзья! А как Вы решали задачу M второго дивизиона о простых числах? Я думаю, что есть какая то формула для подсчета количества простых чисел из заданного интервала. В литературе нигде не нашёл формулы.

→ Ответить

14 лет назад, # ^ |

Находим решетом все простые числа до 10⁶. Теперь просеиваем ими наш отрезок, и считаем ответ)

→ Ответить

14 лет назад, # ^ |

+1. 2 решета. Первое обычное, второе - модифицированное.

→ Ответить

14 лет назад, # ^ |

Спасибо за помощь. Программа прошла(ОК).
А может кто-нибудь поскажет, как решать задачу B первого дивизиона (о k-простых последовательностях)? Спасибо.

→ Ответить

14 лет назад, # ^ |

формула M^(min(n,k)) + (M-1)^(max(0,n-k))

→ Ответить

14 лет назад, # ^ |

точнее произведение а не сумма

→ Ответить

14 лет назад, # ^ |

А как Вы получили эту формулу?

→ Ответить

14 лет назад, # ^ |

ну, сначала пока длина <=min(n,k) расставляем всевозможные m букв, а дальше оставшиеся n-k расставляем чтобы i-ая буква не совпадала с i-kой а это m-1 вариант для каждой буквы...
Хотя не исключаю возможности решить ее динамикой.

→ Ответить

14 лет назад, # ^ |

Какой тип Вы использовали для ответа?

→ Ответить

14 лет назад, # ^ |

Java.Math.BigInteger;

→ Ответить

Petr	14 лет назад, # \| 0 Нельзя ли увидеть 11 тест в задаче E? А то он похоже у всех команд падал. → Ответить

14 лет назад, # ^ |

У меня возникло ощущение, что недостаточно чётко было условие. Первый тип запроса - максимальное количество очков которое могло быть на промежутке времени [0, t_i]. Хотя, возможно, ошибка и в моём решении.

http://pastebin.com/Cb5KNQJf

→ Ответить

Petr	14 лет назад, # ^ \| 0 Оп-па. Да, мы все поняли, что надо очки после t_i секунды. Сейчас смотрим на русское и английское условие и все равно не можем понять как надо было до этого догадаться :( Сейчас поправим наше решение и пошлем в дорешивание. → Ответить

14 лет назад, # ^ |

Да, нехорошо получилось. До меня только час назад дошло, что этот момент условия я забыл уточнить. Вроде кто читал, у них вопросов не возникало.

Я думал вы по другой причине не можете её сдать, после 3-х часов я увидел 2 минуса по E, посмотрел своё решение, нашёл у себя ошибку и сразу послал новые тесты.

Я не видел сабмиты участников, видел бы, послал бы клар. Постараюсь в дальнейшем не допускать таких ошибок.

→ Ответить

Petr	14 лет назад, # ^ \| 0 Мы сейчас поправили и послали решение в соответствие с новым видением условия - TL 27. Так что тесты до 26-го теперь видимо точно правильные ) → Ответить

14 лет назад, # ^ |

Я английский вариант читал мельком, но подумал, что есть разница "for the first t seconds" и "on i second", но не спорю, надо было уточнить.

Решение через быстрое возведение матрицы не проходит, или вы не так решали?

→ Ответить

Petr	14 лет назад, # ^ \| 0 Так. Сейчас думаем как побыстрее ) → Ответить

Petr	14 лет назад, # ^ \| 0 Получили OK поиском периода (на котором просто +delta). → Ответить

14 лет назад, # ^ |

Авторское решение такое же. Наш тренер как-то доказал, что период всегда будет.

→ Ответить

14 лет назад, # ^ |

На контесте МГУ была задача про карточки. В условии было: "В процессе игры счёт не должен опускаться ниже нуля". Многие не так поняли, было сначала много-много минусов, а потом много-много плюсов. Показалось, что я более-менне также написал.

→ Ответить

Petr	14 лет назад, # ^ \| 0 Про какую ты задачу я не понял - наверное не решал; но не суть. Спасибо за контест! → Ответить

14 лет назад, # ^ |

С прошлых петрозаводских сборов, задача cards. Сейчас посмотрел, там не совсем так было. "It is not allowed to make your score negative."

→ Ответить

14 лет назад, # ^ |

Кстати, как вы сдали задачу F? Сами догадались или знали теорему?

→ Ответить

Petr	14 лет назад, # ^ \| 0 Какую теорему? Сами догадались. Андрей сначала научился дублировать строку, потом оставлять из длинной строки одну букву, потом при дублировании подставлять перед каждой копией свою функцию, тем самым скрестив первые два достижения - и получилось решение. → Ответить

14 лет назад, # ^ |

Теорема Карри-Шейнфинкеля. У нас на первом курсе был предмет, где на экзамен надо было учить эту теорему. Мне попалось задание, на её применение, я его решил и получил 5. Курс читал Н. Н. Непейвода, кто был на ижевских сборах, скорее всего, его знают.

→ Ответить

14 лет назад, # |

Судя по количеству Accepted'ов глупый вопрос, но всё же: как решается P Polygon из второго дивизиона?:-) Считается ли пересечением, если 3 и более диагоналей выходят из одной вершины? Или это допустимо?

→ Ответить

KirillB

14 лет назад, # ^ |

допустимо что 3 и более диагоналей выходят из одной вершины
мы не досмотрели это в условии
но с другой стороны если выходят максимум 2 из одной вершины то количество частей может быть различным в зависимости от проведения диагоналей
ответ формула
количество точек пересечения (каждые 4 различные вершины дают точку) +
количество диагоналей + 1

→ Ответить

14 лет назад, # ^ |

Брат программист! Я сам дурил голову с этой задачей. Выводил закономерности. А оказывается есть огромная формула для подсчета количества частей при пересечении диагоналей.

→ Ответить

JKeeJ1e30

14 лет назад, # ^ |

Я вообще не считал какую-то формулу шел такой динамикой: допустим мы уже имеем n-угольник, там как-то пересеклись диагонали. Теперь я достраиваю вершину напротив какой-то стороны. Та сторона становится диагональю, но, так как она не пересекает ни одну из ранее поставленных диагоналей нигде, кроме вершин, то следовательно ответ не увеличивается пока. Теперь постараемся провести из вновь поставленной вершины диагоналей. Каждая диагональ разобьет поле на k вершин в одной части многоугольника и m в другой(считайте сами сколько). Проводим эту новую диагональ, ясен пень, пересечет она m*k диагоналей. Проводим все диагонали из этой вершины, получаем ответ))

→ Ответить

KirillB

14 лет назад, # ^ |

а какая сложность в итоге?
если линейная, то как бысто посчитать все произведения m*k

→ Ответить

JKeeJ1e30

14 лет назад, # ^ |

А я не помню

На Екатеринбургском вроде так прокатило, а тут вроде формулку потребавалось вывести. Вроде это будет что-то типа суммы по j j*(i-j-2), ну посчитай, мне лень))) i-это наша динамика

→ Ответить

14 лет назад, # ^ |

там формула
кол-во диагоналей+кол-во точек пересечения диагоналей+1
то есть
(n*(n-3))/2+(n*(n-1)*(n-2)*(n-3))/24+1

→ Ответить

14 лет назад, # ^ |

Спасибо большое, а как вы пришли к такому результату?

→ Ответить

14 лет назад, # ^ |

на прошлом open cupe решали задачу про точки пересечения, пошаманили немного с формулой, расписали случаи до 7 и решили =)

→ Ответить

14 лет назад, # ^ |

А, ну тогда всё ясно:-) Мы не участвовали в прошлом туре(был региональный турнир в этот день)... Теперь понятно откуда столько принятых решений)

→ Ответить

14 лет назад, # ^ |

я и раньше видел эту задачу в Coci была

→ Ответить

KirillB

14 лет назад, # ^ |

попытайтесь проводить диагонали одну за другой

→ Ответить

14 лет назад, # ^ |

Так и пытались решать, но в итоге ничего путного не вышло... Попробуем ещё:-)

→ Ответить

14 лет назад, # ^ |

Мы, например, просто искали ответ как полином четвёртой степени, интерполировали по первым пяти значениям. Наверное, делается проще. А причём тут пересечение?

→ Ответить

14 лет назад, # ^ |

Как при чем? В условии задачи сказано, что никакие 3 диагонали не должны пересекаться в одной точке:-) А как вы получили этот полином?

→ Ответить

14 лет назад, # ^ |

Паша, есть такой прием. Интерполировать полинов по первым значениям какого-то ряда....но не всегда это работает, но тут было более, чем очевидно

→ Ответить

14 лет назад, # ^ |

первые значения получаем ручками

→ Ответить

14 лет назад, # ^ |

Что для семиугольника не совсем тривиально)

→ Ответить

14 лет назад, # ^ |

Ну, вроде понятно, что имелось в виду) Хотя да, можно понять неправильно.

Мы это никак не получили, интуиция. Эта функция примерно того же порядка, что и количество пар пересекающихся диагоналей, а их четвёртая степень от количества вершин. Значит, если это многочлен, то четвёртой степени. Если кто-нибудь сможет объяснить, почему это многочлен, не подсматривая итоговую формулу (и не выводя её), буду признателен)

А готовый ответ, конечно, наверняка несложно доказывается формулой Эйлера.

→ Ответить

14 лет назад, # ^ |

Простите за мою безграмотность:-) Не знал точного значения слова интерполяция. Вопрос снимается:-)

→ Ответить

14 лет назад, # ^ |

Простите за мою невнимательность) Я думал, вопрос был в том, почему это многочлен.

→ Ответить

14 лет назад, # ^ |

А вот и формула,
rez:=(n*n*n*n-6*n*n*n+23*n*n-42*n+24) div 24;
проходит на 100%

→ Ответить

14 лет назад, # ^ |

если я не ошибаюсь твоя формула это раскрытая
(n*(n-3))/2+(n*(n-1)*(n-2)*(n-3))/24+1

→ Ответить

saigono

14 лет назад, # |

Кто знает хорошие тесты на задачу C?

→ Ответить

14 лет назад, # ^ |

например
1 1 1 1
1 1 1
4 1
4 1 1
4 4 1
4 4 1 1

→ Ответить

14 лет назад, # |

А как T решать?

→ Ответить

14 лет назад, # ^ |

динамика по подмножествам.

→ Ответить

14 лет назад, # ^ |

Можно подробнее? А то та динамика, которую придумал я, была слишком медленной

→ Ответить

14 лет назад, # ^ |

Пусть free - это маска незахваченных городов.
dp[free] - ответ в задаче для такой маски.

Пусть S(free) = множество всех непустых подмасок маски free.
Тогда
dp[free] = 1 / |S(free)| * $\text{[math]}$ (P(x) * dp[free - x] + (1 - P(x)) * dp[free]),
где P(x) - вероятность захватить множество x.

Крайние случаи:
dp[1] = 1,
dp[x] = 0, если нулевой бит x равен 0.
Ответ в задаче: dp[ (1 << n) - 1 ]

+ надо использовать алгоритм перебора всех масок длины n и всех подмасок каждой маски + O(3^n).

→ Ответить

14 лет назад, # ^ |

Как отслеживать случай, когда у него не получается захватить подмножество городов и он в дальнейшем повторно будет его захватывать. Петли ведь получаются.

→ Ответить

14 лет назад, # ^ |

Это учтено во втором слагаемом равенства. Фактически, мы получаем линейное уравнение на dp[free].

→ Ответить