Не могу понять решение 275C (http://codeforces.net/contest/482/problem/C):

Я понимаю, как определять, является ли подмножество уникальным для строки, но не знаю, как найти вероятность выбора подмножества.

Она может быть различна для разных строк. Например, если даны строки

aax; aay; mnf

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

Разбор скрыт в черновиках.

Здраствуйте.

Я нашел описание min cost max flow, где описан процесс выдачи потенциалов: http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/min-cost-max-flow-2009/algorithm

Там не доказывается, что выбор потенциалов описанных образом позволит избежать появления ребер отрицательного веса.

Пусть у нас такая остаточная сеть. Вершина 4 -исток. Вершина 5 — сток:

Найдем кратчайший путь веса 1 4->0->2->5 и протолкнем через него одну единицу потока. Получим такую остаточную сеть:

Найдем такой кратчайший по весу путь:

Он действительно кратчайший

4->1 вес: 0+0-0=0

1->2 вес: 1+0-1=0

2->0 вес: -1+1-0=0

0->3 вес: 1+0-0=1

3->5 вес:0+0-1=-1 (Ребро с отрицательным весом)

Т.к. появилось ребро отрицательного веса, гарантий, что Дейкстра сработает нет. Я неправильно понял описанный по ссылке алгоритм, или он неверен?

Не подскажете, как решать эту задачу?

Делал так: завел карту nums<long long,int> чисел, для каждого числа указал, сколько раз оно встречается и исходный массив 'a'.

Для каждой пары (i;j), j > i к ответу добавлялось: 2 * (nums[a[i] + a[j]] - (a[i] =  = 0) - (a[j] =  = 0))

Работает за . Получает TL.

код

Здраствуйте. Во время написания игры столкнулся с задачей, которую не могу решить. В игре у вас есть меч и им надо отбивать пули. На каждой итерации меч (для начала, я хотел бы решить, упростив его модель до отрезка) подвергается двум геометрическим преобразованиям:

1)Точка, относительно которой он вращается совершает перемещение на вектор v из позиции (x0;y0)

2)Все остальные точки меча вращаются относительно нее на угол omega.

На каждой итерации пуля перемещается на вектор z. Изначально она находится в точке (m;n)

Меч должен отбивать пули, с которыми столкнулся. Разработка ведется в Unity3D, с физическим движком PhysX. Как оказалось, его стандартной точности не хватает для расчета этих преобразований и пули застревают в мече.

