Codeforces Beta Round #87

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Добро пожаловать на Codeforces Beta Round #87!

Таинственным автором сегодняшнего раунда оказался я. Как обычно, раунд состоит из семи задач (по пять в каждом дивизионе). Я не могу прямо сейчас раскрыть условия, поэтому единственное, что могу сказать: мне нравятся все сегодняшние задачи. Спасибо RAD и Delinur за вычитку и перевод условий, проблем с пониманием быть не должно. Надеюсь, что и вам задачи понравятся :)

В некоторых условиях будут картинки в формате .png, поэтому убедитесь заранее, что ваш браузер их поддерживает. Проверьте, видна ли картинка в задаче Время грабить корованы (автор: Alex_KPR).

Хочу поблагодарить it4.kp за тестирование (уже в ~~четвертый~~ пятый раз - он тестировал 4 моих SRMа), а также RAD, MikeMirzayanov и всю команду Codeforces за отличную систему и возможность провести раунд! Кстати, именно тут я получил приглашение на стажировку :)

Так что сейчас я из города Кракова желаю удачи всем на Codeforces :)

Не забудьте вернуться на эту страницу после конца контеста.

<продолжение следует>

Это перевод оригинального поста, поэтому английский в комментариях приветствуется [примечание переводчика].

Комментарии (99)

Показать архивные | Написать комментарий?

RodionGork

13 лет назад, # |

← Rev. 2 →

Since "from Krakow now", could you please include in future contests some problems about Ijon Tichy and possibly other Stanisƚaw Lem's heroes? ;-)

→ Ответить

dolphinigle

13 лет назад, # ^ |

You're too late, this is my last month in Krakow :)

I believe such a mighty problemist could create two or three contests during one month! Ok, it was almost joke, never mind! :-)

it4.kp

Thanks for mentioning me, but I didn't deserve it this time.
The only thing I did was comparing the difficulty of two problems. I didn't even read the other ones. So, this is definitely not testing :)

kyuridenamida

Will the strange illustrations appear!?

sdryapko

← Rev. 3 →

In what SRM's you were a problemwriter?

List of Topcoder's problems I authored

bolivar1997

га га

d1xlord

Thanks a lot. Hope to have a great contest (and great translations :D)

Sammarize

промахнулся с языком.

And again, I'd compete, if time of start of round was later, then standard 19:00.

ir5	13 лет назад, # \| 0 Toastman may appear in the statements. → Ответить

ivan.metelsky

Maybe even Toastwoman. :)

Though, on a serious note, it seems dolphinigle doesn't reuse his characters too often, so I would expect some new heroes.

So sorry to disappoint you ;)

Anastasko

Надеюсь, условия будут не длинные. Люблю краткие, чтобы не читать 5 минут.

crazy_bober

Достали уже такие комменты, не хочу ничего говорить про конкретных людей, но думаю многие начали это писать из-за вклада(обычно такую ересь всегда плюсуют:( )

I_love_Tanya_Romanova

А так же плюсуют ересь, которая описывает плюсование выше написанной ереси, и ересь, которая описывает плюсование ереси, описывающей плюсование...

Да сбейтесь вы уже с темы вклада:)

tunyash

Да, да, плюсанул.

Лучше всего плюсуют комменты типа "контест был г-о, потому что я его слил. Задачи А-Ц были каждая отдельное г-о потому что я их решал со скрипом, а остальные были ещё большее г-о потому что я их не решил" - при этом важно чтобы коммент был от авторитетного автора! ;-)

А задачки симпатичные были на мой чайницкий вкус, получил от контеста удовольствие вполне! Автору респект, хоть он и не прочтёт по-русски небось. Many thanks to author!

2hpwrrbm

err.. Excuse me but what is the SRMs by the way? (I'm really sorry if it's inappropriate to ask like this)

Hopefully the newly added link can answer your question :)

aajjbb

I'd like to compete, but its right on my lunch time.

Coder

Damn auto correct
http://www.~~code~~iforces.com

sicasli

I tried to submit a solution for practice in past contest but it was taking so long for judging.. I'm afraid this will happen in contest also.. Any solution for this, admin ?

I think this happens because the server is rebooting before each contest. I may be wrong though.

Alireza

Your problems are usually nice and make the competitors think more rather than just coding. I was eagerly waiting for you to be an author of one the codeforces round. Thank you dolphinigle

alex270295

блин я же вроде зарегистрировался.. по крайней мере нажимал на регистрацию но вероятно инет повис и регистрация не прошла а я контеста час ждал думал что все нормально

можно ли дорегистрироваться как то

istchenko.m

как заблокировать свое решение , чтобы взламывать чужие??? помогите плиз!

нажать на замочек у задачи которой ты хочешь заблокировать на вкладке задачи.

