Добрый день!
Авторами сегодняшнего контеста являются Евгений Лазарев (Нижегородский ГТУ) и я (Алексей Шмелев, Нижегородский ГУ)
Сегодня вам предстоит помочь мальчику Васе cориентироваться в виртуальном мире компьютерных игр.
Обращаем внимание, что раунд пройдет в нестандартном формате - 6 задач стоимостью 500, 1000, 1000, 1500, 1500 и 2000 баллов.
В связи с измененным количеством задач продолжительность раунда увеличена до 2 часов 30 минут.
Выражаем благодарность Марии Беловой за перевод условий, Артему Рахову и Александру Куприну за помощь в подготовке задач, написание альтернативных решений и создание хитрых тестов.
Желаем удачи и успешной сдачи решений!
UPD: Приносим извинения за неточности в задаче E и последующие неверные ответы на вопросы некоторых участников.
Good day!
The authors of today's contest are Yevgeny Lazarev (Nizhny Novgorod State Technical University) and I (Alex Shmelev, Nizhny Novgorod State University)
Today you will help the boy Basil corientirovatsya in the virtual world of computer games.
Please note that the round will take place in non-standard format - 6 objectives of 500, 1000, 1000, 1500, 1500 and 2000 points.
Due to changes in the number of task duration of a round increased to 2 hours and 30 minutes.
We are grateful to Maria Belova for translation conditions, Artem Rakhiv and Alexander Kuprin for assistance in the preparation of tasks, writing and creating alternative solutions to tricky tests.
Good luck and successful delivery of solutions!
Мы на этих задачах проводим локальное соревнование в Нижнем Новгороде, поэтому желательно, чтобы время проведения совпадало.
Yes, he did.
Согласен, наш промах.
Забыли, что о контесте на Codeforces предупредили только одного "удаленного" участника, а не всех.
"The Elder Trolls .." :)
Помнится и в предыдущих контестах авторы весело коверкали названия известных программ, но ИМХО в этот раз они явно превзошли себя как минимум в этой части подготовки задач. Респект!
Монстр погибает только тогда, когда количество частей, на которые его разрубил Вася, достигает некоторого критического числа.
По-моему, претензия на пустом месте, как и придирки к задачам A (тоже читается однозначно) и B (странно было бы располагать задачи так, чтобы их было проще решать персонально вам).
И кстати, в моей комнате я не видела решений с такой ошибкой, хотя специально искала.
Но вариант голосования здесь вполне уместен, поскольку действительно повлияло это на очень немногих участников.
An alternative proposal:
First, ask coders whether they want to be rated this time.
After the voting is over, run the system test.
If a contains all primes, you can choose mode i that satisfies a[i] == 2 first, so the answer is at most 2.
But the problem is that this understanding don't match examples.
(I sent a clarification and decided to solve D first while waiting for the answer of the clarification, so I wasn't affected during the match.)
You have to find all the divisors for the numbers 2..x-1. You can safely ignore all the composite numbers, as their divisors will be already present for smaller numbers.
Да, странное по-моему нововведение, если учитывать, что недавно пересчет рейтинга сделали общий. ИМХО логично, когда ровно одно из этого выполненоНепонятно, кто от этого выиграл и что, кроме тех, кто не пользуется взломами.
И вот не надо, пожалуйста, делать вид, что мы такие все из себя благородные, очень заботимся о тренировке второго дива, а не о своём собственном рейтинге.
Ну давайте, крэшмастеры, минусуйте.
> Взламывать можно преспокойно кого угодно...
Неверно. Теперь взламывать Div2, будучи в Div1, нельзя.
>...если сначала читать код, а потом придумывать тест.
При чём тут это? И почему так, как ты сказал, взламывать должно быть лучше, чем наоборот?
> "Кто проиграл кроме тех, кто на взломах раньше набирал over 9000?".
В том числе, как я уже написал, те из Div2, кто допустил баг, гораздо более очевидный Div1 участникам, чем Div2 участникам. Читай внимательнее.
> И вот не надо, пожалуйста, делать вид, что мы такие все из себя благородные, очень заботимся о тренировке второго дива, а не о своём собственном рейтинге.
Твоя спортивная “этика” такого не приемлет?
Gassa has "Accepted". It seems the test case is OK, but test #62 is difficult.For problem D, for the testcase:
100 0 1
Why is the answer 98 instead of 49?
Ah well, thanks for your clarifications!
i have a question , do you write any editorial for this contest or not ?
if yes it is russian or english ?
Интересный вопрос. Задача B. Такой тест:
4
k 1
b 2
c 3
d 4
4
1 2 3 4
k
Ответ должен быть 2 4? Мне известно, что прошло решение с ответом 4 4
Слабые тесты - факт.
4 4 даёт моё решение, в котором в макс. стратегии после назначения максимальных баллов тем кто заведомо выше, я отдаю оставшиеся баллы по убыванию с конца турнирной таблцы - очевидно, это неверно.
Думаю, что даже плохо выступившие, но которых пробема не затронула, это бы делать не стали. При наличии самоуважения.
Особенно в варианте, когда в таблице было бы отмечено
"отказался""вне конкурса", и нет ни одной посылки по задаче Е.we have the formula (1+x1)*(1+x2)*(1+x3)
where xn is the cut in the xn koordinate
I iterate over all x1
and do simple calculus for for the maximum value of (1+x2)(1+x3)
f(x2)= (1+x2)(1+k-x1-x2)
f:(x2) = 1+k-x1-x2-1-x2=k-x1-2x2
maximum : (x1-k)/-2
Code in :http://www.ideone.com/yZIqi
x2=(x1-k)/-2=(k-x1)/2
x3 =k-x1-x2
They cannot become to big
x1+x2+x3=k, this property holds for all values of x1, I think.
Да, у меня тоже неприятные ощущения, получить >-100... Но это справедливо, намного справедливей, чем если бы множество участников пострадали из-за того, что матч сделали не рейтинговым, хоть они и не ощутили никаких проблем.
З.Ы. И в обеих случаях кому-то было бы неприятно, и кто-то был бы недоволен. Лучшее решение подобной проблемы - составлять проблемсеты и подготавливать систему так, чтобы не было подобных конфузов.
Проблема в том, что на СФ соревнуются не меньше 10 участников тех соревнований (только из тех, кого я знаю... а я ведь уже студент, не был на УОИ в этом году), не меньше 30 участников, которые уже видели эти задачи, так как имеют прямое отношение к подготовке к УОИ или к участникам...
Я сам, при желании, могу через 10 минут получить все условия:)
Разве что сделать голосование "Вы знакомы с задачами соревнования или же хотите писать его, как рейтинговое"?
sorry, deleted
The first line contains number n (1 ≤ n ≤ 105) — number of racers. Each of the next n lines contains si and ai — nick of the racer (nonempty string, which consist of no more than 20 lowercase Latin letters) and the racer's points (0 ≤ ai ≤ 106). Racers are given in the arbitrary order.
The next line contains the number m (0 ≤ m ≤ n). Then m nonnegative integer numbers bi follow. i-th number is equal to amount of points for the i-th awarded place (0 ≤ bi ≤ 106).
The last line contains Vasya's racer nick.
It means there should be at least n+2 lines with Vasya's racer name after m numbers, nothing more. And the tests were correct! If you are changing correct test cases, then maybe you could also change tests for A, with k <= 10^6, so that my solution passes :/
So considering russian statement these tests were incorect as they omitted blank line after m=0.
This is a cite from English statement.
I agree that there were several ill-written phrases in today statements, but this time all is correct. In English when you say: the first line contains a and the last line contains b, it generally means that this data is the only data it contains. Following your point of view we can add tons of garbage in every test for every problem because there is no phrase that we shouldn't. Can you imagine test for a+b problem: "sdfa 123414 sd fa 23". Doesn't it look unnatural?
По человечески-же вроде просили не обсуждать, нет?-26, -28, -31...
Назовем степенью провинции - минимум из k - и ее размера (именно столько тоннелей мы можем из нее построить).
Если сумма степеней - больше чем 2n - 2, где n - количество провинций - то выводим ответ 0, иначе увеличим ответ на 1, соединим две самы маленькие провинции дорогами, и повторим сначала. С помощью структуры данных set выбирать две самые маленькие провинции и заменять их на объединение можно быстро.
2n - 2 - это количество ребер дерева из всех провинций, умножить на 2. (У каждого ребра есть два конца, т.ч. добавление одного ребра уменьшает суммарную степень на 2)
2) И тут по индукции. Доказательство аналогично доказательству оптимальности кодов Хаффмана (см, например Кормен). Будет время - распишу подробнее.
Зааксепченый код можно увидеть у меня в дорешивании.
На контесте получил МЛ, т.к. не знал некоторых особенностей Явы=(
Tunnels are undirected so (1,2) and (2,3) both are counted as tunnels from city 2.
5 13
2 3 5 7 11
I think the answer is -1, because 12 and 13 cannot be distinguished. But the answer is 5.
4 0 2
is
1
in problem D?
1,2,3,4 are separate provinces.
if we add tunnels 1-2,2-3,3-4....then 1 and 4 will be added 1 tunnel,2 and 3 will be added 2 tunnels.no province will be added more than 2 tunnels.
Why answer is not 0?