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.

Nothing! simple observation.

my_D (without any Bfs/Dfs) just simple HashMap you can use array too to store. for any (i,j) pair distance(k) will be k=min(abs(i-x)+abs(y-j)+1,abs(i-j)); just store it and finalyy print it.

my_E just sort and pick TopMax x+y having constrain that you can't pick more than x from red and more than y from green apples respectively.

https://atcoder.jp/contests/abc160/submissions/11292835 Runs in quadratic time for D. Can it be improved?

Hold rght there Sparky!!

Why logN , it should be logM (M=1e9+5)

You are double counting when you check whether distance_direct_path is equal to distance_bridge_path. They are the same pair, and thus should only be counted once.

You mustn't count it twice

I think there is another O(n^2) solution not using BFS in problem D. We can figure out the shortest path from vertex A to vertex B (A<B) is among two cases: [A — B](the length of this path is B-A), [A — X — Y — B](the length of this path is abs(A-X)+abs(B-Y)+1). For each pair we can just compare these two numbers and find the length of the shortest path.

Why do they divide?I don't understand it

Your solution seems much simpler than others.Could you please again explain it with more details?specially the

You can calculate the distance for every pair of nodes in the graph with N BFS (for every node). After that, you will have a matrix dist of distances, where position [i][j] represents the distance from i to j.

Then, you just count the number of times the k-th distance appears above the main diagonal of the matrix.

vector<int> counter(n);

for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            counter[dist[i][j]]++;

This solution is O(N²), which is enough for the restrictions.

Found the following links which have relevant problems, thanks:

https://codeforces.net/blog/entry/75136 https://codeforces.net/blog/entry/68142

Oh, I only got an $$$O(n^2)$$$ solution using an algorithm like bucket sort. I didn't think about using difference array and prefix sum:(

Perhaps my algorithm is easier to code, but its efficiency is very low...

My code is below:

#include <bits/stdc++.h>
using namespace std;
const int maxN=2005;int n,x,y,s[maxN][maxN],ans[maxN],t[maxN*maxN];
int main() {cin>>n>>x>>y;
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++) s[i][j]=min(j-i,abs(x-i)+1+abs(y-j));
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++) t[s[i][j]]++;
	for (int k=1;k<n;k++) cout<<t[k]<<'\n';
}

You're using an unitialized value, c, and accessing the array with it: C[c-1]

Check for overflow.You have declared sum as int try to change it to long long.

For each vertex perform a BFS and calculate the distance to each other node and update their counts.

For International Readers: English editorial starts on page 7.

for problem D: check editorial on page 10.

Let $$$size[u]$$$ be the size of the subtree rooted at node $$$u$$$.

Consider you're starting the process in node $$$u$$$. Then the number of answers for $$$u$$$ is the number of possible permutations of size $$$size[u]$$$ such that a child never comes before its parent in this permutation. Why is that? Because if we start at $$$u$$$. We write $$$1$$$ on it, then we go to its children, write first number between $$$2$$$ and $$$size[u]$$$ that hasn't been written yet and so on. So a child's number will never be smaller than its parents in this permutation.

Now to get to the $$$dp$$$ formula, read this: https://codeforces.net/blog/entry/75262?#comment-594252