imslavko

я такой дурак: захотел челенжить тем, что у меня не проходит... и после блока :(

почему нельзя себя взломать! Хочу свои заработанные 100 очков :)

CherryTree

И еще подсказал решающим контест, кого взламывать :)

почему-то меня никто не взламывает уже час

riadwaw

но все же так делать не стоит

agul	13 лет назад, # ^ \| 0 Чтобы его взломать, надо хотя бы тест придумать. Самое интересное-то он не написал! → Ответить

Я такой дурак! Мое решение прошло...

daftcoder

Как тонко!

Я не совсем понял, что имелось ввиду, но я действительно очень сильно натупил, когда придумав тест, "прокрутил его в голове на своем коде", подумал что решение не правильное и побежал взламывать этим тестом других, да по-быстрее! Потом я написал комментарий выше и забыл про задачу, даже не проверив свой код нормально. С Вами такого никогда не бывает?

Чуть-чуть капитанства.
Под тонким я имел в виду троллинг. :) Т.е. написать, что задача не верна, а оказалось, что в общем то и совсем верна.

А со мной (можно на ты) такое совсем недавно было.
Я быстро написал задачу, решил залочить и посмотреть что у других. И пока открывал комнату, осознал, что запутался в индексах и моё решение не пройдёт уже очень маленький тест. Систесты то тем более. Я огорчился, что зря рано залочил, но стал писать далее.

Какого же было моё удивление, когда моё неверное решение получило AC! И вот тогда уже я написал на форуме. Но не раньше, не во время контеста.

agul	13 лет назад, # \| 0 In all problems today we should return only one number (both Div1 & Div2) (: → Ответить

Tranvick

Контест отличный, спасибо автору)

Объясните кто-нибудь E div 2/C div 1 пожалуйста

al13n

Можно рассматривать строки и столбцы отдельно. Рассмотрим строки, столбцы рассматриваются так же. Заметим, что в строке в последовательных клеток направление горизонтального участка трубы чередуется, то есть чередуется значение выражения (тип=1 или тип=2). Иными словами, в пределах строки постоянно выражение (тип=1 или тип=2) xor (номер столбца четен). Для каждой строки посмотрим, какие значения этого выражения встречаются. Если оба, ответ 0. Если ни одного, умножаем ответ на 2.

спасибо

Я ничего не понял, но спасибо!

В первой правке понятнее по-моему)

hacker007

Clear statements, useful pictures, and nice problems! I enjoy this match very much. Thanks, dolphinigle .

Sarkin

Great problemset. I'm just wondering about the solution of Div 1 C, that kind of tasks always confuses me.

mkagenius

Could you please see Prob B of DIV 2 .

How to solve DIv2 prob 2. I have no clue whats the best way ?

eduardische

The answer is the number of wolfs, which have at least 1 neighbour pig. Since there is only one step in the task, and a wolf can eat at most one pig, it doesn't matter which to choose, and because no pig has more than one neighbour wolf, there can't be a fight over the same pig between multiple wolves as well.

Ahh.. did not notice that thing and whole time I was thinking , whether by mistake I have opened division 1 problem B.

Great problemset!

Especcialy I like problem C

Hohol

КОСИЛКА НЕ УМЕЕТ ЕЗДИТЬ ВВЕРХ КОСИЛКА НЕ УМЕЕТ ЕЗДИТЬ ВВЕРХ КОСИЛКА НЕ УМЕЕТ ЕЗДИТЬ ВВЕРХ КОСИЛКА НЕ УМЕЕТ ЕЗДИТЬ ВВЕРХ Я ИДИОТ

Trytrytry

ГАЗОНОКОСИЛКА КОСИТ ГАЗОН

agul	13 лет назад, # ^ \| 0 Петросян, да? → Ответить

Jokser

Тут просто продолжение должно быть в стиле "Бригада садовников жрет самогон". :)

Да так оно и есть:)

bytybai

зачем ж так критично по отношению к себе?)подумаешь..всякое ж бывает)

T_T

JKeeJ1e30

Despite the fact that I wrote bad today, this contest seems me really good: there was solved and interesting problem. In my opinion, it would be great to see similar contest every time.

Avalanche

Не могу не привести цитату из "Криминального чтива": English, ****! Do you speak it?!
Но вообще согласен, контест действительно хороший и интересный.

Макс, откуда ты знаешь??? Ты ведь его не писал.

Читал условия, смотрел решения.

На самом деле, часто впечатления от контеста после того, как прочитал условия и решения, сильно отличаются от тех, которые были бы, если бы прочитал условия и после этого 2 часа решал:)

P.S. после публикации сообщения язык поменять никак?.. Жаль.

Безусловно, но не всегда же удается написать тот или иной контест.

