Any help with the last one? I observed that 2 permutations are possible for even, but I couldn't get the other part of the editorial.

Nice problemset!

This was one of the best contest which I do in last 4-5 months! My opinions about tasks and maybe some advices for greater contest in future :

The first task was nice and easy, good for that place. Maybe graph should have been constructed on some other way ( without intersections between diagonals ), but that isn't big deal :)

The second task is good dp problem, I like it very much. It is amazing to see that someone solved it in 10 minutes.

The third problem, also was interesting, generally that is fine task. But I think it is easy to find that we talk about Fibonnaci numbers and coefficient C isn't very important. After that it is obvious to see the sum F[i-1]*F[j-1] + F[i]*F[j] must be some number with certain rule. I think many guys could guess answer with trying brute force solution for smaller constrains or even find on the internet given sum.

For the fourth task I will say right task on the right place :)

Edit: Now I saw editorial for this task and I think I solved it on other and possible easier way. First I used monotonic queue to find range where i-th element is the minimum. After that I used some kind of mapping and summation sum[X] — in how many intervals element with maps bigger or equal to X is the minimum. At the end with using simply math I could find needed answer for each element in the array.

The fifth problem is very good for me, despite I couldn't find any better solution than modified recoursion. I put one line before recoursion and got 20 more points. I put line :

if (k>1e6) printf("%d",-1);

That is a lot of points for such a little and unimportant optimisation, possible I could earn more points if I put on the right side number 50-100.

The difficulty of contest was nice for all HR users, except the second task (it is much harder, for me that is enough even for the third), also my advice that you should put smaller subtasks in the statements. That is usual thing in all other long contests. Setter or manager won't spend a lot of time for it, but it is useful and shows seriousness in work.

Thanks again for nice round.

Sorry for several posts, but Codeforces had some bug and I clicked around 10 times to post my comment :)

(CF has server and LaTeX problems...)

I solved the last problem by writing a bruteforce and observing a pattern: for even permutations, there are only two permutations; for odd ones:

• if we count permutations starting with x for x=1..N, we get 2,3,7..,power of 2,the same sequence repeated backwards..7,3,2

• the number of permutations is the sum of them, something like N*2^N; any permutation in the second half can be computed by replacing K by the number of possible permutations+1 — K, computing that permutation and replacing each of its elements by N+1- it (it seems some of the following rules have inverted greater/smaller there?)

• if we count permutations among those 2,3,7.. starting with the same triplet, we get 2,3,7,..,power of 2

• if we've reached the "power of 2" part, there's a different pattern — add some pairs until the last added element is N/2+1, then the only remaining element that can go after N/2+1 (the max. distance is N/2) and based on the 1-s in the binary representation of K, put pairs of "smallest unused number <= N/2, > N/2" to the beginning or to the end of the remaining part of the sequence

• the sequence 2,3,7,..=$S$ continues with 16,36,80.. — the i-th member (0-based) is the sum of previous ones plus 2^i - 1, so we can generate it easily and it's short

• we can iterate over S and subtract its elements from K; when encountering an element  ≤ K, choose the first element or a pair of two more (how to choose the pairs: start greedily with the smallest y allowed element greater than the last added and the smallest unused element overall; as we iterate over S, the smaller element in the pair increases and if we're at the "power of 2" part, there's a collision between the elements in the pair, so we should increase the larger one)

• if we stopped at 2 in S, we can fill the permutation with one of two patterns based on K being 1 or 2 (maybe it's the same as the pattern for "power of 2"?)

Time complexity: O(N|S|log(N)) — one set<> lets us find the greatest/smallest element something.

It's nasty; I didn't bother with checking if the set of rules can't be simpler and memorynuked my computer twice while debugging. But it got me first place.

Small observation about Coolguy and Two Subsequences: following solution runs in O(N^2) and at the sime time gets AC in 0.2 seconds :) In CF custom invocation it works 7 seconds for sorted array of size 20k, so it will probably take a few minutes on 200k array.

Still waiting for rating changes ......