The round-trip doesn't have to pass through all the cities so it suffices just to find one cycle in a graph. This can be done by doing a DFS and keeping track of the current stack of vertexes.

If you cannot find a cycle then you can add a single edge to road with 2 vertexes. The possible answers can be -1, 0, 1, 2.

Can you give me a hint for 5 and 10? Thanks!

Is this the first contest on CF for which more than 7000 people registered?

Thank you for your patience! Now I understand! :)

Oh, I see. This makes more sense.

I suppose that the proof given in the Errichto solution can be solved using induction but I find it very counter-intuitive, or maybe that's just me.

I'm not really convinced why in D Div2 you should always select side a and a-1 but not a-2. The reason is that having a smaller quantity doesn't necessarily yield less towers.

Can you tell me where's my mistake?

I think the rating should not be correlated with one's ability to do research. If you are willing to put enough work into something you enjoy, you don't have to be a red rated user to succeed.

I highly recommend this reading: https://terrytao.wordpress.com/career-advice/does-one-have-to-be-a-genius-to-do-maths/ , it's a blog post who partially inspired me to do research.

I had in mind the same picture but I cannot figured out what's the connection with the number of paths in a subtree — (why isn't just the product of sizes of the 2 subtrees?).

Then I thought more about it and figured out that the expected length you're adding to the L[u] + L[v] — 2 * L[lca(u,v)] is equal to the number of paths in the sub-tree. Thank you :)

I was trying to understand the solution for problem E. I am having trouble with the editorial so I decided to look up on some code.

For no particular reason I chose this one: http://mirror.codeforces.com/contest/629/submission/16276620 . But I'm stuck again.

Let's consider the case where LCA(u,v) is not equal to either u or v. Can anyone shed some light on why the answer depends on the product between the number of paths in the subtree determined by u (or v) with the size of the other subtree determined by v (or u)?

Thank you!

Oh, so maybe I didn't understand it even after the end of the contest :) It happens.

No. It also has the first explanation wrong. It should be written '2' instead of '4'...

Thank you, now it's clear the induction step. I can make this more formally, for those interested. Denote . We want to prove that degree of P_k(n) is k + 1.

Base case of induction after k:

By the induction we know that deg(P_k - 1(n)) = k. Taking the derivative of P⁽¹⁾_k(n) = k·P_k - 1(n). This implies that deg(P⁽¹⁾_k(n)) = k

Therefore deg(P_k(n)) is exactly k + 1.

Why is the sum a polynomial of degree (k + 1)?

For problem 403D could someone please tell me why the answer isn't sum[len] * ((k, n - len)) from Theorem 2?

Thank you!

Cheer up mate! It's not the end of the world, you still got many contests on Codeforces to participate next year! :)

You can start by reading the topcoder tutorial and then solving the problems left as homework.

Assume that you have the distances from vertex with index 1 to every vertex u in a vector d[].

Define lca(x, y) the lowest common ancestor for vertex x and y. You must find out the distance from v to u.

The result is d[u] + d[v] — 2 * lca(u, v) because you add twice the distance from vertex 1 to lca(u, v) (that's where the 2 roads intersects). You can draw a tree on a paper and and work with some examples, it will be clearer.

Thank you for your time! :)

Then, how can i log-in?

I didn't receive the confirmation mail :(

Can someone post an idea for Problem E ?

Thanx ! :)