Maybe they meant "log in" :v

два часа

с 14:00 до 16:00 (МСК)

на главной написано

sort according to non-decreasing L[i] , now if u set number of left legs to L[i] , the number of valid pairs will be number of R[j] ≤ N - L[i] where 1 ≤ j ≤ i , so do coordinate compression and apply a BIT.

I sorted the sequences increasing with respect to L.

After that, I iterate in that sequence, let's say at step i we have L_i as the left number:

• Then the maximum right number is R_i = N - L_i. Observe that in this way, R_i is decreasing

• Since L_i is increasing, we satisfy every note in respect to L before, the only problem is satisfying R queries before. So we use a structure (like a C++ map for example) that can get the values of R before that are greater than our current R — and we delete the values lower than our current R since R_i is decreasing. The answer for iteration i is the sum of values in the map. We get the maximum in every iteration.

For each i, compute two values:

• The sum of values of all coins whose value is between [2ⁱ, 2(i + 1))
• The smallest value of all coins whose value is between [2ⁱ, 2(i + 1))

This will lead to an O(nlog²ⁿ) solution. However I'm not sure if this is intended (sparse table got MLE, segment tree got TLE, segment tree + pruning passes).

There are absolutely no complex DS involved, at least in my solution.

First, think about why it's enough to iterate "x -> 1 + sum of numbers up to x" for a given range until the sum is smaller than x. It's fast enough, since as we're iterating, x strictly increases and so the sum increases quite quickly.

We can find sums in a given range using a Fenwick tree. We'll process numbers in non-decreasing order, add them to the Fenwick tree and deal with iterations in all queries at the same time.

When we've just processed all numbers  ≤ x for some query's current x, we can find the sum for its next iteration, check if it's time to stop and if not, move on to the next iteration there. The current iterations for all queries can be stored in a set / priority queue / etc., from which we can take the smallest ones as long as they're less than the currently processed number. Time complexity: unknown, but it passed without any optimisations.

UPD: Downvote logic on CF again. If I'm wrong, why not comment?

i used persistent segtree to get sum from L to R with values from x to y. It passes with coordinate compression.

: let's add numbers one by one starting from the smallest, and maintain sums on the segments from queries. If we're adding number x and there are sums  ≤ x - 2, recompute them (and if they're still too small — we're done). The trick is, each sum will be recomputed logarithmic number of times: if it was s₁, then s₂ and then s₃, then s₃ - s₂ ≥ s₁.

One pitfall is that Segment Tree is too slow here :( But Fenwick tree passes.

S = 0
while (true) {
   S2 = sum of numbers less than or equal to S + 1 on segment [l, r]
   if S2 == S
      break
   S = S2
}
print S + 1

That can be done online with persistent segment tree code

Да, правда

Нет, не правда. Если в отрезке числа 1 и 3, то после добавления H=1 можно получить числа от 1 до 5.

А сумма в лонгах хранится?

После раунда архив с тестами выкладывают, надо подождать.

Обычно Михаил добавляет в тренировки, как только появляются тесты.

Контест в тренировках: 2016 Russian Code Cup (RCC 16), Elimination Round.

А как решать в принципе задачу Е?

Что? У меня 2 персистентых дерева отрезков спокойно влезли за .

Обычное ДО нормально зашло — код.

Ну так не зря в том году они Фенвика прям на футболку печатали, а я стебался еще

У меня зашло двумерное дерево отрезков за O(n log^3 n). Видимо они тесты против какого-то конкретного решения делали (ну или против жавы)

Ну не знаю, у меня персистентное дерево отрезков прошло с 1 попытки. А выше тоже жалуются, что у них дерево отрезков ТЛится...

Мое ДО тут на КФ прошло с двухкратным запасом. Сложно сказать, что там со скоростью на RCC, конечно

Что-то несправедливо тебя задаунвотили, это правильное замечание. Да, я даже не пробовал дерево отрезков, сразу делал фенвика на это. Особенно печально что оказывается задача уже была, я был шокирован увидев на 15-ой минуте сабмит по ней.

Ну и понятно что можно было персистентное писать, просто я их не люблю :)

Интересно, а вот нафига задачи, которые уже где-то были включать в контест? Видимо, жюри не знало о её существовании, да? )))

F была в этом году на каких-то сборах. Мне сокомандники решение рассказывали. :)

Are both your numbers larger than 1?

Not the first time most important problem of RCC elimination round is from some other contest. Copy-pasting doesn't take that much time.

I spent about 10 minutes. Copy-paste of Fenwick tree (+2 minutes) and fast input-output.

1. Well known greedy

2. We see 2D-queries

