Всем доброго времени суток)
Рады приветствовать вас на очередном раунде Codeforces #151 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса.
Задачи для вас были подготовлены авторами: Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за прекрасную систему Codeforces и Polygon, а также Марию Белову (Delinur), которая перевела условия задач.
Распределение баллов по задачам будет стандартным.
Всем участникам соревнования мы желаем удачи, успешных взломов и высокого рейтинга!
UPD: контест завершен, надеемся вам понравилось)
Поздравляем победителей:
UPD2: разбор задач можно найти здесь
Can you please fix the registration for Div.1 participants? We can't register out of the competition.
I have the same problem.
It works now, thank you.
lets fun everybody :)))
we want to register , watching others writing contest isn't very attractive :))
Div1 people are unable to register for the contest (unrated). Please fix this issue.
We are very lucky div2 participants. Sorry for you(div1) :D.
They will fix it,I am sure. Because many people wants it.
Fix please :D can't not wait until succesful register message appear :))))
all contestmakers are offline :(
:D :D hahaha
I guess if Div 1 registration won't be fixed soon, there will be more new users than usual in this contest.
Good Luck everybody!
maybe everybody wants to be easy hacks :D
Don't worry, some of the contest authors will connect before the contest start because they have to check everything is ok, and they will fix it.
REGISTERED!!!
151 minutes before the start Codeforces Round #**151**,Good Luck everybody!
Thank god! I has just register succesfull :))
Lucky codings and hackings to everybody ;) Just Have Fun!
Lucky codings and hackings to everybody ;) Just Have Fun!
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.
"wish you successful hack" it is not bad wish. It means you help someone who coded wrong to know that his/her solution wrong! If he/she didn't locked that problem he/she will resubmit it. Otherwise if he/she already locked that problem wil not wait for that problem while judging.
If someone didn't hack your problem while you submitted wrong solution. You will think your solution is acceptable
Hacker gain 50 more point for their goodness ;)
Yup! I think so
Just imagine that you submit, accept pretest but WA in the main test
You may wish that somebody hack your solution and you will recheck your submission :)
you are right,sorry for my comment. so WISH YOU SUCCESSFUL HACKS!!!
Стандартная разбалловка — это замечательно. Правда, давно уже не было динамической, хочется верить, что она в процессе доработки.
Думаю контест будет решаемым) Всем удачи!!
gl & hf
good luck everybody, happy solving! :D
Hope server will stable today.
I liked the problems, but they seem much easier than usual div2... Hope I am wrong and my solutions will fail full system test =D
Edit: nevermind, just figured out that my E solution is a complete failure. :D Edit2: YEAH! E failed with Time Limit on 60 =D
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.
that's why I'm not even going to unlock it.. =D Anyway, I didn't say anything clear about it...
Could anyone explain it to me please:
Q(k) = {cu : cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.
Раунд действительно такой простой или всех покрашит на систестах?
уверен, что на С и Е покрашит еще как )
Даммит! Д взломали за минуту до конца =(
Nice contest.
По-моему E с ВКОШПА прошлого года...
а как решалась то?
Храним для каждой вершины дерева deque<set>, где в deque[i] хранятся айдишники всех имен на глубине i. В dfs-е предок забирает информацию у потомков, сливая все элементы меньшей деки в большую, а потом добавляя в деку спереди сет с единственным элементом — id текущей вершины.
Я думал что подобная штука не пройдет, там же около квадрата памяти?.. Или вся фишка в "около"? :)
За счет того, что мы всегда сливаем из меньшей деки в большую, операций и памяти будет в худшем случае N*log(N). Ах да, деки надо выделять динамически, тогда предок будет забирать всего лишь указатель на самую крупную деку у потомков.
Забавно, что там по пути надо сеты объединять, и там тоже в сумме мало операций.
В общем, вот код.
Да, по хорошему сеты надо тоже указателями хранить и сливать из меньшего в больший, я как-то забил на это и оно все равно прошло систесты... Может, не критично?
Понял, спасибо)
Я тут подумал — "тупое" решение с линией времени на запрос прошло претесты (потом, разумеется, провалилось на полном тестировании), отсылал просто так, от скуки, хотя контртест к этой штуке очевиден. А что, если бы кто-то из правильно решивших заблокировал свое решение? Тогда мне бы ничего не мешало заблокировать свое, терять то все равно нечего, и посмотреть \ закодить его идею, благо времени еще много оставалось. Скриншот сделать, например... Такое разрешается правилами? (in before — такое не проверить)
Так во время контеста отослать-то нельзя, если уже заблокировал. Только после контеста. А после контеста и так можно смотреть все что угодно.
Ааа... Неправильно понял диалог вверху топика. провал.
Нет, она не такая, там надо посчитать не просто количество, а количество с различными именами.
Эта ветка про задачу E
in how much time are the systests completed???
Can we give input with leadings zeros when it must be integers? I have seen a scanf("%i") on my room, but didn't know if I can hack him by giving integers like 033 who will be considered like a hexadecimal.
in how much time are the systests completed? EDIT: So, much negative votes just for asking a question!
Задача D самая легкая, по-моему)Упс, забыл посортить вектора перед выполнением unique. Гробище, невозможно сдать.
Я тоже не понимаю, что эта задача делает под буквой D. Я час просидел над C, так и не придумав нормального решения. Сдал какую-то чушь. На прочтение задачи D у меня ушло минут пять, зато потом считанные минуты чтобы написать тривиальное решение.
Аналогично с задачами A и B. Я трубашатал эти коды глазами парсить. Там, оказывается, цикл начинается от i, а не от 1. Для меня такие тесты на внимательность всегда были губительны. Зато задача B уходит за 3 минуты, 2 из которых ушли на чтение условия.
А я написал решение, забыв, что нужно обязательно выводить существующий цвет. Потом 30 минут сидел и не понимал, на каком таком тесте падает решение. Гроб, а не задача.
а я решил написать дфс по графу и забыл, что он может быть несвязным=)
может задумка авторов была в том, что в д все бросятся писать граф, как я, и словят или тл или еще какие гадости, а более простое решение, которое бол-во сдавали, не увидят.
Можно же без дфс'а : храним для каждого цвета вектор вершин, у которых такой цвет, а потом втупую перебираем вершину, берем ее цвет (если до этого не обрабатывали), и проходимся по вектору этого цвета, попутно просматривая соседей каждой из вершин и проверяя их цвета. Заходит за 218 мс.
Да, я примерно так и придумал, после того как залил) Я с Ц долго провозился и на Д мало времени осталось, поэтому в лоб решал, лишь бы успеть закодать=)
А я тупо хранил при помощи map<int,set > множество всех разноцветных соседей для каждого цвета...
"Кто как извращается" (c)
Ну почему же, я тоже так залил. не вижу ничего предосудительного, как раз таки наоборот — все достаточно лаконично.
Wow Amazing system testing speed.
In question D , the definition of Q(k) was quite mathematical , I could not figure it out correctly so got a lot of wrong answers.
Вот смотрю я чужие решения С и... Мне кажется или куча народу при решении вслепую тасовала возможное количество солдат и потом проверяла, можно ли их послать?
ага. мой random_shuffle() и просто проход с начала пока не встретим сумму, которой нет в сете, прошел. там очень маленькое ограничение на k, поэтому легитимно
У меня даже без random_shuffle() какая-то фигня заходит.
А зачем рэндом, зачем фигня? Выведем каждого солдата по отдельности. Потом выберем самого красивого и выведем с ним вместе каждого из оставшихся. Потом выберем двух самых красивых, выведем каждого из оставшихся вместе с ними. И так далее. Очевидно, что из-за монотонности это будут различные суммы. А их количество — n+(n-1)+(n-2)+...+1=n(n+1)/2.
Можно было и без этого решить ведь Оо
Вести массив с различными возможными суммами и массив массивов с различными возможными ответами. При получении нового значения пробовать добавлять его в конец всех имеющихся возможных значений и проверять, допустимо ли такое значение. И такие действия проводить пока количество имеющихся возможных ответов достигнет к.
P.S. Хм... Я в Д вместо цветов считал соседние вершины другого цвета, на чём и зафейлил. =(
Оказывается заходит полный рэндом. Т.е. храним в set полученные суммы, и пока не набрали нужное количество, берем случайную n-битную маску, считаем сумму соответствующего подмножества, смотрим в сете, была ли такая сумма.
А я делал что-то типа рюкзака: хранил в мапе текущие набранные суммы и пытался к ним добавить очередного солдата)
perhaps it was better if problems C and D were swapped, for a more standard score distribution!
this contest was very good, one time it is difficult an one time it is fun :D :)))
Рандом по С заходит, это так и предполагалось?
will be the rating soon?? i cant wait, am nervious :D :D
still no rating change...
Печаль такая, Д прочитал за 7 минут до конца и не успел заслать( А в дорешке зашло( Жалко. Но все равно хороший контест!
What is the main idea of problem C? Though I could managed to make it accepted by randomized algorithm(2616018), but I think it's not beautiful...
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:
Code
I was wondering how to make sure that the total beauty is different from other combinations. Now it's clear. Thank you very much!
banging my head on the wall after hearing the solun :(
Same here(
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
Problem D:
Please note, that you want to find such color, that the graph has at least one vertex with such color.
for the sample below
3 1
1 2 2
2 3
my output is 1, it passed system test though there is no vertex with color 1. i m still confused. o.O
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.
vertex 2 and 3 has same color, so they are not "colored" => they have 0 colored neighbours, so as vertex 1 that has color 1. So the answer is 1.
ну вы и нубы!!!
Sorry if this seems to be a stupid question, but why is B's solution, n if sum mod n = 0, otherwise n-1?
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.
n-1 is always possible: we can make a[2]..a[n] equal to 10000, decreasing a[1] at every step.
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.
it is frustrating to continuously check whether the ratings have changed or not after the end of a great contest...
can the admins tell when the ratings will get updated??
6 4 11 22 22 44 55 66 1 2 1 3 4 5 4 6 How about this data of problem B,, the right is 44 or not ?? Thank you !
The right answer is 44 or not ?? Thank you ,,
Ratings are updated now.
Ну почему каждый контест выигрывает чувак который ни разу не писал контест??????
Да и больше он и не участвует, как правило.
Точнее unrated аккаунт. Чувак может и много раз писал.
Ждем обновления рейтинга
обновили)
plz quiqly :(
Господа, я глупый. В задаче D на тесте
какой должен быть ответ? и почему. имхо и 500 и 300 подходят, но чекер хочет видеть 300. почему?
Нам же нужен минимальный
Banging my head after solving problem C now :| I was using bit-masking and unordered_set in the contest and got hacked (TLE)! It couldn't pass the test cases though,, by the way,, very nice contest. Loved the problems. Tricky yet pretty simple solutions :)
One simple request,, found it bit hard to understand the problem descriptions,, a simple note and easy explanation could help us and save much time of us. Thanks :)
Sorry for my bad English.....
I think there's room for improvement in the English Descriptions. Anyhow, they're always comprehensible.
Печалька, после сдачи первой задачи вырубили свет =(
What is the approach for problem E?
First, solve the original version. http://codeforces.me/search?query=130&_tta=375
For E they said that Print m whitespace-separated integers — the answers to Polycarpus's records. But printed integers on new lines.
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.
which data structure should we use to find the number of different strings on a segment in problem E?
http://codeforces.me/blog/entry/5935
It's link to AC solution, which do it in such a way:
At first calculate it in linear time.
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.me/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.
Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?
"In offline" means, if I have m queries, I can get all m answers in time.
Let our quries are segments [L..R], and array "next" is already calculated.
for i = 1..N
cnt[next[i]]++
for all q : R=i
increaseanswer[q]
by Sum ofcnt
on[R+1..n+1]
for all q : L=i+1
decreaseanswer[q]
by Sum ofcnt
on[R+1..n+1]
This can be done in o(N+M) time. You are always looking for sum on [r+1..n+1] so you can easyly change it in o(1) when you step to next i.Sum will decrease by cnt[i].and you will go to i+1.Looks like you will get LogN for binary search to transform V[i], K[i] into L[i],R[i].
I'm sorry. Right version: R[q]. I thougt it's obviously =(