Top 200

по условию фигура полностью связана. И во входных данных тоже.

There is a solution for n^2log. You check symbols one by one for nlogn and also keep in mind dp[x] = min{y, you could have finished known prefix with x-prefix of a and y-prefix of b}.

I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.

We just construe answer one by one and for each position in either array keep track of minimal position in the other array such that we can construe prefix of answer we have so far from corresponding prefixes of arrays

My solution is O(N²), but it didn't pass test 9 because of the corner case.

I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.

For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.

Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).

Там все решается в целых числах (как и в большинстве задач на геометрию), зачем какой-то корень?

Прогнал локально, ожидаемо все тесты прошли.

RussianCodeCup, нет планов поддержать инвокеры на других ОС?

Same. Quite atificial condition that we can get rid of just by adding following to the end:

        if (maxElement(answer) < minElement(b)) {
            answer[k - 1] = minElement(b);
        }
        if (maxElement(answer) < minElement(a)) {
            answer[k - 1] = minElement(a);
        }

18 миллионов обращений к сету? Неплохо.

У меня зашло через Дейкстру, когда я начал добавлять только одну (следующую) раскладку из состояния за раз, а не все возможные. Сначала был TL.

Пока тренировку не представляется возможным залить из-за внутренних проблем Codeforces. Как только починят — сразу выложу.

И почему дейкстру? В динамике dp[i][j] = время нужно, чтобы набрать первих i знаков с актуальной раскладкой j, восможно взять массив 2N раскладок вместо цикла длины N; после имеем dp[i+1][k%N]=min(dp[i][k%N],dp[i][j%N]+a+(k-j-1)*b)+c для всех 0 ≤ j < k < 2N, k ≥ N, и это легко вычислить линейно.

Дейкстра с сетом получила тл22 на ркк, на кфе АС.

Yes.

Just count for every vertex v, number of pairs (u1<u2) ui!=v, such that Ang(u1-v-u2) < 90. Then you just need to subtract 2 * binom_coef(n,3).

Зашла с первой попытки.

Что за mask <= revMask?

You can try DFS, you just need hash table to check point exists or not and same for visited.

Вот она: https://www.codechef.com/problems/TAACUTE

Там можно и решения скопировать.

Например: https://www.codechef.com/viewsolution/10948326

Авторы RCC даже загуглить не попытались, а кто-то еще гонит на Глеба с Максом за то, что на Я.Алгоритме задача баяном с аткодера оказалась, хотя они искали и не нашли.

http://codeforces.net/blog/entry/52023

vovuh, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.

Thank you!

To RussianCodeCup: I still don't know why I got TLE for E during the contest. My submission is #27152353 of http://codeforces.net/gym/101397/status/E, and it's much faster (2027ms) than genomes_iz_2modules.cpp (2870ms). Is it possible that my code works very slowly on RCC's server?

Да, порядка месяца назад пришла