Всем привет!
Сегодня, 23-го октября (в воскресенье) в 12:00 (по Москве) начнется онлайн трансляция недавно завершившегося четвертьфинала Южного подрегиона NEERC. Два дня назад это соревнование состоялось в Саратове на базе Саратовского ГУ, а сегодня вы можете принять участие в нем неофициально. Участники официального соревнования будут присутствовать в текущих результатах. Условия задач будут доступны как одним PDF-файлом, так и в HTML по одной задаче. Для участия перейдите на сайт http://acm.sgu.ru.
После контеста здесь можно будет обсудить задачи. Надеюсь они вам понравятся.
Председатель жюри четвертьфинала,
MikeMirzayanov
Короче, задолбался исправлять отдельные слова, что непонятно-спрашивайте.
Если я не ошибаюсь (не сдавал), то следующее верно:
Рассмотрим все числа, которые получаются заменой одной буквы на 1, а остальных на 0.
Если различных букв 10, то вычтем из всех минимальное из них, а само минимальное помножим на 45
GCD == GCD полученного набора [Он из не более, чем 10 чисел. Вся вычислительная сложность в разложении на множители]
Доказательство именно этого факта чуть выше. Или же вот здесь в комментариях
Microsoft Visual C++ 2010 Express. Хотя да, может 2005я плохо относится к lld.
Путем проб и ошибок нашел. Если одновременно пользоваться cin и printf/scanf, то студия нормально хавает(VS 8 c++), а gcc - нет. Что конкретно там творится - не знаю, но после того как переписал полностью на потоковый ввод/вывод прошло под gcc. Так что, либо синхронизируйте потоки, либо вообще не смешивайте.
Я писал bfs по состояниям (состояние = клетка + битмаска, задающая, съедена ли та или иная чёрная фигура).
yeputons, демон, как ты умудрился сдать в 5:00?
Думаю, виновато округление времени
Вот если бы сдал на 5:01 - это было бы колдуем :) Где-то для пятичасового контеста были прецеденты.
(кажется, проверялка ставила время фактической проверки вместо времени посылки).
Какая у вас сложность? У меня со сложностью (2 ^ 14) * (14) * ((15) * (15) + 14) операций проходит.
(Не в ту ветку, ответ на вопрос Malinovsky239)
for seg1 in vertical segments
for seg2 in vertical segments (index of seg2 > index of seg1)
{
curCnt = 0;
for seg3 in horizontal segments
if seg3 intersects seg1 && seg3 intersects seg2
curCnt++;
ans += curCnt*(curCnt-1)/2;
}
print ans
Could you explain your approach and share the code, if possible?
- Если u + 1 < x + y. Т.к. в этом случае второй игрок может выбрать вершину на кратчайшем пути между этими программистами и в зависимости от хода первого игрока, приближаться к соответствующему программисту. В силу неравенства второй игрок наймет обоих программистов раньше первого.
- Если не существует 2 вершин v1 и v2, таких что они обе лежат на каком то кратчайшем пути между программистами, расстояние до вершины выбранной первым игроком до v1 и v2 равно 1 и расстояния от v1 и v2 до программистов совпадают. Если они существуют, то несложно построить выигрышную стратегию для первого игрока.
Предподсчитаем кратчайшие расстояния от всех трех программистов, тогда хода первого игрока мы может быстро определить x, y, u.Итак, центр дерева в вершине. Выкидываем из дерева все ребра, что не входят в диаметр и подвешиваем на центр. Полученное дерево мы назвали "веник":) ибо все пути от центра до листьев одинаковые. Дальше вполне себе очевидная динамика на венике - наименьшее количество денег, которое надо потратить чтобы на любом пути от вершины до листьев было хотя бы одно удаляемое ребро. Пусть мы все посчитали, ответом будет сумма дп по детям корня минус максимум по детям корня. Дальше остается только построить ответ (не забыв при этом про случай когда центр был на ребре).
Решение с разбора.
Решается динамикой по поддеревьям.
Найдем центры дерева. Их либо 1, либо 2 штуки.
Пусть центр один. Пусть из него идут несколько ребер, и в направлении K из них длиннейший путь из центра до некоторого листа максимален. Тогда для уменьшения диаметра нужно уменьшить длиннейший путь в K-1 направлениях. Подвесим дерево за центр, и запустим динамику, которая считает стоимость уменьшения максимального пути до листа в поддереве вершины. Пересчитывается думаю понятно как.
Если центра два, появляется еще немножко колдовства, например нужно учесть, что диаметр можно уменьшить, выпилив ребро между центрами.
UPD: охщи, слоупочина, ну пусть два разбора будет.
Нигде наверно. Михаил Мирзаянов вживую проводил.
in the all rest you are right
How can you know that brute-force is too slow for this problem?
I only see 10! different possibilities, and at each possibilitie you just calculate the gcd with the previous gcd. Is the gcd operation (euclidian's way) to slow for this strategy?
I got AC by just checking 10 random numbers! 10^5 is so much!
And how to approach the Berland Chess problem, constraints says solution will be exponential, but looks too complex for me, please elaborate.
[nice habbit btw. :) ]
I guess you are telling it will be lesser, but how?
C частными случаями получается короче :)
Идея - динамическое программирование. Сложность - O(N). Для каждого банка B ищете самый правый банк A левее банка B, который еще можно ограбить. Теперь, если вы грабите банк B, то можете вместе с ним грабить любой банк левее A и включая A. Додумайте сами.
Magic.
It's proofable that any array can be sorted in no more than 2 multiswap operations.
If array is sorted, answer is 0.
Now, let's suppose that all numbers in array are distinct. So, we can consider this array as some permutation. Have a look at graph representation of this permutation.
Answer is 1 if this graph contains cycles only with length no more than 2 (we can swap elements of this cycles and sort array this way).
If there is at least one cycle of length more than 2, answer is 2. You can notice that swapping two elements of some cycle, divides this cycle into two cycles. This way by one multiswap operation you can divide any cycle into cycles of length no more than 2. goto previous paragraph.
If not all numbers in array are distinct, we can enumerate all identical numbers as consecutive distinct numbers, and apply algorithm above, so we can still sort array in no more than 2 operations. But not any enumeration will form permutation which requires minimal possible amount of operations for sorting. So, I don't know, what exactly should we do if not all numbers are distinct.
Exactly - try to use greedy matching for sorting in one step, if this fails and two steps are required, you can assume that this is a permutation and use the solution above.
Надо ли было в явном виде искать точки пересечения?
> b=ind+1, line 109
Seems to be wrong for test like this
4 1
100 100500
200 1
300 1
400 100500