Всем привет!
Добро пожаловать на Codeforces Beta Round #77. Как вы наверное догадались, автором задач сегодня буду я, Герасимов Виталий (witua). Большое спасибо Артему Рахову (RAD) и Павлу Кузнецову (it4.kp) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий и Codeforces (CF) за существование.
Всем удачи!
Добавлен разбор.
(Just a hunch)
(Then suddenly noticed 77 , everything clicked)
http://www.topcoder.com/stat?c=problem_statement&pm=11462
(I just read 1 problem and wrote the solution, and when I clicked submit , it was disabled. So thought , it would be good to know exact timing.)
rng_58 is red, not rng_57
for example link of CF #76(div2 only) is : http://www.codeforces.com/contest/94
(looks like problemset is completely disabled but /contests/ links are working.although links do not appear on contests page.)
oh boy! Obviously my account is fake!
Just I am a big fan of this great Actress!
Счатливые числа со Львова! Даже номер контеста счатливый :)
I can't submit because apparently I'm not registered.
I thought I did register...
Thanks
If it was so, you would not be directed to the registration page. I missed two or three contests because of this reason...
I wonder what could be the reason. :)
Можно представить элемент x с ограничением на количество y в виде 2^0*x + 2^1*x+...+2^k*x+z*x. Где 2^0+...+2^k+z = y. И далее решить простой рюкзак.
Прошло.
Смотрите. У нас есть сколько чисел, с общей суммой n. Различных среди ни не больше, чем 2*sqrt(n). Каждое из них можно использовать сколько-то раз. Пусть какое-то число x можно использовать k раз. Рассмотрим вместо него несколько чисел x, 2x, 4x, ..., 2^log[k]*x, и всё, что осталось до xk. Понятно, что любое количество x можно представить, как сумму нескольких из этих слагаемых. Теперь будет порядка sqrt(n)*log(n) чисел, каждое из которых надо использовать не больше одного раза - получился обычный рюкзак.
Сам себе злобный буратиноснова здравствуй, второй дивизион. :-)Вместо Флойда можно было пустить Дейкстру N раз за NElogN.
UPD. хотя не, можно и в простых int сделать, если аккуратно... так что есть такая вероятность.
Так что думаю нельзя.
if (w[i] == letter && letter == 'a') replace_with('b')
is awesome tricky :)
wclee2265
is a cheater. He has only one minute between two submits for problems A and B (Div 2). More than that, he solved them quite late. The source code for problem B is quite huge. Admins, please, check this out :)Why the output of the third text is abCacba,not abCccba.It is hard to understand.
Yes.You are right.It is a regret that I hav't asked the author.
(on test 21 or any other, and how did you correct it?)
I am unable to see whole testcase.
I request the author to give me pastebin/ideone link for Test No. 21 .
I will be highly thankful.
for(i;i < a.size() - b.size() +1; i++)
unsigned integers should not be compared with signed ones.....
Actually I saw the RE and AC codes of bloops ,then came to know.
So, You and bloops gets full credit from my side.
Thanks to bloops too.(may be he doesn't even know that he helped me)
http://ideone.com/Z2eS6
Странные какие-то тесты на codeforces.. Чем им не понравилься мой код.. У меня пашет, а у них почему-то виснет..
http://pastebin.com/sU5SxGG7
Очень опасная строчка. Обычно /n бывают в конце, но никто не гарантирует. Вдруг там EOF?
Тогда уж надо было с '\n' сравнивать.
И автор возможно под линуксом пишет, поэтому у него работает (чисто предположение, вполне может быть неверным).
Да.. идея из посимвольным чтением не опрадала себя.. Впредь буду в подобных ситуациях пользоваться cin.getline(). Модефицированый вариант задачи получил вердикт "Полное решение".
http://pastebin.com/P6wpPjC4
The Balance is restored. :-)
After struggling for a while, I closed all the pages and retried... and I succeeded when I loaded only one page...
This took me around ~10 minutes...
Е: Превышено время на 91-ом тесте
фэйл :(
То Таймлимит ты получишь.
На совсем крутой задаче
Юзай кучу Фибоначчи."
(c)ЛКШ
Контрпример:
1
SekbyedgXMVponfrIyFFUNcGBlQEopWOVYtUlRaMiAFglfo
hJHDzSDeGRvvjIQAVJPNBeTjKDubHTIzkYLLMYxiW
c
Yes, I am sure.
P.S. There is no super lucky number in this case, only lucky.
My solution gave RTE on test 52 as well. I was not sure what was wrong because (I thought) I tested it on all possible combinations (of 1,4,5,7,9). Well, turns out I did not. 4 digits were not enough
For anyone else having the same problem, try this case:
477747
Div 2 problem D is very nice. Thank you the author! This problem can train ours ability of thinking about the problem completely.I learned a lot after AC this problem.
(сам так писал, и все зашло, правда, работало 1380 мс)
немногосложная в реализации и набажить в ней очень просто, особенно при удалении вершины из кучи, хотя наверняка есть какие-то фишки которые все облегчают.В целом, немного дегтя:
1. Лишние параметры в условии - скучно. Зачем в задаче A-1 давать букву как параметр? Это что, делает задачу интереснее? Возможность поломаться на 'a'/'b'? Зачем вообще нужно несколько различных строк-шаблонов? (тот же вопрос) Почему нельзя обойтись одним? Зачем вообще все это чудо с регистрами?
2. По задаче В - я все понимаю. Число называется интересным, если не содержит цифру 1. Число называется очень интересным, если оно к тому же не содержит цифру 2. Число называется совсем интересным, если к тому же ни одна из его цифр не делится на 3. Число называется счастливым, в нем нет цифр из шутки про предел. Можно писать условия так, только зачем? Почему сразу не сказать, что число очень счастливое, если состоит только из одинакового количества цифр 4 и 7?
3. Задача С. Без комментариев. Задачи на Дейкстру всегда такие задачи. Ну, давайте есть пчел.
ну и т.д.
2. В этой задаче было аж два (!) объяснения, условие вписывалась в 6 строк. Не думаю что в участников была проблема с ее пониманием, тем более что первый абзац - самое обыкновенное вступление.
3. Стандартная задача. А почему бы в контесте не одну стандартную задачу? Тем кто ее никогда не делал это пойдет на пользу, те кто ее делал справятся с ней без проблем.
4-5. Почему вы о них ничего не говорите?
2 - Первая фраза просто лишняя. В ней дается определение. Это определение дается во многих других задачах. Это вызывает желание ее прочитать. Ты читаешь ее, потом читаешь вторую фразу и понимаешь, что первую фразу прочитал просто так. У меня уже это вызывает острый приступ желания не решать контест и идти домой.
3 - Да, стандартная, но:
По просьбам автора.
4 - комбинаторика, стандартная задача. Из смешных в эту группу следует отнести разве что эту, там неожиданно левее середины все меняется.
5 - задача в стиле "ну и пусть".
Вообще, не очень люблю задачи, которые надо просто знать. Максим Буздалов, например, писал диплом по задаче о рюкзаке. Думаю, что задачу Е он сдал бы быстрее, чем задачу А div 2.
Да, решение номер два из разбора можно придумать, но в формате CF придумать - это неизбежный проигрыш. Да, я помню, как на тренировке, не зная строковых конструкций, придумал min-lex-shift за N*log(N). Минут за 20-30, что составляет примерно 25% времени соревнования на CF. Не думаю, что это бы поставило меня в равные условия с остальными участниками.
В любом случае, это больше подходит для сообщения "еще одна задача" пользователя ilyaraz, не для задачи Е соревнования.
По поводу задач, я не согласен. Именно мне понравились :) [не считая С, каторая оказалась скучной, надо было прость Дейкстру знать и всё]
I see a lot of these during SRMs when someone misses to register by 1 minute or so....they say i missed the match "5555555555".
Am I correct ?
But I want to know how to solve this problem? Can you help me?
Petrosianeditorials!