That was a stupid joke.

me too

I don't know anything about it.

It is guaranteed that each node of the graph is connected by the edges with at least k other nodes of the graph.

Therefore it's possible to form cycles from any point (I think) So I do a DFS on node 1

Let's go from vertex 1 and build a chain. At each iteration, if we are in vertex v, if exists some vertex u, that is in our chain at distance at least k, then we go to it and end the cycle. Else some vertex u exists such that it hasn't been visited yet, so we go to it. At some moment we'll end the cycle, because it's only finite number of vertices at all.

Build up the cycle as a path, until the last vertex of the path is the same as first one. Start with an arbitrary vertex. For the first K+1 vertices of the cycle, use a greedy approach — K times choose one vertex which is not in the path and connected to the last vertex of the path. There will always be one (because at most K-1 vertices apart from itself are in the path, so there must be at least 1 neighbour vertex left). Now, augment this path in the same way, until you can't do it. Then, take the last K vertices of the path; the last of them will have at least one neighbour other than those, but all his neighbours are in the path, so there must be a neighbour X of the last vertex of the path; add it to the end of the path. This way, there's a simple path in the graph, which starts and ends at X, and contains at least K vertices. BTW the time complexity is O(N+M), and it's optimal.

Переберём в лоб первых 4 позиции. Остальные восстанавливаются однозначно. Меня взломали, но я думаю, что если писать более аккуратно, это заходит.

Для n=5 ответ 1 2 3 4 5, для n=6 ответ находим перебором, иначе находим ближайшее к текущему число — для них количество равных чисел, с которыми они соединены, равно двум, и продолжаем поиск из того, что нашли

No.

Case N=5 is clear. Bruteforce N=6. For N > 6, there are vertices a,b,d,e, all connected to vertex 1, and connected in the order in which they appear on the cycle: a-b-1-d-e; among them, only b and d are also connected. So you can find b and d — the only points which have 2 common neighbors with 1. You now have a part of the cycle: b-1-d. If you have a part A-B-C, then you can find the next vertex D on the cycle (A-B-C-D-...), because it's the only common neighbor of B and C other than A. Complexity: O(N).

Мы её еще допилим. Будет еще лучше!

One dfs is enough to find a solution for this problem. That's why backtracking needs only one branch to find the answer so it works in O(N + M).

At least one AC solution fails at this test:

7 8 2
1 2
2 3
3 4
4 2
1 5
5 6
6 7
7 5

My guess is than in all tests vertex number 1 is on the needed cycle.

thanks i still don't believe that i finished second

I see something strange in your contest stats, it seem that the solution for B is still in queue o.O

but the limits aren't good for this problem... if k = n / 4 the complexity is n/2*n/2*n/4 = O(n^3) which should not work in 3 sec i dont think there are faster solutions cause all the sources are like this

Your rating depends on how well other people did in the contest as well. Probably almost everyone did solve at least 1 problem. So that's why your rating did not increase.

I think if you want to increase your rating, you should learn a lot of things before taking the next contest.

Maybe because you need to solve more than just the first problem to increase the rating :D

1 — Рейтинг уже пересчитали.

2 — Думаю не все мутили бэктрэкинг. У меня на этот тест выдало 3 4 3 2.

It's incorrect input because "It is guaranteed that all given squares are distinct."