Because community of atcoder is just a subset of CodeForces community.

Can you give link to submission?

C001_scrambled should be sample test case, by the way.

The key observation to C is that the distance from last to first house is $$$ k-a[n-1]+a[0] $$$

Dude the contest isn't over, don't discuss

solution please?

The base of the idea is like this.

Let's suppose there are two edges connecting node (x,y) and node (x,z) and the node x is root. And let's define the number of the nodes belonging to the y-rooted subtree(subtree whose root node is y), as A, and the number of the nodes belonging to the z-rooted subtree, as B.

Now we can count the number of the ways in which writing 1 on vertex y(or z) and writing each of the numbers 2 ~ A(or B) on the nodes of the y(or z)-rooted subtree. Let's define this number as C, D each.

In short, the number of ways writing A numbers on the nodes of y-rooted tree is C, and the number of ways writing B numbers on the nodes of z-rooted tree is D.

In this case, the number of ways writing (A+B+1) numbers on y-rooted tree, z-rooted tree, and the node x is C*D*(A+B)!/A!/B!(It contains combination).

Sorry for many definition.

First: answer for given root is: $$$\frac{n!}{s_1s_2\ldots s_n}$$$, where $$$s_i$$$ is size of subtree rooted at $$$i$$$. Why? Because a permutation is valid iff value at any node is less than any other value in its subtree, probability of this holding for specific node $$$i$$$ is $$$\frac{1}{s_i}$$$ and those are all independent.

Now run dfs from one fixed root and calculate for each vertex size of its subtree. For any vertex $$$v$$$ except for the root let's consider two parts of the tree splits to when edge between $$$v$$$ and its parent. If the root is inside $$$v$$$ subtree size of upper subtree with size $$$n - s_i$$$ will be included in calculating the result, otherwise lower subtree with $$$s_i$$$ will. Thus for each such node we want to multiply all answers in its subtree by $$$\frac{1}{n - s_i}$$$. The latter is equivalent to multiplying all values by $$$\frac{1}{n - s_i}$$$, and those in $$$v$$$ subtrees by $$$n - s_i$$$. To perform sequence of operations: multiply all values in a subtree by $$$x$$$, and at the end extract value from each node we can just: whenever we multiply all values in a subtree multiply the value at its root only, and at the end use basic dfs to calculate for each vertex product of values on path from root to this vertex.

EDIT: to be precise: the formula I described includes dividing by size of root's subtree, while the solution divides by all except for the root. Thus we need to divide answer for all vertices $$$n$$$.

You have N cities around this lake and you can traverse it clockwise or anti-clockwise. You have to pass through every city and total distance travelled is sum of distances between every two cities in your path.

In second sample, one city is in position 0 degrees ("north of the lake") and the last is in position 15. If you walked anti-clockwise (array is circular, remember), you could go from the 0-th city to the 2-th in 5 degress, because $$$(0 - 15) \ mod \ 20 = 5$$$.

Solution.

The O(N^2) solution is as follows:

Root the tree at k. Now, we observe that this problem bijects to listing nodes in order such that all parents appear before their children. Let the number of ways to order nodes in the subtree of v be s[v]. We observe that through combinatorics, s[v] is the product of s[i] for all i that are children of v, multiplied by (stsize[v] — 1)!, divided by the product of s[i]!. The part with the factorials corresponds to the number of ways to order the different subtrees relative to each other. Thus, this can be solved in O(N) per root if we precompute the factorials and the multiplicative inverses.

To speed up to O(N logN), a further idea is needed. (Hint: consider how to reroot the tree.)

Edit: divide by the product of stsize[i], not s[i]. I'm a bit of an idiot...

So we have to read the statement carefully, because the case which the order is not important usually uses sorting.

At atcoder, it's kind of difficult to have new questions (at least in beginner contests)

Can you explain DP formula there? I can't get it...

Damn, makes me miss CSAcademy: this kind of short statement problem was like lots of their other good quality problems :'(

Because coloring all the colorless apples red, before coloring any of them green is not always optimal.

Ex.:

2 1 2 2 2
2 2
1 1
10 10

The answer is 22, but your code gives 21.

I didn't go through your whole code, but here is what I did.

1. First sort A, B, C array in descending order.
2. Make a new array(Let it be F) by taking the first X and first Y of B.
3. Sort the new array F in descending order.
4. Now try replacing the smallest element of F by the largest element of C.
5. Do it until Del(Ci) — Del(Fj) > 0.(Why? Because If we replace now, our sum will decrease).

Here is my simple implementation: Submission

When you use a colorless apple you must decide which color it has to become based on which color has the worst apple who was being eaten before coloring this one(because that's the one you want to discard). If you mix all the apples you don't get to choose by this criteria and fail to reach maximum value.

Hint: Tree Dp

Think, of a node N with two children X,Y

You already know the size of the subtree on each child, and the number of ways you can label it.

Since N is a parent of X,Y N should get the lowest number. And among the remaining you've to choose which are going to each child and multiply by the ways to label on each child.

That will give you the solution for a particular root, use re-rooting after

A tab labelled "editorial" should show up on the AtCoder itself.

See any of the past contest. You will get it.

That's what I did, took me 40 mins.

d: brute force e: sort, greedy

The key observation in D is that we cannot use Floyd-Warshal because it gives TLE, and then we implement BFS wich works better $$$O(n^2)$$$

E is dynamic programming.