I have the same problem.

It works now, thank you.

we want to register , watching others writing contest isn't very attractive :))

:D :D hahaha

sorry to say,but I don't like when someone says "wish you successful hacks",Simply say that I wish you success,sorry again if I said something bad,This is only my opinion.

You should not talk about your solutions during the contest: you give a advantage at the coders who are on the same room than you and who came here by saying that your E, if it isn't some bluff, has chance to be hacked.

уверен, что на С и Е покрашит еще как )

Даммит! Д взломали за минуту до конца =(

а как решалась то?

Нет, она не такая, там надо посчитать не просто количество, а количество с различными именами.

Я тоже не понимаю, что эта задача делает под буквой D. Я час просидел над C, так и не придумав нормального решения. Сдал какую-то чушь. На прочтение задачи D у меня ушло минут пять, зато потом считанные минуты чтобы написать тривиальное решение.

Аналогично с задачами A и B. Я трубашатал эти коды глазами парсить. Там, оказывается, цикл начинается от i, а не от 1. Для меня такие тесты на внимательность всегда были губительны. Зато задача B уходит за 3 минуты, 2 из которых ушли на чтение условия.

А я написал решение, забыв, что нужно обязательно выводить существующий цвет. Потом 30 минут сидел и не понимал, на каком таком тесте падает решение. Гроб, а не задача.

а я решил написать дфс по графу и забыл, что он может быть несвязным=)

может задумка авторов была в том, что в д все бросятся писать граф, как я, и словят или тл или еще какие гадости, а более простое решение, которое бол-во сдавали, не увидят.

ага. мой random_shuffle() и просто проход с начала пока не встретим сумму, которой нет в сете, прошел. там очень маленькое ограничение на k, поэтому легитимно

Оказывается заходит полный рэндом. Т.е. храним в set полученные суммы, и пока не набрали нужное количество, берем случайную n-битную маску, считаем сумму соответствующего подмножества, смотрим в сете, была ли такая сумма.

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

still no rating change...

1) n times 1

2) n-1 times 2 (pairs with most beautiful)

3) n-2 times 3 (two most beautiful with others)
...
k) n-k+1 times k (k-1 most beautiful with others)
...
n) all of them

Sorry, I posted my solution in Russian, but forgot to translate it... First step. Let's print every soldier. Second step. We take the "beautiest" soldier and print him with every differrent soldiers. Third step. We take two "beautiest" soldiers and print them with every differrent soldiers. And so on. Obviously, all these sums are different (because of monotony). And thier number: n+(n-1)+(n-2)+...+2+1=n*(n+1)/2. Example of output:

1
2
3
4
4 1
4 2
4 3
4 3 1
4 3 2
4 3 2 1

Code

Randomized algorithm, cool =)

Notice that k is at most n.(n+1)/2 Solution is to use the following values:

(a[0]),(a[1]),...,(a[n-1]), (contains n detachments)

(a[0],a[n-1]),(a[1],a[n-1]),...,(a[n-2],a[n-1]), (contains n-1 detachments)

(a[0],a[n-1],a[n-2]),(a[1],a[n-1],a[n-2]),...,(a[n-3],a[n-2],a[n-1]), (contains n-2 detachments)

...

All of these sums are different. Number of available detachments using this method = n + n-1 + n-2 + ... + 1 = n*(n+1)/2 so you will always be able to get k detachments.

The randomized solution is much more beatiful for me :| I didn't implement it well myself though.

2619137 — a fixed 50 percent probability was way too slow

2621963 — a randomized probability makes the solution quite fast

There exists a rather simple deterministic solution which has O ( N * K * ln ( K ) ) complexity. Traverse though the array and try to add current number to any of the possible sums and if you can make a non existing sum add it to the list of existing sums. Use a set to check if a sum exists or not in logarithmic time.

Solution : 2616373

1 Vertex color is 1.

you are confusing between vertex color and color of those vertices which are connected by edges. vertex 1 is colored by color 1 and hence it counts.

It's obvious that we always can make n-1 equal by adding or subtracting 1 from any other sacrifice-lamb element (e.g. n'th). If sum mod n == 0 then we can also do this for that last element, making all of them equal to sum div n.

We can make an unlimited number of moves.

1. n-1 is always possible: we can make a[2]..a[n] equal to 10000, decreasing a[1] at every step.

2. If sum % n == 0, we can make all a[i] equal to sum / n. And it's obvious that we cannot make it otherwise.

when sum%n==0, we can get n numbers, which will be equal to average. when sum%n>0, we can get n-1 numbers, which will be equal to average, and 1, which will be average+sum%n=)

Thanks all of you.

can the admins tell when the ratings will get updated??

Да и больше он и не участвует, как правило.

Точнее unrated аккаунт. Чувак может и много раз писал.

обновили)

Нам же нужен минимальный

I think there's room for improvement in the English Descriptions. Anyhow, they're always comprehensible.

First, solve the original version. http://codeforces.net/search?query=130&_tta=375

Actually it doesn't matter, depending on the judge used. When we must print numbers, usually the CF system checks your output token-by-token, ingoring whitespaces and new lines.

http://codeforces.net/blog/entry/5935

It's link to AC solution, which do it in such a way:

1. At first calculate it in linear time.

2. Cache the answer into some map and in future answer to the same query in O(logN) time.

P.S. If you would like to read some prove of correctness, look at http://codeforces.net/blog/entry/5935 :-)

For arbitrary queries [L, R] your may for each i precalculate next[i] (minimum j > i : a[i] = a[j]), and then answer to query will be number of i in [L, R] such that next[i] > R. In offline it can be calculated in using segment tree with sweeping line.