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.

Ответ — это количество путей по сетке идущих вверх или вправо до какой-то точки вида Ax + By = C. Динамика dp[C] = dp[C - A] + dp[C - B], свертываем в матрицы.

Предполагаю, что можно также предположить, что мы считаем количество разбиений отрезка длины C на отрезки длины A и B и запустить рекурсию с запоминанием по параметру C, перебирая, каким отрезком занята центральная клеточка и как расположен этот отрезок. Вроде должно обработаться порядка состояний. Правда, у меня пока WA 25.

я писал ДП

dp[i][j] — ответ если i-ое число равно j. Идём с конца и для каждой ячейки поддерживаем то сколько нам надо ещё оплатить. Ответ очевидно в dp[1][1]. размер dp 20 на max(a[i]) т.к. иметь купюру большую чем стоимость любого товара нам не нужно, а 20, т.к. одинаковые купюры нам не нужны, т.к. любую и так можно брать сколько угодно раз, a минимальное число для X, которое кратно Х это 2*Х, то есть купюр максимум будет log2(max(a[i])). дальше есть свойство что n/1 + n/2 + n/3 + n/4 + ... = nlog(n). из этого выходит асимптоматика log2(max(a[i])) * max(a[i]) * log2(max(a[i])) = log(max(a[i]))^2 * max(a[i]).

CODE

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);
        }
    }
}

Эта система плоха только тем, что требует участия во всех раундах — если меньше, то это риск участника. Т.е. затраты времени. Хороша тем, что используется усреднение по трём раундам, целых 15 задач, решённых в три разных захода. Поэтому любые случайные факторы — плохой день / плохая задача / застрял на одной и не решил и прочее — нивелируются. Меньше случайностей => достоверней результат соревнования.

Видимо, чтобы понизить элемент случайности, который всегда есть у одного отдельно взятого раунда. Если хочется проходить в финал — стоит всё-таки уделить время на все три раунда. А для футболки, вроде бы, 2 раунда по 3 задачи должно будет хватать.

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

Подвешиваем за 1, выписываем эйлеров обход (в обходе приоритеты), строим простое двумерное ДО на эйлеровом обходе (там где сорченный список в ноде).

Считаем кол-во инверсий для ноды 1 (просто используем ДО), затем учимся пересчитывать при сдвиге корня на одно рёбро в какую-то сторону (Тоже с помощью ДО).

Запускаем DFS и считаем ответ для каждой ноды, делая такие сдвиги.

http://pastebin.com/nWPTCRyb

Для одного корня за NlogN решать просто — запустим дфс, будем хранить в ДО/Фенвике сколько есть вершин с определенным значением на пути от корня к текущей вершине, в каждой вершине посчитаем, сколько инверсий она прибавляет, сделав один запрос к этому Фенвику.

Осталось научиться пересчитывать, что происходит, когда мы двигаем корень из одной вершины в другую. При переходе по ребру изменения затрагивают только два его конца — для вершины, которая была корнем, раньше инверсии считались со всем деревом, а теперь только с каким-то его поддеревом, так что надо посчитать, сколько есть вершин со значением больше текущего в каком-то поддереве графа; для вершины, которая стала корнем, все ровно наоборот. Эти запросы "сколько каких-то вершин в каком-то поддереве" можно перегнать в оффлайн и тоже порешать обычным Фенвиком/ДО по Эйлеровому обходу.

Upd. Код.

Есть ещё такой вариант (но не писал): осуществить heavy-light декомпозицию и на каждом пути завести аддитивное дерево отрезков с обновлением на интервале, в котором мы будем считать количество инверсий для каждой вершины. Далее, добавляем числа на вершины в порядке убывания. Добавляя очередное число, мы видим, что в каждой ветке в каждой вершине добавилось столько инверсий, сколько уже было ранее добавлено чисел в других ветках. Обновляем информацию с помощью деревьев отрезков на путях.

Я хранил для поддеревьев списки значений вершин в декартовом дереве по явному ключу и мерджил их от меньшего к большему, узнавая для каждой вершины v и каждого ребра из нее вниз в вершину to, сколько вершин в поддереве to больших, чем наша. Также в отдельном массиве складываем эти величины по всем to, а также считаем сумму этих величин по всем поддереве v. Потом считаем количество инверсий вершины v со всеми кроме поддерева v (запрос к итоговому декартову дереву + вычесть сумму в поддереве v), и уже по этой информации можно найти ответ еще одним dfs-ом по дереву (спускаем в вершину сумму количеств инверсий для вершин не в поддереве v, эта величина через полученную информацию легко пересчитывается). Код

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.