No, it's ok now

The same here :D
I used GeoGebra trying to generate a pattern that never lead to collinear but failed on that.
at a moment I thought that no test case will contains 2.5k input and brute force will pass I'm curious to know such big test cases.

I have actually managed to squeeze N^3 solution under time limit: http://pastebin.com/e6NDEj0q

but couldn't get all the bit juggling right during the contest time :)

And when you look at simplicity of Petr's solution after such efforts, it's jaw-dropping :)

Точки для простого p > n должны давать хорошую конфигурацию.

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

Я запихал в вектор полярные углы всех точек [0, 2*pi) и отсортировал. После перебирал пары точек p1, p2, причем p1, p2, (0,0) образуют правый поворот, если не так, то поменяем их местами. Пусть полярные углы этих точек a1 и a2, соответственно, тогда третья точка треугольника должна быть с полярным углом из интервала (a2 + pi, a1 + pi), количество таких точек получим из вектора, используя lower_bound\upper_bound. Нужно еще разобраться со случаем, когда a1 + pi >= 2 * pi. O(n² * log(n))

Если треугольник ABC не содержит начала координат, то углы AOB и AOC ориентированы против часовой стрелки. Собственно, переберем точку A, найдем количество k кандидатов на точки B и C, вычтем из ответа C_k².

Я решал так: инвертируем перестановку. Теперь нам надо из данной перестановки получить 1, 2 ... n

Если уже всё на месте — 0.

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

Посчитаем, сколько нечетных чисел в первой половине. Путь это будет число x. Этого числа достаточно, чтобы охарактеризовать текущее состояние. Нам надо из начального состояния x = s перейти в состояние x = n / 2. Это, например, бфс.

Как из текущего состояния найти все возможные переходы? Нужно подумать, сколько минимум и сколько максимум нечетных чисел мы можем из первой половины отправить в первую же. И сколько из второй. Сложить mn и mx для этих двух половинок. И это как раз будут состояния, достижимые из данного. Т.е. один сплошной отрезок из состояний. Где-то тут, возможно, кроется линейное решение, но я и за квадрат еле успел придумать и написать, хех.

Вот как-то так выглядит мой бфс (N в коде уже равно n / 2):

while (!q.empty()) {
	t = q.front();
	q.pop();
	int mn = max(0, t - N / 2), mx = min(t, (N + 1) / 2);
	int tt = N - t;
	mn += max(0, tt - (N + 1) / 2);
	mx += min(tt, N / 2);
	for (int i = mn; i <= mx; ++i) if (d[i] == INF) {
		d[i] = d[t] + 1;
		q.push(i);
	}
}

I had an idea that is based on writing down the basic equations and then noticing that, for instance, the part that depends on the cursor can be isolated since everything is additive:

So, $f(m,i)=f(m)+d_i$, where

So $f(m)$ seems to only depend on the number of set bits in m, and can be calculated via Gauss elimination. BUT that is not quite true, because if m = 0 or m = 2ⁿ - 1, then f(m, i) = 0 and we have to adjust for that. There is probably a way to derive the adjustment (it can be separated since everything is additive) from the mask, but I couldn't find it. There is also the possibility that I went completely the wrong way about it. There are some solutions in practice room but I didn't read them thoroughly and don't know if they're correct or not.

There was an announcement about maintenance before it went down.