If two person gets same score, the person who reached the score first will be ranked higher. So, time of the last correct submissions and no penalties for wrong submissions.

Its not that we hate these countries in the list, there are some legal restrictions to send prizes in these countries.

The world itself is a joke :(.

It's not about how civilized it is.

It is wrriten Serbia ad Montenegro, and that country doesn't exist :P

Glad to know that you liked the problem-set. This time we tried to make the problem-set a little easier than the last one. But may be another hard problem would be better.

Thanks for your feedback. I didn't expect so many top people in just after world finals. I agree that the problem-set was too easy for top people but at least it problems were nice :).

I personally don't really like the idea of tie-approximation problem (esp, for 24h contest (I mean not several days))

• there are already such contests (codechef, hackerearth)
• it makes you spent much more time for the contest (instead of solving everything and go away)
• competition transforms from [solve algorithmic problems better(faster)] to [solve algorithmic problems somehow and really-compete in approximate problem] *
• I personally can't into these problems:)

*I don't say that it's bad per se, but if we want competition in solving approx.problem, let's create competition that consists of approx.problem

You need to binary search the answer for each query. To speed it up, you need to do these binary searches simultaneously.

My Code

Complexity: O(mlogm + logm(qlogq + nlog²n + m + qlogn))

Iterate over roads sorted by cost. Find&Union with adding smaller CC (connected component) to larger one, to amortize complexity. For each CC also store (in "set" from STL) set of queries where both x_i and y_i are already in this CC. Such set of queries should be sorted by the required number of types of buildings. After merging two CC's you need to check the first query from the set (the one with the least required number of types of buildings) and check if maybe there are enough types of buildings now.

My code (there is some small bug and it didn't pass 2 small tests. I resolved it by submitting it again with brute force, run if the input is small)

I remember few informations when merging subtrees:

• remember history of parents for each node and the minimum cost of edge which caused that merge — cM
• for each merge resulting in increased number of types, in the root add the new number of types and cost of edge which caused that merge — cP

I answer query online:

• find first common parent of (x,y) — check the cost of that merge = cM
• check each common parent and find first which got desired number of different types, compare the cost of that edge cP, with cM and print max

More or less — I think answering query is O((log^n)^2).

So the total complexity:

time — O((n+q)(log^n)^2 + mlogm) memory — O(n lg n).

6th: Y^3 + T * Y

7th: NlogN

8th: NLogN. I think problem 8th can even be reduced to O(n)

I did the 8th task in O(n), using DP. Given the answer for v, we can calculate the answer for each of its children, using some values. If col[v] == col[par], ans[v] = ans[par]. Else ans[v] = ans[par] — A + B. A is the number of nodes in the subtree of v which can be reached from v without encountering any node of color col[par]. B is the number of nodes above v, which can be reached from par[v] without encountering any node of color col[v]. Hope this helps. :)

There is an O(X + Y + TlogMOD) solution for the 6th problem.

Related paper

There is a formula for 6th task. My solution looks like this

int solve(int x, int y) {
    int n = 2 * x + y;
    int val = Comb(n + y, n) * (n - y + 1) % MOD * pmod(n + 1, MOD - 2) % MOD;
    return catalan[x] * val % MOD * factorial[x] % MOD * factorial[y] % MOD;
}

i did 6th in O(sqrt(N) * M * M + M * T) . Basic idea was dp(i, j) = number of ways to place J pairs of brackets in I slots . Answer is dp(2 * n + 1, m) * catalan[n] * factorial[n] * factorial[m]. This has complexity O(N * M * M). To optimize this i precalculate answer for all dp(N, m) where N = i * sqrt(n) for integer i and also dp(i, j) where 1 ≤ i ≤ sqrt(n) . With this precalculation takes O(sqrt(N) * M * M) time and each testcase takes O(M) time.

Mine was nlog^3n and offline. Your solution is really amazing.

Yeah I did the same except I found the number of distinct elements online using Pesistant Seg Trees.

editorial for all problem is live, please check.

I can try:

• We should notice that if you have X [] pairs, then you have 2*X+1 positions where you can insert () pairs:

1 [ 2 [ 3 ] 4 [ 5 [ 6 ] 7 ] 8 ] 9 -> I showed 9 positions for the sequence [ [] [ [] ] ], which has 4 [] pairs.

The number of such ways equals Cat[X], so now let's pick one and think in how many ways we can insert Y () pairs.

We have Y () pairs and 2*X+1 positions to insert them. In each position you can insert between 0..Y pairs of () and the sum over all positions must be equal Y. Moreover if you decide to insert k pairs of () on one position, you can also do that in Cat[k] ways.

So for example, you have 3 positions and 3 () pairs, you can insert them in the following ways:

Cat[0], Cat[0], Cat[3]

Cat[0], Cat[1], Cat[2]

Cat[0], Cat[2], Cat[1]

Cat[0], Cat[3], Cat[0]

Cat[1], Cat[0], Cat[2]

Cat[1], Cat[1], Cat[1]

Cat[1], Cat[2], Cat[0]

Cat[2], Cat[0], Cat[1]

Cat[2], Cat[1], Cat[0]

Cat[3], Cat[0], Cat[0]

So now you have the following question: given Y pairs of () and 2*X+1 positions, compute the number of ways in which you can insert pairs into positions. And a lot of papers and formulas in this thread were devoted to explain how to compute this efficiently.

I also didn't get the T-shirt from January Codesprint. And still no information about prizes from April Codesprint.

For last april codesprint, the tshirts are being sent now. Are you talking about any other contest? You can inbox me.

This is one problem I am aware of. I agree that its very bad when someone posts a spoiler, corner case etc. I try to monitor the contests I manage but I can't monitor 24 hours. We will try our best to figure out a solution for this before the next contest.

Interesting,

I "won" the $750 dollar prize, which means I am izban = P

I also got a message that I won the contest.

Also in the April contest I got a wrong message.

I got two messages with prizes. I actually won neither. Seems legit :^)

Yep, still waiting for the May prize. And their support ignores messages.