Божественно кодить можно не только для разных поисковых систем, но и в индустрии видеоигр — и не где-нибудь, а прямо на родине. Если не верите, то компания ZeptoLab, создатель известной во всем мире игры Cut the Rope, дает вам возможность убедиться в этом лично. И да, мы находимся в Москве.
Не секрет, что высот программирования достигают только те, кто много работает, в том числе — над собой и своим образованием. В ZeptoLab мы стараемся создать пространство, которое максимально к этому располагает. В частности, недавно у нас появилась корпоративная библиотека, где можно найти все необходимое для получения новых знаний, а также импровизированный читальный зал с диванами и креслами.
Также мы устраиваем чемпионаты по разработке внутри компании, чтобы наши ЗептоПрограммисты могли в свое удовольствие порешать нетривиальные задачки и помериться с коллегами нулями и единицами. Победители получают славу, ценные подарки и именное оружие (шутим, не оружие).
А с недавнего времени в Zeptolab открылась своя алгоритмическая школа, в которой преподает не кто иной, как создатель и руководитель всея Codeforces — Михаил Мирзаянов! Личность в девелоперских кругах немалоизвестная: Михаил уже тренировал команду, которая стала чемпионом мира по программированию, так что можно себе вообразить, какие горизонты развернулись перед разработчиками ZeptoLab и перед компанией в целом. В таком формате Михаил преподает впервые, в России и мире аналогов подобной системы корпоративного образования практически нет.
Для нас алгоритмы играют существенную роль, ведь требования к разработке стоят довольно жесткие: приложение на таргет-устройстве в идеале должно выдавать 60 кадров в секунду, и все расчеты игровой логики надо производить очень быстро и предпочтительно с простой сложностью в противовес амортизированной. Кроме того, у нас есть возможность делать неслабый препроцессинг, перенося некоторые вычисления на этап подготовки ресурсов для игры. Понимание этих фактов, как и множества других — вот ключ к быстрой работе наших игр. По этой причине мы поддерживаем движение алгоритмистов.
И впервые Зептолаб проводит конкурс по алгоритмической разработке, на базе Codeforces. Вас ждут нетривиальные задания, бескомпромиссная девелоперская борьба и крутые призы:
Ну и чтобы добавить интриги: будет еще один приз:
IPad Mini Retina мы вручим рандомно тому, кто попадет в ТОП-50 победителей конкурса и будет выбран вот так: мы просуммируем времена всех успешных попыток трех победителей (в секундах от начала контеста) и возьмем строчку с номером s % 47 + 4, где s — найденная сумма. Если вычисленная строка будет делить место, то приоритет будет у того, кто сдал последнюю из решенных задач раньше.
И на сладенькое: у того, кто покажет неплохие результаты по конкурсу, будет возможность устроиться к нам по упрощенной схеме. Если тебе интересно попробовать себя в команде ZeptoLab — поставь соответствующую галочку при регистрации.
О том, что такое работать у нас можно почитать тут: http://zeptoteam.ru/.
Чемпионат будет проводиться в один раунд. Формат соревнования — по правилам Codeforces. Раунд будет рейтинговым и общим для обоих дивизионов.
Дата и время проведения: 13 июня 2014, время: 19:30 — 22:00.
Разбалловка задач: 1000-1000-1500-2500-2500-3000.
Ура-ура! Соревнование завершено! Спасибо всем принявшим участие! Надеемся, что вам понравились задачи. Особые поздравления победителям соревнования:
- 1 место — KAN (Николай Калинин, Нижний Новгород) — iPad Air
- 2 место — winger (Владислав Исенбаев, США, Фейсбук) — iPad Mini
- 3 место — tourist (Геннадий Короткевич, Санкт-Петербург, ИТМО) — iPad Mini
Все участники, занявшие места с 1-го по 30-е получат подарки: замечательного плюшего Ом Нома и сувенирную футболку, а участники с 31-го места по 50-е получат в подарок футболки чемпионата!
Дополнительный приз достается участнику, занявшему 21-е место: package.zaic (Вадим Зайцев, Новосибирск, Новосибирский ГУ).
Хак — делать все сабмиты в моменты, кратные 50 секундам, чтобы в случае победы получить так же и рандомный приз)
Да, есть проблемка. Думаю, исправим )
Достаточно рассчитать время последнего сабмита :)
...предполагая, что раунд общий, задачи простые, победитель решит все)
Ведь некогда не знаешь, какой сабмит станет для тебя последним на контесте)
Challenge accepted! Спасибо, немного изменили правило выбора.
И вновь рандомные призы... На этот раз хоть для топов :)
Футболки классные, но их мало. :С
А возьми и займи первое место! Или эта задача не для Ворса?
I think it will be good contest. We will see.
А кто автор проблемсета?
Задачи подготовлены совместными усилиями команды Codeforces и программистов ZeptoLab.
...
What is the degree of difficulty of problems? like codeforces one?
Didn't you see this when editing your comment? :
You may edit your comment only for fixing grammar mistakes or small changes.Do not change the main idea of your comment.All previous revisions are available for others. Are you sure you want to edit comment?because I do a big mistake that :
I post my comment (in russian) mode :|
then I edit that comment and that comment change automatically :D
Do is incorrect.
Did is correct.
Thank you :|
You're welcome. :)
"Code Rush" говорите?
http://ru.wikipedia.org/wiki/CodeRush_(программа)
https://www.devexpress.com/Products/CodeRush/
Спасибо за находку, будем готовиться к возможным вопросам. Хотя у нас пробел в названии ;)
Я вас не сдам :-) Хотя мы CodeRush выпускаем с 2002 по-моему года.
Вон оно как! Тогда двойное спасибо =)
"И на сладенькое: у того, кто покажет неплохие результаты по конкурсу, будет возможность устроиться к нам по упрощенной схеме."
"неплохие результаты" об этом можно поподробнее или это для Div1 только?
Раунд будет общим для двух дивизионов, и у всех участников будут равные возможности. Просто старайтесь, как всегда, максимально хорошо решить задачи )
The contest lasts 2h30. It has how much problems, viktork!
Seems very funny :D I like this kind of round.
Мои наилучшие пожелания автору который не стал создавать новый логин (фейк), а брутально запостил объявление о приеме на работу для желто-красных со своего зеленого акка :D
Спасибо :)
доминируй, властвуй, унижай!
в зептолаб наверно неделю не могли найти человека с аккаунтом корпоративного цвета, потому что там только красные и немного желтых. А вы стебетесь :(
Дизбаланс, однако.
Да он просто 2 года раунды не писал. Вероятно тогда еще не работал в ZeptoLab, поэтому был только зеленым))
Ну у нас же не Киндза-Дза какая-нибудь — приседать разное количество раз для ников разного цвета :)
По вопросам о приеме на работу можете обращаться ко мне напрямую — с радостью все расскажу.
How will this round be rated (keeping in mind that both divisions can participate)?
like this round
Good Bye 2013
Если бы рядом с парнем на заднем плане тоже стояли три милых девушки, я бы подал резюме.
Честно говоря, еще две девушки, которых нет на фото, сидят по соседству слева и справа от него )
Вот только на фото с лекции с MikeMirzayanov почему-то подозрительно мало девушек)
Одна девушка там все-таки была — фотограф :)
А блондиночка ниче такая!
Судя по ее взгляду, ее сердце принадлежит парню в красной футболке)
а может и девушке в оранжевой футболке;)
I love cut the rope and I will love this contest
Oh, Cut the Rope is an interesting game, and I have designed a problem based on the game mechanics in "DJ Box": CandyOnDisk.
I saw the website is in Russian, does it means the working language in ZeptoLab is Russian?
After this announcement I decided to try Cut the Rope app really really it's Amazing game
this is an English version
http://www.zeptolab.com/
Wow, a good problem! If you wish we could ask you to be a co-author of the following possible contests in the future. We are an international company, but yes, our working language is mostly Russian at the moment.
Yes, there are mostly russian-speakers here. But we do have offices outside Russia — so your English language won't be a problem :)
Watch it if you want
This video make me download this nice game it's really has a nice character I love it :)
Does that mean Top 50 have T-shirt with their name on it? Really awesome! Achieving that result is hard though..
Can anyone participate or it's just for Russians?
There is no difference
Registration started earlier than expected. :))
У меня вопрос. Необходимо ли валидировать входные данные на корректность? Например, в условии написано, что на вход из стандартного ввода подаются 2 целых числа через пробел, нужно ли проверять, что ввели реально 2 числа, а не 2 символа, или подразумевается, что входные данные будут именно такими, как в условии задачи?
Гарантируется, что все входные данные соответствуют ограничениям в условии.
знаю препода, который при виде текста: "на вход 2 целых числа" пишет "one two"
Lol, I wanted to google "Cut a rope", but instead "cut the rope" I mistakenly typed "cout the rope" :P.
I remembered when I told my friend do you watched breakpoint Series and I mean Prison Break Series :D
Подавать заявку на работу есть смысл только москвичам?
Вовсе нет, у нас работает много сотрудников со всей России и ближайшего зарубежья. После трудоустройства они переехали в Москву, потому что удаленной работы у нас нет.
How many problems will there be in this contest?
Привет коллегам-игроделам!
Миша Лялин был у нас в гостях в бизнес-инкубаторе МГУ :)
"The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, Go, D and JavaScript." — and usually Perl is not forbidden! Thanks for early opening of registration and early notification about round.
Will there be any indicator of who is the random owner of iPad Mini during the contest?
UPD Damn, I realized what was wrong with my comment 8 months later I posted it O_T By "random" I didn't really mean random but (quoting from the post):
Ждем с нетерпением начала раунда:)
Does this contest influence the rating?
The round will be rated
Рейтинг потечёт из div. 1 в div. 2 или наоборот?
Думаю, наоборот.
Over 4000 people doesn't watch World Cup today
When score distribution will be announced?
Why is score distribution so important for many people?
Because of thinking about strategy. and knowing number of problems and preparing file for each problem.
Что там уже насчёт разбалловки?
все очень плохо!
Registration users are 4664 :) lucky palindrome
А это разбалловка относительно задач div1 или div2?
Не знаю почему, но у меня кнопка "Отослать" не нажимается. Браузер — последний Хром. Отдебагать что происходит — тоже не могу, кто-то добрый override'ит клики правой кнопкой мыши по ней, так что inspect element не работает.
Upd. Разобрался, она была disabled (хотя внешне это незаметно), видимо, disabled не убрался при выборе задачи из-за какого-то race-condition'а в JS (ну или ещё почему).
Can two items have the same "H" in Problem A? If yes, can "Om Nom" eat both of them? Or just one of them? Thank you.
I suggest you ask stuff like this through the "Ask a question" form (see contest dashboard)...
Теперь я понял, почему так редко раунды проводят зеленинкие — потому что их даже красные не могут решить..
строго говоря, viktork писал раунды 2 года назад, так что нельзя ничего утверждать о его уровне сейчас
а кто знает, у Гены есть девушка?)
Слухи ходят, что есть.
Сначала в задаче Б говориться, что поле NxM, а потом оказывается, что N — количество строк, а M — количество столбцов. Тогда уж MxN пишите.
Я например кучу времени убухал, писав решение для NxM. А когда узнал, что поле MxN, совсем желание отпало участвовать в конкурсе, где в наглую пытаются надурить...
А ещё получил compilation error того, что на компе у меня компилится
посмотрите строки компиляции на codeforces. http://codeforces.net/blog/entry/79
может, проблема из-за этого. посмотрите чьи-нибудь старые посылки на Java, и все поймете.
эмм. так-то все верно. не понимаю, на что вы жалуетесь. обычно так и пишется.
лучше прочитать задачу целиком
Всегда так пишут. Так в циклах удобнее, как минимум. Первый for соответствует количеству строк.
если бы у меня возникла такая ситуация, я бы при вводе поменял бы порядок M и N :) скорее всего все было бы норм
По-моему, достаточно распространён подход писать сначала кол-во строк, затем-кол-во столбцов.
Очень понравилась задача C. Отличная идея! :)
в С жадно набираем, типа как в Приме?
C — это и есть Прим. Миностов то есть :)
Мощно у Petr D на последней минуте зашла.
UPD: Не, не зашла(
Thank you! Contest was fantastic.
This comment and your avatar makes a perfect combination :D. But agree, contest was awesome.
Может ли в Е проходить такое: храним в индексированном бинарном дереве всех пользователей, которым надоела реклама, перебираем тернарным поиском суффикс, который даст наибольшую выгоду, если целиком клянчить бабло с него.
Нет, функция сильно невыпуклая.
Мне кажется дискретные функции редко бывают унимодальными.
Ну мы по факту добавляем на отрезке [0,p] прогрессию [0, , 1, 2 ,p] и надо выбрать максимум в ячейке.
Ну тогда если мы добавлии 12345 и 12 то получится 24345, что не является выпуклым, т.е тернарник не должен работать
Доход может быть не монотонен от стоимости. Если у нас есть 10к пользователей, готовых платить 1, 1 пользователей, готовый платить 2, 1к пользователей, готовых платить 10к, 1 пользователь, готовый платить 10ккк, то доходы получаются (11002, 2004, 10010000, 10кккк).
Блин, точно. Надо учиться сначала думать, потом писать~
Видимо имеешь ввиду задачу F.
Для тернарного поиска функция должна быть выпуклой. Пример с невыпуклостью придумывается на раз. Например, числа: 5 5 9 10.
Да, F. Привык уже, что E последняя в проблемсете)
The little drawings of Om Nom in each problem were really nice and cute :)
i don't know why but for almost an hour I thought in problem C you could only use the last sent level!
did anyone else understood the problem in this way ?
I wasted a ton of time thinking the same thing!
The same >.<
me too !
(
Me too, but then I looked at the sample test :P.
i have made this mistake (not solving/looking at the sample test) a lot of times and i never learn :D
How was C supposed to be solved?
Create a complete graph: weight between level i and j is min(n*m, w * their difference).
The answer is then n*m + Min cost span tree in this graph.
Minimum spanning tree
It is nice to see the beautiful pictures in the statement. :)
Seems the hard tasks are all about data struct and the code is long, looks like an OI contest.
Yeah, except OI involves long codes because it has full feedback and no time penalties.
Can anyone please tell me why this is not a correct solution for C ?
It is.
I got WA in test case 3. This is 3rd case of C.
Could you be printing null characters or something? Link to your code.
http://codeforces.net/contest/436/submission/6883198
You output 12 as the cost, while it was actually 11.
In my pc it generates the output which i gave to u, but for the same code codeforces generate another output. Although my solution may be incorrect, thanks anyway. I am looking forward to it.
After sort(), the order of edges which have the same w is indefinite. And unfortunately your algorithm for calculating cost is incorrect. These are the cause of different output. Additionally,
if(par[r] = r) return r;must beif(par[r] == r) return r;It appears correct to me.. Did it give you WA?
Yes it gave WA in test case 3, I include my solution.
The output is correct , may be the way that are you printing the output is the problem , maybe you are using printf("%d\n") y using long long .
Great problemset... However, so many participants worked out only A, B and C. And among them, they only compete who code faster... Sad story :(
Is there going to be an editorial?
When will be the editorial available?
Wow fast system test!
relevant comment :D
Как решается Е? Я пробовал жадно набрать по относительной стоимости, и, если у нас вышло на 1 больше, чем нужно, выкинуть эту одну лишнюю звезду. Это я пробовал сделать, меняя какой-то уровень с 2 до 1, с 1 до 0, и меняя один уровень с 2 до 0 и проходя другой уровень на 1 звезду. В общем, вы уже поняли, что это не заходит.
Мне кажется должно работать следущее: набираем звездочки с минимальным средним костом, пока не останется BUBEN, а потом рюкзак
Что значит BUBEN? :)
Я брал с минимальным средним костом до тех пор пока не наберем все или пока не останется одна звезда. Ну и последнюю звезду тоже естественно с минимальным костом. Почему-то WA13. Кто скажет почему? :)
Посмотрел тест.
Контрпример:
2 3
5 7
3 6
Нужно взять 7 + 3, а описанная жадность берет 5 + 6 :(
Спасибо, кэп!
Я имел ввиду, что это значит в контексте данного решения.
Ну имелась ввиду какая-то константа, взятая изниоткуда.
Короче, это не зашло, WA10:)
Вот, кстати, жадное решение 6885072, получившее АС.
Можете рассказать про жадность?
Можно же решение почитать ;)
О, а внизу уже есть описание этого решения.
Наверное меня засмеют, но блин, как нормально решать A? :D
Надо перебрать начальный тип, а потом брать самую большую по массе из тех, что можно
Вот блин, при копировании забыл один символ изменить >.<
Таки победитель по жизни, все дела.
Сортируешь предметы по высоте и начинаешь с карамельки, потом с леденца. Дальше обычная максимизация высоты прыжка, просто на каждом шаге берёшь доступный леденец/карамельку с максимальным весом.
Это я так туплю или тут действительно не обойтись без set/priority_queue?
С такими ограничениями решение за квадрат заходит.
Set тут не нужен. В этой задаче вполне заходит решение за квадрат. Просто на каждом шаге перебираешь предметы и выбираешь из них доступный с максимальным весом.
Как сказали выше, квадрат прекрасно заходит, там же ограничение 2000 конфет.
Влоб можно было
Почему всегда нужно начинать с карамельки?
он имел в виду, сначала пробуешь начать с карамельки, потом с леденца
Он имел в виду, сначала пробуешь начать с карамельки, потом пробуешь с леденца. Выбираешь, что лучше
Почему не всегда лучше начинать с того типа конфет, которых больше?
Контрпример:
Контрпример: леденец на высоте 2, 100 леденцов на высоте 100, карамелька на высоте 1.
I am never able to hack anyone's solution until my own solution for that problem is wrong and I realize that after locking the solution :(
Problem A is not clear. I thought after Om Nom eats a candy, it continues hanging on that rope instead of jumping back to the ground :( I lost many precious minutes.
No, it does not. (At least: I did not assume that and got AC... I'm not sure about anything after seeing the results of problem E...) How would it do that, anyway? What a strange idea...
Me too :( In Cut the Rope the game, Om Nom cannot hang onto a normal rope, though...
А в Е тернарку на декартово специально не пустили?
У меня зашло после избавления от merge/split в самом вложенном месте: 6884993
Объясни, что ты имеешь ввиду. У нас было решение на Java с декартовым деревом.
Понятно, что если мы отсортируем по b — a, то все синглы будут раньше всех даблов. Так же понятно, что если мы знаем, что все даблы мы берем из первых i, а все синглы — из оставшихся, то можно посчитать сколько именно даблов мы берем тернарником
Собственно, это моё решение на Java с декартовым деревом. Не нужен же тернарник. Мы можем бегать по дереву, имея частичные суммы в поддереве. Кажется, это даже проще тернарника. :P И даже такое очень тяжко взлетает.( http://pastebin.com/guuz5qjh
Так ну естественно нужны частные суммы. И как без тернарника обойтись?
А, видимо чуть другое решение.( Я доказал, что после сортировки по b, мы можем перебрать префикс, который мы возьмём точно хотя бы на 1 звезду. А далее нам нужно найти оставшиеся звёзды из b-a с префикса и a на оставшемся суффиксе. Это просто делается декартовым деревом, если ходить в нужное поддерево.
Will the problems be available for solving after the contest? Took just a little too long to solve E ={
I can't find my mistake in Problem A, please Help
My code
Consider input:
Your program will start with type 1 (because the mass is large), and will be able to collect only 2 candies. The optimal answer is 3.
I cant submit my code . Please fix it.
Congratulation to package.zaic!!! You won an iPad.
Luckiest guy of Friday the 13th! Congrats :D
Saturday the 14th.
134-th place expected, 134-th place in the standings!
And fast systest is fast :D
Achievement unlocked: failed systest on a problem from Petr Mitrichev Contest :) (problem F)
orz
Through author of reference solution for that problem take a glance at the code in polygon and decided to rewrite from scratch and got OK ;)
Petr tasks are so hard, so even Petr can't solve them.
Do you know any solution faster than O(n*sqrt(n))?
I think I had some O(n*polylog(n)) in mind when I gave this problem, but I can't remember now :(
I solved this problem on your contest, but for some reason this time I decided to use segment tree instead of sqrt decomposition. Unluckily, I realized that the idea is wrong and sqrt decomposition can't be replaced with segment tree in this case only 12 minutes before the end of the contest after spending almost an hour in debugging. And I realized that I've already solved this problem only after reading your post here :)
I implemented incorrect segment tree solution too, but I had more time to rewrite it :)
problem F is equivalent with which one of your problems?
It hasn't been published, but it's called "Business As Usual".
Thank you.
So was your code actually wrong? I'm starting to think problems are not available for practice because they're double checking the test cases of that problem =P
Yes, it was wrong. The problem on my contest didn't allow a[i]==0, and the solution didn't handle that correctly (but only one part of it, so it worked when n<=sqrt(maxn)) :)
is there any chance of interview from with rank 465
Hey! Look at this: http://codeforces.net/profile/worse
He/She is trying to be the worst in every contest! So He/She solve a problem, and hack solutions with easy testcases!
Why do you know ?
you can look at the standings, and turn to the last page.... you will see two funny coder....
relevant comment
In problem E, is the correct solution to split the levels into two groups, where b>a*2, and b<=a*2, and choose how many stars to get from each group (since for both groups it is possible to find the answer in O(1))?
I had something completely different in mind: sort the levels by 1-star cost; if we pick the rightmost (i-th) level with 1 star, all levels to its left must be either solved for 1 or 2 stars (otherwise, we have a better solution). Then, if we picked the number K of 2-star levels to its right, then we know how many to its left need to have 2 (or that it's not possible). It's clear that we pick the cheapest ones (by bi to its right, by bi - ai to its left) then. The cost of this first increases and then decreases as we increase K, because what we add levels with larger bi and remove levels with smaller bi - ai. Now, we iterate over all i from left to right, the sets that we should pick don't change much with each iteration, so we just need set<>s to simulate it. I'm getting TLEs and other fails, though, so maybe it has a loophole... but it's hard to code, anyway.
My idea was that if for all levels we have b>a*2, then we can make a list of a and b-a for all levels and sort it. If the optimal solution includes b-a, then it must also include a. If for all levels we have b<=a*2, then the optimal solution can have at most one level with 1 star, all others must have 2 stars.
So we split all levels into these two categories, precompute partial sums as required, and choose how many stars we want to get from each category (obviously, the optimal answer gets exactly w stars).
А как решалась D?
I would like to thank dreamoon_love_AA for sharing the 51st place with me. It is comforting to know you are not the only one who is the first to win no material prize.
DEL
Have result ?
please update the ratings soon:)
I hope that
I got the logic for C but couldn't figure out how to print operations in order. When i figured it out there was only 1 min left. Bad luck :(. Anyways when will the problems be available for practice.
Dunno what you did, but I just found the differences between levels; these are the costs of edges of a complete graph (+ 1 node with edge costs NM from it), and I just need to find its minimum spanning tree. That's done by adding edges, so I have the edges' order given directly by algorithm.
I found the MST using Kruskal, than I was not able to figure out the ordering about which I came to know when I submitted my solution the one without ordering and got WA on 1st testcase. Later I figured out that I should do DFS to get the order but only 1 min was left and couldn't code it it in time.
And I also started out at around 9:35 IST (around 35 minutes late).
Not a good idea — if you don't submit anything, it's as if you didn't register at all. You should've waited until the contest was over and virtual-participated.
I meant to say I started 35 minutes late. I have correctly submitted A and B but couldn't submit C after correcting the ordering.
Yes, I understood that. I'm saying that you shouldn't have submitted anything.
Will keep this suggestion in mind from next time. And now I am again Expert :(
I did the same thing and wasn't sure how to find the order. Then I switched to Prim's algorithm, which gives you the right order for free.
This is a really nice idea. Thanks for this one :)
If you got the MST, you can pick any root and simply print it out in DFS/BFS order. Prim's algorithm gives a simpler solution, though, because you can use N^2 instead of priority queues, and get the edges in the correct order.
You may consider using Prim instead, it's easier to write edges back
UPD: has been answered above. I didnt mean duplicate comment. sorry :(
fix it -_-
Задачи-то можно будет дорешать?
How can I resubmit my solution ?!
The system don't let you resubmit the code submitted
editorial and rating are wanted!!!
quickly ! quickly !
Since I have made it to top 50, what does "name-encrusted weapon" means? Itching to get that :P
In problem A, many people got WA on 37th test case and me too. Can someone tell me the trap of this test case? Thanks!
Try this test:
3 2
0 1 1
0 2 2
1 4 4
i hacked this solution with the same input.
well, not totally the same, but i guess our ideas are. :)
В задаче А, что за коварный 37-й тест?
Думаю, дело в том, что среди всех доступных конфет выгоднее брать конфету с наибольшей массой.
Mine failed on 36th :(
а разбор будет? или как решать С?
Строим минимальное остовное дерево. При этом рёбра, которые выйдут тяжелее, чем n*m удаляем. В итоге получим лес деревьев. Для каждого дерева выбираем корневой элемент и тратим на него n*m ресурсов, оставшиеся создаём обходом в глубину по рёбрам, в которые переходим.
P.S. Реализацию можно существенно упростить, если не рвать рёбра явно, а просто ставить им вес n*m. Тогда получим одно единственное дерево, которое и обработаем.
Реализацию можно еще упростить, если добавить фиктивную вершину 0, из которой есть ребра веса n*m во все остальные вершины, и построить каркас в полученном графе. Тогда после построения каркаса достаточно ориентировать его одним DFS'ом из вершины 0.
Если считать остов с массивом минимальных расстояний, то фиктивную вершину можно добавить просто в уме. Всем вершинам заранее проставляется расстояние N*M и сразу можно запускать обычный цикл поиска ближайшей и обновления от неё. Таким образом я даже не строил явно граф, рёбра считались прямо в остове.
А если еще и запустить алгоритм Прима из вершины 0, то при построении каркаса как раз и получим эту ориентацию.
Блин, я и забыл, что у нас полный граф и выгоднее использовать Прима)
большое спасибо, но к сожалению, я еще не готов к решению таким решениям...
А в чём проблема? Никогда не искал минимальный остов?
да, и вообще страшновато звучит, если честно, то разбор Fefer_Ivan как-то проще выглядит. я понимаю, что по сути — одно и тоже)) в любом случае спасибо, попробую завтра разобраться))
waiting DmitriyH' statistics :)
I just learned that (a maximization version of) E is known from a Polish middle-school OI :) And, if you're Polish, here's a link to a video editorial of it: https://www.youtube.com/watch?v=hhrLaokKBtk
Yes, I watched that during the contest XD.
It was a funny story, because few months ago I was solving exactly the same problem in TopCoder, but for n<=8 as a part of some 500pts problem and I told my friend about it and then he told me that johnasselta proposed this for a middle-school OI, but I haven't came up with a solution, but today I learnt that this problem has a video editorial xD.
Is there any link to this OI problem?
i just noticed that the OIG logo is very similar to the CF logo :)
Is there any way to see div2 only ranks?
Round Stats
My screencast: http://codeforces.net/blog/entry/12682
У меня по E зашло следующее:
Будем набирать звездочки по одной. Каждый раз смотрим 2 варианта, из них берем самый выгодный: 1) Просто повышаем какой-нибудь уровень на одну звезду. 2) Находим уровень, на котором последняя собранная звезда была самой дорогой, убираем эту звезду, а вместо этого находим какой-то уровень, который мы можем апнуть сразу на 2.
Все это решается с помощью priority_queue(или, может, сетов). Кто-нибудь может пояснить, почему это должно проходить???
Ну как — рассмотрим оптимальные решения для w и для w+1, и вычтем первое из второго.
Получится для каждого типа число от -2 до +2, в сумме дающие +1. Заметим, что можно считать, что например +1 и -1 одновременно быть не может в наборе — если бы были, то либо эти два изменения в сумме положительны, и тогда их можно применить к ответу для w, а значит он был неоптимальный, либо они в сумме неположительны, а тогда их можно убрать из ответа для w+1 и хуже не станет. Аналогично, можно считать, что +2 и -2 одновременно не бывают, и что +2,-1,-1 одновременно не бывают, и что -2,+1,+1 одновременно не бывают.
Но какой-то плюс должен быть, ведь в сумме 1. Если это +1, то ничего больше нет, потому что -1 запрещены, а -2 потребует ещё двух +1, что тоже запрещено. А если это +2, то должен быть ещё -1 и больше ничего.
Итого всего два варианта +1 или +2,-1.
In problem A test 5, how the answer is 2? Why it is not 7?
What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?7 is impossible as there is only one caramelYou can't eat the same type (1) twice in row, you can't start with type 1 (not enough high), and if you eat the (0 1 3) first, you can eat one type 1, and nothing else (you are still not high enough to eat 0 20 3).
Tnx. So I misunderstood about the meaning of 'in a row'.
Finally I'm RED!!!! After failed on TopCoder SRM 624 because of stupid MOD issue :'(
Anyway, thanks for the amazing round. I will remember this round forever :)
Congratulations! I wish someday I become red too like you :)
Спасибо за раунд, задачи и красивые рисунки в условиях! :)
Почаще бы такие DIV-смешанные раунды..
В таких смешанных раундах хотелось бы видеть какой-то более сбалансированный набор задач. Даже первая задача — для значительной части div2 слишком тяжелая. Это судя по таблице и числу нолей по этой задаче; а я знаю нескольких людей, которые открыли задачи, усердно пытались решить хоть что-то, но в результате ничего не придумали, и в таблице их даже нету. Переход от третьей к четвертой — скачкообразный. Было бы лучше, если бы четвертую по сложности задачу решило 150-200 людей. ИМХО можно было даже вставить что-то "промежуточное" дополнительно четвертой задачей в этот проблемсет, на 2.5 часов и 7 задач дать не страшно.
Я не смотрел на рисунки во время раунда, пойду хоть сейчас оценю их)
особенно с учетом
в результате больше 2-х задач решило 600 человек, а больше 3-х — 50. Как говорила принцесса Лейя, "что именно тут неплохо?" :)
How amazing it is! viktork became 21th top-contributor because of only one blog. Most positive blog ever.
+710! really amazing!
В тесте задачи Е:
5 3 10 20 5 10 10 20 6 9 25 30
Почему 01000 не может быть ответом? Ведь игрок набрал достаточное кол-во звезд (5>3). Объясните пожалуйста.
В вашем ответе игрок набрал только одну звезду. Каждый уровень характеризуется двумя целыми числами: ai — сколько требуется времени, чтобы пройти уровень на одну звезду, bi — сколько требуется времени, чтобы пройти уровень на две звезды (ai < bi).
Все понял. Спасибо большое. Блин, как я мог так запутаться, прочитал текст по несколько раз и все равно)
Господа участники! Всем еще раз спасибо за эту схватку, было захватывающе) Отдельное поздравление победителям — ваши призы в ближайшем времени будут собраны в кучу и отправлены по адресам :) Сейчас мы собираем данные по размерам ваших футболок, дабы всем все было в пору.