3. To solve the problem in offline sort queries and use Fenwick tree. Implementation is short, 25-30 lines of not copy-pasted code

P.S. Some people said the problem was on CodeChef contest. For me it was a new one.

One more resource with problem E: http://cs.stackexchange.com/questions/19651/minimum-number-that-cannot-be-formed-by-any-subset-of-an-array

And that's why I was shocked that someone got AC in 15-th minute of competition :)

Greedy algorithm. First fill all containers to minimum volume. Then, start filling the containers to maximum volume in the order of increasing p_i. When filling a container to volume v, reserve of reagent c_i and of any reagent (you need to track the total volume of unreserved reagents).

int n = nextInt();
int m = nextInt();
double min[] = new double[n];
double max[] = new double[n];
int c[] = new int[n];
final int p[] = new int[n];
Integer idx[] = new Integer[n];
for (int i = 0; i < n; i++) {
	min[i] = nextInt();
	max[i] = nextInt();
	c[i] = nextInt() - 1;
	p[i] = nextInt();
	idx[i] = i;
}
double v[] = new double[m];
double sumv = 0;
for (int i = 0; i < m; i++) {
	v[i] = 100.0 * nextInt();
	sumv += v[i];
}
sort(idx, new Comparator<Integer>() {
	public int compare(Integer o1, Integer o2) {
		return p[o1] - p[o2];
	}
});
double level[] = new double[n];
double sumcap = 0;
for (int i = 0; i < n; i++) {
	double vol = p[i] * min[i];
	if (v[c[i]] < vol) {
		out.println("NO");
		return;
	}
	v[c[i]] -= vol;
	sumv -= vol;
	level[i] = vol;
	sumcap += (100 - p[i]) * min[i];
}
if (sumv < sumcap) {
	out.println("NO");
	return;
}
for (int i: idx) {
	double space = max[i] - min[i];
	double vol = min(p[i] * space, v[c[i]]);
	double capvol = (100 - p[i]) * vol / p[i];
	if (sumv - vol < sumcap + capvol) {
		vol = sumv - sumcap;
		capvol = vol * (100 - p[i]) / 100;
		vol = vol * p[i] / 100;
		v[c[i]] -= vol;
		sumv -= vol;
		level[i] += vol;
		sumcap += capvol;
		break;
	}
	v[c[i]] -= vol;
	sumv -= vol;
	level[i] += vol;
	sumcap += capvol;
}
if (abs(sumv - sumcap) > EPS * max(abs(sumv), 1)) {
	out.println("NO");
	return;
}
out.println("YES");
for (int i = 0, j = 0, k; i < n; i++) {
	int curNum = c[i];
	double curAmount = level[i] / 100;
	double free = level[i] * (100 - p[i]) / p[i];
	int cnt = 1;
	for (k = j; k < m; k++) {
		if (v[k] > free) {
			if (free < EPS) {
				break;
			}
			if (k == curNum) {
				curAmount += free / 100;
			} else {
				++cnt;
			}
			break;
		}
		if (v[k] > EPS) {
			free -= v[k];
			if (k == curNum) {
				curAmount += v[k] / 100;
			} else {
				++cnt;
			}
		}
	}
	out.print(cnt);
	out.print(" " + (curNum + 1) + " " + String.format(Locale.US, "%.9f", curAmount));
	free = level[i] * (100 - p[i]) / p[i];
	for (k = j; k < m; k++) {
		if (v[k] > free) {
			if (free < EPS) {
				break;
			}
			if (k != curNum) {
				out.print(" " + (k + 1) + " " + String.format(Locale.US, "%.9f", free / 100));
			}
			break;
		}
		if (v[k] > EPS) {
			free -= v[k];
			if (k != curNum) {
				out.print(" " + (k + 1) + " " + String.format(Locale.US, "%.9f", v[k] / 100));
			}
		}
	}
	out.println();
	if (k < m) {
		v[k] -= free;
	}
	j = k;
}

Same me, "cout<<-1<"\n" bring me out of top 200.

Заметим, что все вершины должны иметь степень  ≤ 3, а корень —  ≤ 2.

Для каждой вершины посчитаем расстояние до самой далекой динамикой на дереве (сначала самую далекую в поддереве, потом в обратную сторону). Далее переберем корень (учитывая ограничение на его степень). Для каждого корня, очевидно, высота дерева будет той самой, которую мы посчитали в динамике, и, соответственно, ответом для него будет 2^h - 1 - n. Выбираем корень с наименьшим h, выводим ответ.Код

Что мешало посмотреть в адресную строку и поменять en на ru?

still nobody answer