Всем привет.
Этим раундом мы торжественно открываем соревнование Яндекс.Алгоритм 2011. Задачи этого раунда были подготовлены мной, конечно, не без помощи команды Codeforces и Яндекс.
Я надеюсь, что задачи вам понравятся, а их решение положит старт удачному выступлению на турнире.
Как вы уже успели заметить — система функционирует в несколько урезанном варианте. Мы решили перестраховаться и выключили на время контеста некоторую функциональность. После окончания раунда все вернется на место.
Напоминаю, что лучшие 500 участников получат путевку в первый отборочный раунд. Однако, если у вас не получится пройти отбор в этот раз, не надо отчаиваться – вы сможете поучаствовать во второй квалификации, которая состоится 6-го мая в 19:00.
Желаю легкости на подъем,
MikeMirzayanov
UPD: Контест закончен! Всем спасибо за внимание, надеюсь вам понравилось. Хочется поздравить победителя watashi и самого удачливого участника cover_dh, который занял 500-е место! Напоминаю, что лучшие 500 участников выходят в первый отборочный раунд.
1) Round will be rated (affects rating).
2) Rules are Codeforces standard rules. Please read them carefully!
3) Also be sure you are registered for the contest! Find yourself here.
4) If you passed this qualification - you can participate 2nd qual. and it also affects your rating.
===
FAQ Раунда:
1) Раунд рейтинговый.
2) Правила: стандартные правила Codeforces, прочитайте их внимательно!
3) Проверьте свою регистрацию на соревнование! Найдите себя здесь.
4) Если Вы квалифицировались в этом раунде - Вы можете участвовать и во втором квалификационном раунде, и он тоже будет для Вас рейтинговым.
P.S.: Мы тут в английской ветке флудим.
UPD: http://cforces.reformal.ru/proj/?ia=123895
This was written in the email which was sent to me about this round, but I see that the registration is closed.
I've got the following error.
-----
-----
So, the server tried to open "tt.py" when the file was named just "tt".
I believe it's not the intended behaviour. Will it be corrected?
UPD: The test is incorrect anyway, so it won't affect the results.
I bet on the left one and got WA . I was dumb enough to not able to think one space will be removed. Though i still don't know what is the correct one from your three choice.
"3464574575367357<space>4674575368345646835<space>56,...,...,56,456,...,"
So the statement was matter.
You didn't press "Enter" key. The input should end with end of line character. At first I had same problem.
Итого: O(M * N * M)
Ваше доказательство напомнило эту байку :)
был один случай, когда хороший знакомый рассказывал решение задачи, и когда я попросил обоснование, он просто ответил: "моё решение правильно, и акцептед это подтверждает" =)
С таким решением меня взломали тестом
6 3
3 2 1
Программа пытается поставить 1 2 1 2 3, на последнем шаге единицу поставить не может и выводит -1. На каждом шаге я действительно выбираю альбом с максимальным числом оставшихся. Что тут не так?
Благодаря таким решениям у меня +500 =)
Надо кроме этого ещё по возможности как можно раньше поставить все элементы из того альбома, из которого взяли первую фотографию, иначе будет, как у LoonaTeg
Без сортировки вроде бы вот такой вот тест ваша программа не пройдет:
6 3
2 3 1
4 3
1 2 1
m = 2альбом с n/2 фотографиями.Вспомнился текст из песни
"Эй, жители неба,
Кто на дне ещё не был?
Не пройдя преисподней,
Вам не выстроить рай.
Эй, жители дна,
Гром смеётся над вами.
Чтобы быть с ним на равных,
Есть один путь - наверх!"
( a1 + a2 + ... + aa ) / a + ( b1 + b2 + ... + bb ) / b
to common divisor
( b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) ) / a*b <= cnst
b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) --> max
then guess that if b > a, then ai sould be >= bi
else if a < b
if a == b we must output 1 1 ... 1 1 2 2 ... 2 2
else if a < b ",can you explain me?
we have a, b and numbers x and y (let x > y)
ax + by - ay - bx = (a-b)(x-y)
x - y > 0, so if a > b and a - b > 0, ax + by - ay - bx > 0
and finally ax + by > ay + bx
S1 / A + S2 / B ->max
S1 + S2 = total sum of all a[i]
if A = B then output 1 1 1 ... 2 2 2
if A > B we need to maximize S2, else S1
if A > B
we need to sort array of marks, S1 = a[1] + a[2] + ...+ a[A], S2 = a[A + 1] + ... a[A + 2] + ... +a[n]
we can count how many marks 1 we must to include in S1, how many marks 2 we must to include in S1..
МЕНЯ ВЗЛОМАЛИ НА НЕКОРРЕКТНОМ ТЕСТЕ :(
ЧТО ДЕЛАТЬ ???.....
Чем мериться количеством, можно было прочитать ещё раз внимательно.
2) Откуда информация, что тест некорректный?
Какая задача, какой тест?
Видимо если решение не проходит по времени, то и чекер не запускается. Поэтому в строчке answer пусто.
Если решение участника падает (по времени например), то авторское решение не запускается и строчка остаётся пустой.
Я сломал решение 424785 тестом [ab]49999раз + [ba]49999раз + с.
Затем прошло точно такое же решине на паскале:
И это же решение снова ломается подобным тестом! Правда не видно каким точно... Но суть вроде та же.
Может бага в системе?
Мне больше интересно как это решение прошло (обошло) мой первый взлом. Не должно же было. Тут же квадрат.
Там конечно было вот точно как у вас!
2. В вашем тесте не хватает девятки. На 4999 оно действительно имеет право работать квадрат.
3. По-моему, напрашивается вывод, что жюри зачем то пропускает очевидно неверное решение по задаче A. Либо мы чего то не знаем о процедуре delete.
UPD: на тимусе оно как не странно получает TLE (задача 1654)
Видимо вы угадали 41й тест. :)
Нет, взломы действительно добавляются. На всякий случай. Но мало и вручную. Т.е. это пока не автоматизировано.
Upd. нет, там все нормально, извините.
Поэтому его три раза ломали.
"Как вы уже успели заметить — система функционирует в несколько урезанном варианте. Мы решили перестраховаться и выключили на время контеста некоторую функциональность. После окончания раунда все вернется на место."
По моему это как-то намекает - )
But I thought it was obvious.
But, it returned correct answer on custom test with input of test 8.
Why did such a thing happen?
Oops. Sorry, I misunderstood interpretation of test result.
Thanks.
Открытый турнир Яндекса 2011<BR>Квалификация 1
http://acm.timus.ru/problem.aspx?space=1&num=1654&locale=ru
Никому ничего не напоминает?)
Может быть задачу B? :)
http://acm.timus.ru/problem.aspx?space=1&num=1445
_____________________________________________________
Похожие - значит у которых много решений, среди которых есть как минимум одно изящное? :) Тогда наверное вот эти:
http://acm.timus.ru/problem.aspx?space=1&num=1249
http://acm.timus.ru/problem.aspx?space=1&num=1614
http://acm.timus.ru/problem.aspx?space=1&num=1744
http://codeforces.me/problemset/problem/65/E
Try test:
abc
It's really hard to wake up before 11:00
It'd be nice to have a auto-translate option for comments in non-English. Using Google Translate API maybe.
"Not everybody understands what you are saying here. If using English, maybe we could understand each other better this way."
So you see, just a little in-joke for Chinese speaking people:)
can anyone tell me how to solve the problem E.
although it has tag of tree and dp, but i think it is not a tree, how can we to solve it with tree dp.
Each connected component in the graph has exactly one cycle. Pick any edge from the cycle and remove it from the graph, now we should consider two cases: a picked edge is in the answer and it isn’t there. Both cases can be easily solved with dp on tree.
Это код посылок 427555 и 427592 с соревнования (от Ministr).
Код абсолютно одинаков. Разница в том, что первая посылка получает
Превышен предел времени на взломе 1 [взломы], а вторая Полное решение [претесты].
Подумал-подумал и решил проверить это решение на систестах в дорешивании. Результат:
Delphi: Превышен предел времени на тесте 12, 1000 мс
FreePascal: Полное решение, 770 мс
Теперь мне хочется прогнать этот код во фри на сервере с тестом [ab]x49999 + [ba]x49999 + c. К сожалению сейчас это сделать невозможно (ограничение на ввод - 20kb).
UPD. На fpc - 3,5. Код здесь.
А вот этот код с 200k символами работает на fpc за 840 ms.
И 3050 мс на Дельфях.
Так что шанс сдать этот квадрат видимо был. о_О
Интересно что за тест был 2й и 3й, которые его поломали.
UPD. Да, оба не умеем считать)))
Тут всего 100Кб из 200 разрешенных условием.UPD. Считать не умею.
А точнее даже не об этом решении, а о том, как оно проходило взломы и было снова взломано.
Мое решение, которое не обращается к несущестующему символу. Памяти ест вдвое больше, зато не падает на aaabbbcc
2000-ый зарегестрировавшийся - erepb1991
При регистрации на вторую квалификацию мне сказали, что я регаюсь вне конкурса, потому что уже квалифицировался в первый раунд.
Значит ли это, что раунд не повлияет на мой рейтинг или все-таки повлияет?
Дай Бог что б сервак выдержал :)
Hi, can someone give me some hints for problem D? I have got to ask since there is no editorial available. Thanks in advance.