pva701

отличные задачи, раунд полностью понравился, ставлю жирный плюс автору!

Belonogov

Задачи были хорошие, понравились.
Но они были не очень хорошо распределены по сложности. В div 1 была большая разница между B и С (((

agul	13 лет назад, # \| 0 Черт, не думал, что в B (Div2) можно накосячить где-то - не блокировал. Смотрю 4 решения в своей комнате - 3 из них можно легко взломать :( Я дурак. → Ответить

PavelKunyavskiy

Я тоже так думал. Но обнаружилось, что большинство идейных багов либо чаще всего парами, которые друг друга компенсируют, либо компенсируют себя сами на другой итерации. В результате решение, уходящее за границы поля оказывается правильным.

iksuy

А сколько посыпалось-то на финальных тестах уже.

Martial

The editorial available right after the match is by itself a reason to call it wonderful.
Nice problems, too.
Kudos to dolphinigle and to the others problem setters!

phantom11

The best thing I liked about the contest was the inages supporting the test cases.Made easier for us to visualize then..Good contest overall:)

desudesudesu

Yep, images were nice and cute :3
But anyways, after I read the problem pictures didn't make much sense to me, because problem text was composed that good.

I liked round, because there were not any longlongs, and output was as easy, as possible - one number.

Liked statements, they were simple, understandable and short. Thanks to writer

Al.Cash

Imo pretests for Div1 D are too weak. Wasn't easy to solve it, and a few seconds before the end I understand that I've missed some special case.

Shuaib

Damn, I didn't know that dolphinigle was going to be the author today. Otherwise I wouldn't have missed it.

ir5	13 лет назад, # \| 0 B: I misread the man in the problem can always flip his direction. C: I misread the top-most side and the bottom-most side are connected. I thought so after seeing the figure in the examples. ...orz → Ответить

tatsuhiro.t

I was comfortable with today's problem set. Thanks to author.

yermak0v

спс за контест

Пишите на английском, автор из Индонезии

Зато сайт из России, так что нас это в какой-то мере извиняет. Большинство иностранных спортсменов уже лихо научились гугл-транслятором просматривать русскоязычные блоги здесь. С русского-то он лучше переводит чем наоборот... %)

good thank for contest

Sandman

а только у меня во время контеста сайт лагал или у всех?

ErzhanDS

Лично у меня ничего не логало :)

Obaida

Many Many Thanks to dolphinigle for such a wonderful problemset :)

"The top three of the Division1 solves all three problems"
didn't you mean five? Topcoder has a very big influence on dolphinigle, I guess. :)

My bad :). Thanks for catching that - fixed.

Yeah I'm used to write summaries to Topcoder's Editorial and that's pretty much the catch-line ;)

Yeah, I guess you wish you could go back in time, like in SRM 492. ;)

← Rev. 4 →

I came across an awkward issue when viewing source code during the contest.The pop-up window had a top-down/vertical scroll bar if needed, but never have a left-to-right/horizontal scroll bar. This brought about a knotty problem that I was NOT able to see those code out of right side of the pop-up window. I tried to view a few submissions and the issue happened all the time, I had to give up hacking. So it is probably a BUG.

Anyone else in the same situation? How to solve it?

Shuai

i agree with u

beyondxgb

Good problemset!I think this contest is organized very well!

Link to test case 12 of D2-D/D1-B, Lawnmower:

http://www.mediafire.com/?v7hdvddcbqnbaqv

oldoldold

Эх жаль такой контест пропустил... совсем с учебой забегался. Задачи понравились, благо есть возможность виртуально контест написать ;D

Egor	13 лет назад, # \| ← Rev. 3 → 0 Well, I think my solution, despite being O(N³), is ok to pass as it is more complex than original (and it can pass in O(N²logN) if I would use FFT to multiply polynoms) :) → Ответить

It's sort of relieving to hear this from a Java coder - my biggest concern was that C++ coders gained significant advantage due to C++'s inherently fast speed. Also the extra effort the coders who had working N^2 solutions (shik, ivan.popelyshev, and (I think) watashi for example).

I'm not going to let this happen again next time :). Though I'm quite happy with how beautiful the passing solutions for current D, it's still pretty evil to ask for that kind of solution.

P.S. To be honest I'm not aware how to solve this problem with polynoms at all :)

Egor	13 лет назад, # ^ \| 0 I post my solution in editorial as comment (with no proof because I did not have one :) ) → Ответить

Cool, thanks! It's in the russian forums by the way

Egor	13 лет назад, # ^ \| 0 Ooops, I thought I double checked to post it in English and still... → Ответить

cherudim

D1--D is a so fantastic problem!!!!

I love it so much! Really elegent! THX

Блог пользователя dolphinigle