Использование различных скриптов, разработанных сообществом Unity для решения этой проблемы мне не помогло. Увеличение количества итераций физического движка в секунду исправляет ошибки при столкновении, но убивает производительность. Подробнее я писал в answers.unity3d.com, но получил только решения для случая, когда движется либо меч, либо пуля, но не то и другое сразу. (http://answers.unity3d.com/questions/749102/collision-of-fast-objects-does-not-work-yes-i-goog.html)

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

(Длина меча постоянна, просто картинка не совсем точна).

Vector2 — класс двухмерного вектора. magnitude() возвращает его длину, normalized() возвращает коллинеарный ему вектор длины 1.

p1 и p2 — точки пересечения траектории пули и траекторий неподвижной точки меча и точки меча, наиболее удаленной от неподвжной соответственно

Определим функции

Line line_from_vector_and_point(Vector2 vec, Vector2 p)

Vector2 lines_intersection(Line l1, Line l2)

float points_distance(Vector2 p1, Vector2 p2)

смысл которых соответствует названию.

Далее, можно найти Vector2 p1=lines_intersection(line_from_vector_and_point(v,new Vector2(x0,y0)),line_from_vector_and_point(z,new Vector2(m,n)));

Vector2 p2=p1-z.normalized()*SWORD_LENGTH;

Пусть tb(r) — функция, которая по расстоянию r точки отрезка p1;p2 от p1 возвращает время, за которое пуля достигнет этой точки.

Пусть ts(r) — функция, которая по расстоянию r некоторой точки отрезка меча от оси вращения этого меча возвращает время, за которое данная точка окажется на отрезке p1;p2

Я предположил, что f(r)=ts(r)-tb(r) — унимодальная функция, при условии, что omega всегда менее 180 градусов и попытался это доказать. Если это верно, то точку столкновения можно определить троичным поиском.

tb(r)=(points_distance(new Vector2(m,n),p1)-r)/z.magnitude()

К сожалению, выразить ts(r) я не смог.

Координаты точки меча от радиуса и времени выражаются как

(x0+v.x*t+r*cos(omega*t);y0+v.y*t+r*sin(omega*t))

ts(0) легко найти как points_distance(new Vector2(x0,y0),p1)/v.magnitude(), т.к. речь идет о точке меча, движущейся по прямой, но остальные перемещатся по кривым, длину участка и скорость прохождения которых у меня не получается определить.

Есть ли способы найти ts(r), или упростить модель столкновения?

Заранее благодарен.

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

Первая: http://acm.petrsu.ru/site/problems/problemset/0289/ . Дана некоторая клавиатура (размера 3 на 10) и текст, который робот должен на ней набрать. Нажатие каждого символа занимает одну минуту. Перемещение пальца – одну минуту. Пробел всегда можно набрать одним нажатием (без перемещений).

Палец представляет собой точку (x;y) Никакие 2 пальца не могут находиться в одном столбце клавиатуры. Пальцы также не могут менять порядок (Указательный не становится правее среднего и т.д.). Руки не могут менять порядок, и на одной руке – 4 пальца.

Операция перемещения – изменение координаты x или y пальца, но не обеих сразу.

Так как палец может иметь y от 1 до 3, и быть сдвинутым не более чем на 2 позиции (иначе какие-то из них будут меняться местами), для кодирования достаточно 9 значений. Всего 9^8=43046721.

Всего символов 20, и даже если мы научимся вычислять расстояние между позициями за без дополнительной памяти, граф [позиция][номер символа] будет иметь 344373768 вершин при ML 256Мб. (TL=5 с)

Жадность не проходит, например если к клавиатуре из условия набрать текст pon (указательный палец переместится на p, и далее не будет разницы, каким из двух ближайших пальцев набирать o, хотя указательным правой — выгоднее)

Брутфорс по пальцам, которыми мы набираем текущий символ, не проходит по времени, если символы на клавиатуре повторяются.

Вторая лежит в архиве комбинаторных алгоритмов того же сайта под номером 24. Это единственная задача, которую я видел, с ограничением по времени в 180 секунд. (ML – 256Mb).

В ней надо найти количество кратчайших путей коня по доске n x n из левого верхнего угла в правый нижний. n до 10^5

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

Вообще, для расчета значения в клетке нужен только квадрат 5 на 5 клеток с центром в ней. Но верхняя клетка может рассчитываться через нижнюю, а нижняя через верхнюю (тоже верно для левой/правой), поэтому нельзя просто рассматривать ряды таких квадратов, отсекая их от доски.

Буду благодарен за помощь.

Upd: Архив комбинаторных алгоритмов:http://acm.petrsu.ru/site/contest/combalgs_archive Ссылка на pdf второй задачи: acm.petrsu.ru/site/problems/combalgs_archive/024/

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

В первой надо найти число способов наградить k работников из n так, чтобы никакие два награжденных не стояли подряд по простому модулю. Очевидное разбиение на подзадачи d[i][j] – ответ для i работников, из которых j надо наградить. d[0][0]=d[i>0][0]=1; d[0][j>0]=0

Из k выбранных одного мы наградим первым => ответ можно разбить на независимые множества, по его номеру. Что-то вроде цикла по t от 0 до i по всем номерам. d[i][j]+=d[max(i-t-2,0)][j-1]

Проблема в том, что 1<=n,m<=10^5. Т.е. если по памяти еще можно оптимизировать, раз нам не нужны значения d[i][j-p] для вычисления d[i][j] если p>1, то по времени квадрат не проходит. Можно ли разбить на подзадачи более эффективно, или надо искать формулу?

Во второй определена функция g от последовательности чисел, которая возвращает натуральное число, равное длине максимальной подстроки из одинаковых чисел, или любой из них, если таких много. Надо найти сумму g по всем таким последовательностям, если на одной позиции могут стоять целые числа на интервале [1;c]. Само условие: http://tinyurl.com/lzkhbmn

Я написал решение за куб, который хотя бы не получает WA. Можно посмотреть здесь: http://pastebin.com/LPW2JDzH

Моя идея — найти d[pos][len].total как количество последовательностей длины pos, в которых не более len одинаковых символов стоят подряд, а d[pos][len].num не более len, и не менее len. Потом можно посчитать сумму всех d[n][j].

Пусть на позиции pos мы хотим поставить i одинаковых чисел справа. i принадлежит промежутку [1;lim]. (lim выбирается так, чтобы не превосходить len, и чтобы не создавать последовательностей длины больше n) Тогда из нулевой позиции мы можем сделать это c способами, а из ненулевой только c-1 м (Т.к. мы не можем ставить то же число, что и на позиции pos).

d[pos+i][len].num обновляется, когда мы ставим после num текущих любые числа, или когда ставим ровно len чисел.

Но из-за того, что внутри циклов достаточно дорогие операции, код падает с TL. Т.к. динамики с разными len получились независимыми, можно искать выражение d[pos][n] через d[pos-1][n], но я не представляю, как это делать.

В контесте, где большинство задач решаются жадностью, нашел такую: "Постройте все сочетания из n элементов по k в таком порядке, чтобы два соседних сочетания отличались друг от друга не более чем одним элементом. Если существует несколько решений, выведите любое"

n и k от 1 до 15 TL 2 секунды ML 64 мб

Подразумеваются перестановка сочетаний, полученных в лексикографическом порядке, т.е. сочетание 2 1 система не засчитывает, в отличие от 1 2

Я не могу придумать параметр для сортировки, потому что количество различных элементов — относительная величина, и его не получается выражать через количество различных элементов с заданным сочетанием

Дополнительное условие для ветки рекурсии при генерации сочетаний, которое не нарушило бы их число/упорядоченность тоже не очевидно.

Как ее решать?