Unfortunately there is no way to participate during the contest for those who didn't qualified.

Though after each round is held, it becomes available for participation on http://contest.yandex.ru. We will also, most probably, publish archives containing test data and all materials of all rounds in the nearest future.

Yep, I'm choosing a nice bar with live football to conduct the contest from there right now :)

Sorry for that, I couldn't do anything with the time of round.

I can send you messages about goals via testing system :D

Её не было и не будет. Регистрация была на участие в квалификационных раундах, которые уже прошли.

I used bruteforce. Code.

Notice that for integer a number of used banknotes is

(all divisions are done in integers).

It can be rewritten as

So we need to maximize the subtrahend

This can be done with DP.

Code.

Well... it is kind of the backwards sieve of Eratosthenes, isn't it?

  for (int i = MAX; i >= 1; --i) {
    for (int j = 0; j < N; ++j) dp[i] += A[j] / i; // i is the highest denomination
    for (int k = 2 * i; k <= MAX; k += i) {        // k is the next denomination
      int tmp = dp[k];
      REP(j, N) tmp += (A[j] % k) / i;
      if (tmp < dp[i]) dp[i] = tmp;
    }
  }
  printf("%d\n", dp[1]);

An N log N DP solution:

We'll pick coins from smaller to bigger. Suppose we already picked some coins and the biggest of them is A. We used coins <A to make all prices divisible by A. dp[A] is the minimum number of coins used to do so. dp[A*k]=min(dp[A*k],dp[A]+sum(price[i]/A%k)).

6 years ago I wrote the same problem: https://community.topcoder.com/stat?c=problem_statement&pm=10569

Yes, d1 med was easier at that time.

Write L and R in binary form.

Now the problem can be solved independently for each bit: you need to calculate for each bit how much there will be nums in [l, r] with this bit set and unset. And then select the bit value, based on this info.

How to count how much nums in [l, r] with such bit set? Traditional trick: it is count in [0, r] — count in [0, L — 1].

So how much nums in [0, r] with i'th bit set? let r = A C B (where A value of highest bits, c value of i's bit, B value of lower bits) It is A * 2^i + c * (B + 1).

(At first consider all numbers which are less than A * 2^(i + 1), and then the all other)

In first group exactly half will be good, and in second none will be good if i'th bit unset (c == 0), and all numbers in [A C {zeros}; A C B] otherwise.

Find count of '1' for every position for all numbers from 0 to n;

It's linear in number of digits.

Then you can do F(r) — F(l-1) to find what you need.

We can calculate the number of integers in [0, R] with i-th bit set using the following fact: if we consider consecutive blocks of size 2^i + 1, the first half of integers has i-th bit set to zero, and the second half with i-th bit set to one. Therefore, one can come up with simple formula.

That awkward moment when the bug in your code is that you forget to return your answer...

int query(int l, int r, int x) {
    int res = 0;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
        if (l & 1) {
            res += t[l].end() - upper_bound(t[l].begin(), t[l].end(), x);
            ++l;
        }
        if (r & 1) {
            --r;
            res += t[r].end() - upper_bound(t[r].begin(), t[r].end(), x);
        }
    }
}

ans(C) = ans(C - A) + ans(C - B), ans(0) = 1 and use fast matrix exponentation.

Sum of required f(x,y) is sum of f(x-1,y)+f(x,y-1)

if Ax+By=C, then A(x-1)+By=C-A, Ax+B(y-1)=C-B

so you need to calculate answers for C-A and C-B and sum them

the rest is converting linear recursion to matrix powers

First, you need to compute, for each vertex, how many vertices with a higher number are there in its subtree (nIn_i), in each of its childen's subtrees (nChild_ij), and outside of its subtree (nOut_i).

To compute the numbers, first sort the vertices in the order of preorder traversal. Each subtree will be represented by a contiguous interval in this order. Create a Fenwick tree. Process vertices in the order of assigned numbers, and use position in preorder traversal as an index in the Fenwick tree. Then, you will be able to compute how many already processed vertices are in any given subtree in .

Then, you can move the root along edges and maintain current number of inversions in O(1) time for each move. Let's call "current root" the vertex you are currently computing the answer for, and "initial root" is the vertex that you used as a root in the previous steps. The answer can be computed as the sum of contributions of each vertex, where contribution of vertex i is defined as:

• If vertex i is the current root, its contribution is nIn_i + nOut_i.
• Otherwise, if i is on the path between the current root and the initial root, its contribution is nOut_i + nIn_i - nChild_ij, where j is the child that is in the direction of the current root.
• Otherwise, its contribution is nIn_i.

