Кажется, мы справились ;)

Why do you need a mirror contest? Everyone can participate in the official contest.

Жадный это выбирать mex? Ну, это не работает на таком тесте:

• 3 3 3
• 1 1 1
• 1 1 1
• 1 1 1

Ответ

• YES
• 1 2 3
• 2 3 1
• 3 1 2

The answer is the number of different prefixes times the number of different suffixes in the range minus the sum over all letters of the number of prefixes that end with the given letter times the number of suffixes that have this letter before them in some string (basically, what we do is counting everything, possibly twice, and then subtracting strings that were considered twice).

Now we need to count the number of different prefixes and suffixes in a range. If we use hashes, it's just a number of different integers in a range. We can compute it using a sweep line with a binary index tree (we also need to keep a binary index tree for each letter in the alphabet to do the subtractions).

и какой он? я пробовал только самый простой x/a>v.x/v.a

inline bool cmp(int i, int j)
{
	return (a[i] - b[i]) * x[j] < (a[j] - b[j])  * x[i];
}

Почему это не работает?

я с 3ей попытки угадал:)

Зачем угадывать, компаратор это решение задачи при n=2.

Optimal order is found by sorting according to the following comparator: (a[i] — b[i]) / x[i]. Then one can do simple DP to find value of savings by using this order.

откуда такой компаратор? в задаче В можно заранее записать табличку вида
1 2 3 1 2 3
2 3 1 2 3 1
3 2 1 3 2 1
... зависит от k. выписал для k=3. Ответ не существует, если есть полоса длиной больше k. Иначе просто выводим те элементы, где стоит 1.

Давай посчитаем длину максимального блока. Если она больше количества цветов — ответа нет. Иначе дадим каждой не лампе цвет (i+j)%k.

Тут граф очень особенный, поэтому задача вполне себе решаема

На контестах зачастую появляются NP-полные задачи в некоторых частных случаях и постановках, которые вполне себе разрешимы, так что ничего удивительного вроде :)

for each index find out how far you can go while having K distinct elements , now do dp with segtree

Check if there exists continuous vertical or horizontal segment of tiles of size more than k. If so, print 'NO', otherwise print 'YES' and ((i + j) % k) + 1 on places where tiles are. (You can check that this answer satisfies the statement).

can you please explain it.I m still trying to figure it out.

Same here.

I didn't understand the statement but managed to guess it from the samples. The explanation for samples would be so useful.

It is not possible to submit solution to system after contest, as far as I know, but instead of that you can download tests and check yourself :)

UPD: It added to gyms, here :)

Если честно, то ты прав.

Петин менеджер умеет мгновенно выдавать данные из любого числа блоков, если на каждый из них указывает хотя бы один указатель. Если же это не так, менеджер сначала переставляет указатели, чтобы условие выполнялось, а затем выдает данные — время выполнения этой операции для i-го запроса составляет si миллисекунд, можно переставить любое число указателей.

А учитывая, что в разборе семпла они специально выбрали индексы так, чтобы по этому правилу их можно было поменять.

Во втором тесте Пете невыгодно выполнять первые два запроса мгновенно (ставя изначально указатели на блоки 1, 2 и 4), потому что потом ему придется потратить 10 миллисекунд, чтобы поставить указатели на другие блоки. Поэтому оптимальная стратегия для Пети — изначально поставить указатели на блоки 1, 2 и 3, перед вторым запросом на блоки 1, 3, 4 за s2 = 1 миллисекунду, а перед последним запросом поставить указатели на блоки 1, 3 и 5 за s4 = 3 миллисекунды. Итого суммарное время ответа на запросы s2 + s4 = 4 миллисекунды.

Это косяк условия.

Чтобы тестировалось быстрее

Регистрация на раунд закрывается, как только начинается сам раунд. Вы зарегистрировались на второй квал (в профиле рядом с кнопкой "Да, я участвую" всегда пишется ближайший открытый квал). Спасибо, что указали на опечатку в правилах, конечно мы её исправим и постараемся сделать процесс регистрации на раунды более очевидным. Пункт про отказ от претензий добавлять всё же не будем :)

That's it. Just open that files in any text editor. There are few files, but each contains a lot of internal tests. *.a files are expected answers. Btw, your answers for B can be different, that in .a files, but also correct, because there can be more than one correct answer.