1) No.

2) As it can't be enforced, there is no limit on number of PC.

Finals.

Sorry, prizes are only for university students.

Yes.

I don't know what you talking about. My first submit got AC with max running time 1.1 sec.

What kind of solution requires so much optimizations?

http://pastie.org/private/ugykrmgzr5nefig1z5ohca

The semifinal will contain better problems for sure :).

It didn't let me create an array of size 1<<26 but allowed an array of size 10⁷.

same here

Which problem? The one with the inversions?

Our solution passes all test cases and works 0,39sec (and what is more important, we can prove it).

First, lets look at this chain (we will call it "left chain"): a sequence, which starts with a[1] and every next term is the closest to the right that has larger value (than the previous term). For example, for permutation 2, 1, 4, 5, 3, 6; their "left chain" is [2], 1, [4], [5], 3, [6].

Second, lets look at the "right chain". It's like the "left chain", but starts at a[n] and goes left (every next term is closest to the left, that has smaller value). So, for permutation 2, 1, 4, 5, 3, 6; it is 2, [1], 4, 5, [3], [6].

Nice! Now, lets notice, that the best swap pair should have its left number in the "left chain" (otherwise, we can improve that swap pair). Similarly, the best swap pair should contain its right number in the "right chain".

Good! Now we can move on. Lets look at some number, which is not term of the left nor the right chain. This number has some range of terms in the left chain, which are "to the left and bigger" and some range of terms in the right chain, which are "to the right and smaller". So, this number makes "+1" for some rectangle on the plane (indexes of the left chain, indexes of the right chain).

So now, our problem is this: we have some rectangles, find how many rectangles has non-zero intersection. This is a classic problem, which can be easily solved with a segment tree.

The complexity of the solution is O(n log n).

We did centroid decomposition with O(Nlg(N) + Mlg(N)²)) complexity and same TL problems.

We had the same solution in O(Nsqrt(N)) but didn't manage to pass TL on 5 test cases, with all optimisations :/

Then we wrote solution with central decomposition — you can fix one central node, count all pairs of residents which should go through the fixed node (you can do that in O(Rlog(R)) where R is the total number of residents), and then delete fixed node and do recursivly the same thing for it's subtrees. So the total complexity is O(log(N) * (Rlog(R) + N)) and it works in 1.5s.

We had O((sumk + n) log (n)) solution.

For each query we sort all cities by tin, find all lca of neigbours and then create "mini-tree" of this lca's and vertices. it has <= 2k vertices maximum.

Now what you need is to solve in O(TreeSzie). it may be done by calculating for each vertex number of elements in its subtree.

We did a method similar to finding LCA via HLD.

Initially, when a query comes we put all nodes in a priority_queue. Now at each step whichever node has the deepest chain head is shifted up to correct position and corresponding number is added to the answer.

By correct position I mean the node is shifted up to the first node above it in its chain, if it exists, or to the parent of the chain head. If another node exists above it in its chain then after moving the node up I just merge them and treat the entire thing as a single node in the future.

And by corresponding number I mean if a bunch of x nodes were shifted up by distance y, then I add x.(k - x).y to my answer, where k is the number of total nodes.

In case anyone is interested, here is our code, using the same approach as Alex Dmitriev. In retrospect, we overcomplicated the actual calculation, since we first calculate , and then subtracted the paths from the LCAs to the root.

link to code It runs in about 1 second.

What is the "standard dynamic programming solution" that you used for K > O(sqrt(N)) ? Can you provide some link/explanation for that approach?

Once Finals will be over contest will be open for individual submissions.

Yes this bugged me as well. Whether or not partial scoring is available has a huge influence on your strategy. The decision afterwards to only do binary scoring for the third problem was very arbitrary as well (I hated it especially because I was two testcases away from a full score), it says "after considering very few AC only challenge bear and safe is binary.", even though at the time of writing it hadd less full-score submissions than the second problem, and more than the fourth..

It's very difficult to understand the decision of the organizers. The problems were great, but they decided to spoil the whole round by changing the scoring system two times in the middle of the round. Now the final round was more like a joke.

Our solution is suffix automaton + suffix array + binsearch on answer.

adamant has said that our solution is overkill :)

Build suffix automaton on reversed string and calculate winning states. On the next step you have to deal with lexicographical order. There is a fact that suffix link tree in suffix automaton is a suffix tree to the reversed string. Given this, you can calculate winning states and find k-th winning string using suffix link tree. Also, this solution is described in editorial.

Has someone received an email?

Sorry to be that guy, but is there any news regarding the prizes ?

As I remember we will get another email which is not from Hackerrank.

Our team hasn't received an email.

Is there someone else who hasn't received ?

I asked for support and they told me this:

"I hope you have the access to click the “Claim Prizes” button that will take you to your profile page where you have to complete your shipping address within your profile and we will get your prizes delivered within 2 weeks."

I am still waiting for the T shirt! :(

Still no T-shirts here. Has anyone received one ?

Please wait a bit longer. Given high volume participation, your prize will be delivered to you a few weeks after you completed your address on HackerRank.com. Please make sure your address is 100% complete including Country and area code

Has anyone received a T-shirt/Hoodie yet? :/

Nope

no.

I received mine about 10 days ago.

I received mine a week ago. Make sure all your address details including country are filled properly. You should receive a mail from DHL once you're done. They require a photo of your identity proof before they dispatch.

Same here!!!

same here