As you may see, when moving the current root along an edge, only contributions of two vertices may change (ends of that edge). So, the answer can be updated in O(1). Since it is possible to visit all vertices using O(n) such moves, this part takes O(n) time, and the entire solution takes time.

int getSum(int fenwick[], int i) {
	int res = fenwick[i];
	while ((i = (i & (i + 1)) - 1) >= 0) {
		res += fenwick[i];
	}
	return res;
}

void updateSum(int fenwick[], int i, int v) {
	fenwick[i] += v;
	while ((i |= i + 1) < fenwick.length) {
		fenwick[i] += v;
	}
}

IntList children[];
int pos[], end[];
int cntInSubtrees[];
int cntInChilds[][];
int cntOutSubtrees[];
long ans;
int ansPos;
int cans[];
long cansSum;

void solve() {
	int n = nextInt();
	int a[] = new int[n];
	children = new IntList[n];
	for (int i = 0; i < n; i++) {
		a[i] = nextInt() - 1;
		children[i] = new IntList();
	}
	for (int i = 0; i < n - 1; i++) {
		int u = nextInt() - 1;
		int v = nextInt() - 1;
		children[u].add(v);
		children[v].add(u);
	}
	pos = new int[n];
	end = new int[n];
	dfs1(0, -1, 0);
	int sortedByA[] = new int[n];
	for (int i = 0; i < n; i++) {
		sortedByA[i] = i;
	}
	sortBy(sortedByA, a);
	int fenw[] = new int[n];
	cntInSubtrees = new int[n];
	cntInChilds = new int[n][];
	cntOutSubtrees = new int[n];
	for (int i = n, j; i > 0; i = j) {
		for (j = i - 1; j > 0 && a[sortedByA[j - 1]] == a[sortedByA[j]]; j--) { }
		for (int ii = j; ii < i; ii++) {
			int cur = sortedByA[ii];
			cntInSubtrees[cur] = getSum(fenw, end[cur] - 1);
			if (pos[cur] > 0) {
				cntInSubtrees[cur] -= getSum(fenw, pos[cur] - 1);
			}
			int cn = children[cur].size();
			cntInChilds[cur] = new int[cn];
			for (int jj = 0; jj < cn; jj++) {
				int ccur = children[cur].get(jj);
				cntInChilds[cur][jj] = getSum(fenw, end[ccur] - 1);
				if (pos[ccur] > 0) {
					cntInChilds[cur][jj] -= getSum(fenw, pos[ccur] - 1);
				}
				cntInChilds[cur][jj] = cntInSubtrees[cur] - cntInChilds[cur][jj];
			}
			cntOutSubtrees[cur] = n - i - cntInSubtrees[cur];
		}
		for (int ii = j; ii < i; ii++) {
			int cur = sortedByA[ii];
			updateSum(fenw, pos[cur], 1);
		}
	}
	cans = new int[n];
	cansSum = 0;
	for (int i = 0; i < n; i++) {
		cans[i] = cntInSubtrees[i];
		cansSum += cans[i];
	}
	ans = Long.MAX_VALUE;
	ansPos = -1;
	dfs2(0);
	out.print((ansPos + 1) + " " + ans);
}

int dfs1(int cur, int prev, int cpos) {
	pos[cur] = cpos++;
	for (int i = 0; i < children[cur].size(); i++) {
		int next = children[cur].get(i);
		if (next == prev) {
			children[cur].remove(i--);
			continue;
		}
		cpos = dfs1(next, cur, cpos);
	}
	end[cur] = cpos;
	return cpos;
}

void dfs2(int cur) {
	{
		int ncans = cntOutSubtrees[cur] + cntInSubtrees[cur];
		cansSum += ncans - cans[cur];
		cans[cur] = ncans;
	}
	if (ans > cansSum || (ans == cansSum && ansPos > cur)) {
		ans = cansSum;
		ansPos = cur;
	}
	int cn = children[cur].size();
	for (int i = 0; i < cn; i++) {
		int ncans = cntOutSubtrees[cur] + cntInChilds[cur][i];
		cansSum += ncans - cans[cur];
		cans[cur] = ncans;
		int next = children[cur].get(i);
		dfs2(next);
	}
	{
		int ncans = cntInSubtrees[cur];
		cansSum += ncans - cans[cur];
		cans[cur] = ncans;
	}
}

I've just posted a PDF-version of an editorial: https://yadi.sk/i/1hC1divYsQtTQ

It is said in the editorial that A = B in that test.

Ooops, WA #18 checks int overflow (C >= 2^31). I feel stupid right now. =)

If you get to the top 512 competitors — yes, sure. You can track your position here.