Всем привет!
Завтра, в 29.10.2011 17:00 (Московское время) будет проведен неофициальный контест Codeforces Testing Round #2. Во время него мы проверим на практике, что последние нововведения Codeforces не влияют на ход соревнований, а если это не так, то быстренько все исправим :) Так что этот раунд будет проходить as is, никаких гарантий на ход его проведения я не даю.
Задачи на раунде кому-то могут оказаться известными, но я постараюсь сделать так, чтобы это было верно не для всех. Будет около четырех задач, как совсем простые, так и что-нибудь похитрее.
Говорю заранее спасибо всем тем, кто придет и протестирует систему. Спасибо!
UPD: Контест перенесен на 29.10.2011 17:00 (сначала был анонсирован на другое время, будьте внимательны).
UPD 2: В контесте, наверняка, будут известные задачи для участников из Саратова. Просьба не участвовать тем, кто живет или вырос в Саратове - не портите fun другим участникам.
UPD 3: Раунд будет нерейтинговым.
UPD 4: Всем спасибо за помощь. Я думаю, получилось довольно весело для вас и полезно для нас!
Чтобы администрация была ещё больше мотивирована на успех сего действия - может сделаем его рейтинговым? Типа кот в мешке :-)
Will it be rated?
Edit: To those who minused this, when I originally asked this question, the "It will be unrated round" part wasn't present in the text above (this was added later), which is why I asked it.
Ладно, Belonogov, рассказывай, как решать А.
А +32 / -3 хака одного чеолвека это
нормальнотоже тестирование?Но.. разве это нормально?
Пусть развлекаются
А вот лимит на взломы одного участника по одной задаче очень напрашивается.
Даже немного жаль, что убрали и перестали ломать. Было бы красиво: первое место с двумя задачами и +INF взломов, а второе - все задачи без взломов :)
Ну и ладно, что)
Ага.
Кстати, это не "вне конкурса", а "разрегистрация", несмотря на то, что в комнате и в списке участников я себя вижу (со звездочкой). Сабмитить задачи не могу. Так и должно быть?
I have tried enough but I cannot understand problem C.
Now taht the contest is over could someone explain me what the problem wanted to say.
Find the largest complete graph with at most N edges.
At this view, a Day is actually a node, a man is an edge, the problem then becomes so obvious
I didn't notice this until I saw hex539's post. I passed pro.C by a construction method
something like:
something like:
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 1 6 7 8 9 1 6 7 8 9
2 => 2 6 => 2 6 10 11 12
3 3 7 3 7 10
4 4 8 4 8 11
5 5 9 5 9 12 ...
I think it can be solved this way. For n=3 you have this solution:
Странно, что у большинства WA34 по D.
Sorry wrong observation!.
http://www.codeforces.com/contest/125/standings/2/page/9
Thanks in advance.
The first element in any case goes to the first sequence.
Then for any two adjacent elements we have 4 variants of their placement - both in the first sequence, both are in the second one, or first of them is in the first sequence or the first is in the second sequence.
Every time we check each variant of partition, if at some stage we were not able to do so - no decision at all, otherwise continue. In the end we print the answer
Did you guys ACed it to explain solution here?
could you please explain the rest - it is not easy for me. if you know 2 numbers, say, A and B, from particular sequence, and there are lots numbers (2B-A) further in the sequence, how you deal with that situation. which one you take, which one - release for the second sequence?
Now, read the a[i] from left to right, put them in either one list or the other.
The problematic i are those for which a[i] could be in both lists.
If i=n, it doesn't matter which one. Otherwise, look at the difference a[i+1]-a[i]:
- If it's the difference of the first list, put a[i] in the first list.
- If it's the difference of the second list, put a[i] in the second list.
- Otherwise, a[i] is the end of the first list, a[i+1] is in the second.
See my submission here; the first and second list are called b and c.
a naive approach based on this observation is probably wrong
try
как смотреть тест полностью?
e.g.
k = 2
1 2 100
1 3 100
1 4 110
2 3 1
the right solution is (1,2),(2,3),(3,4)
The question in problem E is to find a minimum spanning tree, such that the degree of node 1 is equal to k.
It is easy to find if we don't have this additional constraint with k.
The trick is to modify the graph a bit so that the MST in the new graph is the one we are looking for.
Separate all the spanning trees into groups, depending on the degree of node 1.
Consider the MST within each group.
What happens if you increase by the same value x all the weights of edges incident to 1?
In group i, the MST is the same set of edges, but the optimal weight is now increased by i*x.
So the optimal weight of group i+1 increases more than that of group i:
(i+1)*x>i*x
So the MST of group k is the MST of the new graph with the right increment x. This increment can be found with binary search.
See the code by MBabin.
UPDATE: systems test are a bit too weak; some solutions break on this example:
4 3 3
2 1 62
3 2 3
4 2 27
Can anyone explain why this solution is correct?
UPD:Sorry, I already understand.
Can you please explain me?
Посмотрел, на каком тесте у меня падало решение и заметил маленький баг системы:
Вывод
-1
Ответ
1
1
Протокол тестирования
wrong answer Jury answer 1 is better than participant 2147483647
Про задачу Е.
Если все веса ребер были бы разные, ее можно бы было решать как сказано сверху(бин- поиск по тому, что прибавляем к ребрам, выходящим из 1-ой вершины) . Но так как у нас могут быть одинаковые веса ребер, это надо немного изменить, иначе мы ножем считать, что решения нет, когда оно есть. Хотя тесты правда слабые - и без этого задача проходит. Некоторые принятые решения валятся на таком тесте:
4 5 2
1 2 1
1 3 1
1 4 1
2 3 1
3 4 1
(Дают ответ -1, а решение есть - например (1,2), (1,3), (3,4))
(Потому что, когда строим MST и есть равные ребра, мы не контролируем порядок их поступления)
15
1 2 3 4 5 7 9 11 13 15 5 6 7 8 9
Выдают no sulutions, хотя решение есть:
1 2 3 4 5 6 7 8 9
5 7 9 11 13 15
Жадный алгоритм ставит первую 5ку в первую последовательность, а вторую потом девать уже некуда