What do you mean exactly? Top-50 will get t-shirts in the mirror contest. So be ready for fight!

Даже не знаю что сказать...

Парсоч?)

Все скопипастят парсоч, а там будет задача про Анатолия Ивановича

u can't compete. VK Cup 2015 Round 3 (unofficial online mirror, Div. 1 only)

I think the opposite of "upvotes" is "downvotes" instead of "negative upvotes"...

Команда зарегистрирована :)

Запасные аккаунты зарегистрированы. :D

Вероятно, у AK_47_NAGIBATOR было бы больше шансов пройти в финал, если бы не несовершеннолетние участники

Вы не загадками говорите, а напишите мне личное сообщение.

I think it wasn't. I've tried binary search.

You can't use binary search — for any cycle in given graph, answer should be divisible by length of this cycle.

3 2 3 1

k=3 works k=4 does not

I failed to solve this problem, but I'm pretty sure your condition x ≥ k does not hold.

Consider a cycle 1 -> 2 -> 3 -> 1; for this example, k = 3. Setting k = 4:

f⁴(1) = 2, f⁴(2) = 3, f⁴(3) = 1.

f⁸(1) = 3, f⁸(2) = 1, f⁸(3) = 2.

What needs to be solved turns out to be a system of congruences, I think.

It's not binary search. Because if F_i(x) is not idempotent this doesn't mean that F_t(x) is not idempotent for all t less than i. For example in the third sample F_4 is not idempotent while F_3 is.

Hint: k can be larger than 100000, or 10^9 (I think).

Hint: Maximum possible answer is around 10^14

I tried 1 to 2500000! and got runtime error 8 times

I think answer of test 9 is bigger than 2500000.

The gist of the problem is to tranform it into one about graphs. We construct a graph with edges (i, f(i)), we see that f(x) is just the neighbor of node x, and f^k(x) is the kth neighbor of node x. Now because every node has an outdegree of exactly one this graph can be decomposed into cycles or paths that lead to cycles. Now the condition f^k(f^k(x)) = f^k(x) can be interpreted as the 2*kth neighbor of node x should equal it's kth neighbor. For nodes that are part of a cycle the answer is the a multiple of the length of the cycle(because k must satisfy the modular equation k ≡ 2 * k(mod length) which is equivalent to k ≡ 0(mod length)). So if there would be only cycles the answer would be the LCM of all the lengths of these cycles. Now what about paths? We notice that we need to pick a k such that it reaches a cycle, then for any K ≥ k we will just be walking through our cycle, so just take the length of the longest path to a cycle then pick a constant c such that c * lcm_of_cycles ≥ longest_path.

The contest Round 1 and Round 2 had the editorial, so I can pridict : will have the editorial.

I also hope it will become the trust, because I can't solve anything in 6 problems

Все? Звучит так, как будто по ней было больше 100 взломов. Меня, например, можно было взломать на ТЛ, но для этого нужно было сгенерировать тест с большим ответом.

на переполнении инта

Looks more like a random fluctuation in run time.

I'd also use less copy-paste if I were you :P

It's like a joke. Unfortunately for you.

Had the same issue... Trusted cin/cout too much; should've used fast input method written on my template :'(

http://mirror.codeforces.com/contest/542/submission/10989470

http://mirror.codeforces.com/contest/542/submission/10989944

I just wrote up a quick python script to see what max answer could be. Basically, you're looking for a bunch of numbers that sum to <= 200, and have maximal LCM. So just take the first primes with sum <= 200 and find their product.

Edit: This clearly isn't actually correct, see Zlobober's comment below.

Maximum orders of permutations of n elements.

Так и решать, только различные простые.

Да, нужно было найти количество решений уравнений (p₁^k₁ + 1) * .. * (p_s^s₁ + 1) = A, где p₁, p₂, .., p_s -  различные простые числа. Я написал перебор с некоторыми отсечениями и она прошла. Вот мой код 10987822

Если кратко:

Сканлайн. Для каждого второго отрезка пробуем его пересекать с первыми. Есть 3 типа пересечений — первый отрезок полностью включен, пересекает левую границу или еще не окончен. Для первого варианта — ДО на максимум, где храним Ф(левого конца) = длина отрезка. Для второго — ДО на максимум, где храним Ф(левого конца) = правый конец отрезка. Для третьего — храним сет ныне открытых отрезков, остортированный по левому концу.

Переберём отрезок [a_i, b_i].

1) Оптимальный ответ пересекает a_i -- считаем максимальное r из тех, что начинаются раньше a_i. Это пара циклов.

2) Пересекает b_i. Симметрично.

3) Лежит внутри. Тогда сканлайн: пусть стоим в каком-то b_i. Нас интересует максимальная длина отрезка, который начался после a_i (то, что он уже закончился выражается в том, мы добавляем [l_i, r_i] в точке его конца). Это дерево отрезков для максимума.

Вроде неадекватной реализации нет.

Я убрал все рекламные ролики, чьё окно времени полностью входит в окно какого-то другого ролика. Тогда оставшиеся ролики сортируются одновременно и по левому краю, и по правому. Дальше я прохожу по каналам и для каждого нахожу бинарным поиском последний ролик, пересекающий левую границу предоставляемого каналом окна (то есть заканчивающийся позже её) и первый ролик, пересекающий правую границу (то есть начинающийся раньше её). Можно или взять этот, или взять тот, или взять самый длинный ролик на отрезке между ними (range minimum query, который можно реализовать тысячей способов).

I reduced it to knapsack with all weights as powers of 2 which can be solved greedily.

Another approach: dp[height][free]: maximum total interest value of the tasks in tree when we use tasks with T - t[i] ≤ height and we have at least free free leaves.
10989745

I used a simple approach. We will split tasks by time. Every minute form a level. Start from the lowest level that contains at least one task. Combine two tasks in this level with the maximum interest. Add the result as a task in next level. If there is only one add it to the next level. If the level is empty precede to the next level. If you reached the highest level (T) the answer is the maximum interest in this level.

Here is my implementation => 10989241

Better is to always give a simple problem, so that at least every one has a submission.

I think so. Let's sort ducks by their tails positions. For each duck, let's calculate the answer ignoring ducks with tails behind this duck's tail. Assume that this duck ends at t. I claim that we will ignore this duck, or shoot at non empty prefix of sequence: t, t - r, t - 2r, ... We can check all meaningful prefixes by iterating over previous ducks.

Number of divisors of A is O(sqrt(A)). But what is the number of Bad Primes in worst case? ( I think your dp array size is O(A) ) :)

The tons of operations on maps are causing you to lose insane amounts of time in memory allocation. Just get rid of them and use static arrays instead: 10992963

And you can even reorder the dp dimensions for extra cache-friendly brownie points: 10992968

This is editorial, but it is not translated.

The translated version of editorial appeared. Sorry for the delay!