Codeforces Beta Round #51

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

+13

хотелось бы знать не только никнеймы авторов, но и их имена и ВУЗ(ы), которые они представляют

ждём интересного контеста :)

→ Ответить

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

yaro с матмеха СПбГУ, инфа 100%

а вот про Rei и бывшего напарника yaro cerealguy я ничего не знаю

→ Ответить

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

+10

Я все-таки думал, что аффтары представятся, а то нам ведь интересно.

→ Ответить

master_j

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

а зачем контесты проводить в первой половине дня? большинство в это время учится. поэтому пропускаю соревнование, а хотелось бы поучаствовать(

→ Ответить

gen	13 лет назад, # ^ \| +4 Для другой половины планеты. → Ответить

diver_ru

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

А если провести в выходной, обе половины планеты будут счастливы :)

→ Ответить

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

← Rev. 2 →

У половины планеты сейчас сессия, так что если сегодня нет экзамена, то вполне есть возможность написать контест.

А у второй половины планеты вечер, так что все в порядке:)

→ Ответить

k-va	13 лет назад, # ^ \| 0 А у третьей половины каникулы закончились и начались занятия в школе... → Ответить

niyaznigmatul

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

у нас три половины?!

→ Ответить

k-va	13 лет назад, # ^ \| +3 Ну, получается так. Если одна половина на сессии, у второй сейчас вечер, то куда остальных девать. → Ответить

ashmelev

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

Да, хотелось бы побольше контестов в выходные, а то из-за работы ничего не успеваю написать.

→ Ответить

astrovsky

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

скажите а как посмотреть на каком тесте меня взломали?

→ Ответить

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

После контеста можно вот тут http://codeforces.com/contest/55/hacks найти себя и нажать на "Успешный взлом". Но там отображаются не все взломы.. кажется только последние, поэтому можешь не найти себя там.

→ Ответить

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

→ Ответить

Snipx

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

+15

Никак. В этом вся и фича :)

→ Ответить

72VanVector_SevNTU

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

В задаче про кексы. Второй игрок в угловых клетках ставит границу лишь на одну сторону угловой клетки или на обе внешние стороны за 1 ход??

→ Ответить

Rei	13 лет назад, # ^ \| 0 Второй игрок за 1 свой ход может заблокировать максимум 1 сторону клетки на границе. Лучше вопросы задавать прямо в контесте, там быстрее ответят. → Ответить

JKeeJ1e30

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

-22

В билайне козлы работают. За 5 минут до начала контеста отрубился нет и только сейчас включился.

→ Ответить

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

эх, мне бы так :) не хочу обратно в синие :D

→ Ответить

JKeeJ1e30

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

А я в желтые хочу но не доберусь никак:)

→ Ответить

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

Столько возможностей для взломов :)

→ Ответить

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

Я ломал B на тесте:
0 1 2 3
+ * +
Ответ = 1 (а многие сортировали операции и сначала умножали)

и C на следующих двух тестах:
1)
9 9 1
5 5
Ответ = YES
2)
11 11 1
6 6
Ответ = NO

→ Ответить

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

почему 1?

сперва 1+2 заменим на 3, получим 0 3 3 + *

потом 3+3 заменим на 6, получим 0 6 *

потом 0*6=0, ответ 0

→ Ответить

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

Порядок операций фиксирован! Читаем условие :)

→ Ответить

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

ну всё равно фраза "сначала умножали" не корректна ;)

→ Ответить

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

Фраза корректна, т.к. некоторые участники действительно предпочитали сначала умножать, а потом складывать (и в этом они были неправы).

→ Ответить

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

хм

то есть они не только неправильно поняли условие задачи, но и неправильно решили неправильно понятую задачу

я правильно понял? =)

→ Ответить

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

Да. Я взломал решение, где пытались сначала умножать, решение, где пытались сначала складывать, решение, где перебирали все варианты расстановки сложения/умножения и решение, где операции были по порядку, но складывать пытались числа побольше, а умножать - поменьше. Итого: 3/4

→ Ответить

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

я никого не ломал по B, но судя по тому, как ты обрисовал ситуацию, я делаю вывод, что авторы хотели дать задачу на умение читать условие и им это удалось

→ Ответить

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

Мне кажется, что задача была просто на реализацию. Тупо написать перебор и загнать. Типа проверялось умение писать переборы (не редко оказывается полезным такое).

Любую задачу можно прочитать неправильно. Наверное, тут было много моментов, где быстрое чтение губило.

→ Ответить

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

Я видел 3-4 абсолютно разных подхода к решению задачи B.

→ Ответить

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

согласен, привычка читать по диагонали имеет свои минусы :)

жаль, что нет статистики: сколько упало по B на систестах, скольких ещё взломали

→ Ответить

niyaznigmatul

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

← Rev. 2 →

у меня такая же ошибка.

Я это понял, только когда два раза неудачно поломал, именно на том тесте, на котором у меня неправильно работает.

→ Ответить

Timus

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

Порядок действий менять нельзя. Т.е. надо сначало сложить, потом уножить, потом сложить.

→ Ответить

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

вопрос снимается :) кто-то условия за 5 лет СП читать так и не научился...

"операции в том порядке, в котором их производил Володя"

→ Ответить

blazerer

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

блин ((( объясни мне почему

9 9 1
5 5
Ответ = YES

так меня и сломал

→ Ответить

blazerer

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

а ...понял ))

→ Ответить

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

-8

Спасибо авторам за контест. Мне задачи не понравились, поэтому и минус много в рейтинге.

→ Ответить

it4.kp

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

Ну тут же не топкодер, почитал задачи, не нравятся - не участвуй.

→ Ответить

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

А я, если честно, думал, что если вошел в турнир, то уже все - дороги назад нет. То есть участие засчитывается если есть хотя бы одна посылка?

→ Ответить

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

да

пока ты читаешь условия, тебя нет в таблице

→ Ответить

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

Блин, тогда есть интересная тактика. Начинаешь с задачи С (так как она зачастую более менее решаемая, а цена одной минуты у нее выше, чем у A и B). Если вообще нет идей, то черт с ним с контестом. Если решил - досдал A и B и уже имеешь преимущество на трех задачах. Надо будет попробовать :)

→ Ответить

Sereja

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

Может кто-нибудь объяснить мне почему в задаче С нужно проверять расстояние в 4 , а не 2 ?

→ Ответить

MBabin

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

Потому что можно добежать до 4 разных углов вдоль границы

→ Ответить

Sereja

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

Я вроде рисовал тесты, и всегда удавалось перекрыть путь если расстояние даже = 3.

→ Ответить

MBabin

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

Нужно Володей подольше побегать вдоль границы (когда он до нее дойдет) и все станет ясно)

→ Ответить

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

Пусть тест
9 9 1
5 5
(т.е. расстояние 4 до всех краев)
Будем двигаться вверх. У нас есть 4 хода, и за эти 4 хода противнику выгодно построить укрепления:
1) во-первых, над точкой (5 1) (мы туда угрозу все равно создадим)
2) во-вторых, слева от (1 1) и справа от (9 1). Если этого не сделать, то из точки (5 1) мы пойдем туда, где заграждения нет, создавая попутно угрозы наверх, а в углу будет двойная угроза.
3) От (1 1) и (9 1) затем пойдем вниз. Т.е. сопернику надо заблокировать еще и снизу от (1 9) и (9 9). Но у него остался только один ход, значит кекс выйдет-таки за пределы стола.

Получается, что надо 5 ходов, чтоб кекс не ушел.

→ Ответить

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

Эх, классные задачи! На третьей взломал 7 решений на тестах 9 9 1 5 5 и 11 11 1 6 6. И во второй два решения. 13-ая комната принесла мне удачу :)

→ Ответить

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

← Rev. 2 →

Да, задачки самое то для взломов.
Я на A взломал парня, который написал if (n < 3 || n == 4), а еще на B пятерых и на C троих указанными выше тестами.
Теперь я желтый *YAHOO*

→ Ответить

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

-41

Всякие синие да зеленые повылазили выше желтых. Я думаю, что авторам есть над чем задуматься в плане формата задач. Задача C это явно задача не для программирования. Тут преимущество получили люди, которые вообще программируют еле как, но зато сумели лучше промоделировать игру про кексы. Задачу D я, почему-то, так и не придумал. А на E и времени не было. Как результат с 1999 падаю далеко вниз и никаких шансов на красный цвет.

→ Ответить

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

← Rev. 2 →

Это была задача в формате TopCoder уровня 450 див1, хорошая задача, я сам по ней получил 2 взлома, но в итоге сдал. Умение подмечать некоторые особенности, не важно где, в играх или в коде, -- хороший навык. Время от времени надо давать такие задачи.

→ Ответить

Gassa

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

Не согласен. Бывают хорошие задачи на алгоритмы, в которых, тем не менее, не нужно кодить. Эта задача — одна из таких.

→ Ответить

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

+20

Замути свой контест и пусть в нем будут только те задачи, которые тебе нравятся.

→ Ответить

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

← Rev. 3 →

Это ты писал, что ооочень понравилась интерактивная задача с NEERC?

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

→ Ответить

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

Не вижу ничего общего между этими двумя задачами. Тем более, совершенно разные форматы соревнований. Одна задача - интерактивная, другая - нет. Вообще не понял, причем тут задача G с NEERC. Даже что написать по этому поводу не знаю.

→ Ответить

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

← Rev. 2 →

+11

Вопрос не в интерактивности.

Объединяет то, что её могли решить также люди не сильно умеющие именно программировать. Там тоже было больше чем половиной задачи - придумать решение. И совсем не сложно закодить.

→ Ответить

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

Кстати, Петр Митричев на разборе неправильное решение привел, если кто помнит :)

→ Ответить

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

Там соревнования командные. Там все равно в любой момент времени, как минимум, два человека не программируют. Времени подумать над задачей предостаточно. И там ACM-система. Тут же все совсем по-другому. Ну и та задача требовала в разы больше программирования, чем эта. Не знаю, сдал ли ты ту задачу. Я сдал обе (C сдал на дорешке, переведя все в 0-индексацию) и знаю, что G с NEERC требовала 15 минут, чтобы ее напрограммировать (у более матерых кодеров могла и меньше требовать). Тут же чтение + иф.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Когда мы с Петей тестово прорешивали полуфинал он, насколько я помню, 2 раза ошибся именно в реализации :) → Ответить

permin

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

+25

Я вообще не часто комментирую, а тем более такие глупости, но сейчас напишу. Мне, как и, я уверен, большинству, кажется, что сложная задача, которую можно решить обходясь маленьким количеством знаний, намного лучше, чем задача, которую можно решить только если знаешь малоизвестный замечательный факт. Конечно, знание фактов облегчает решение задач. Но, например, для пресловутых "кексов" это не верно. Не понимаю, как вообще задача должна разделять участников по цветам? И что такое задача "для программирования"? Распарсить какую-то штуку -- это для программирования? Вот здесь думать в математическом смысле надо меньше, зато нужно продумать получше разбор организовать. Если это задача для программирования, то не думаю, что много кому понравится решать только такие задачи. Почему ты думаешь, что "синие да зеленые" всегда должны оказываться ниже желтых, кажется именно так они и станут желтыми. И авторы, я думаю в этом совершенно не виноваты. Как и в том, что "Задачу D я, почему-то, так и не придумал".

PS. И это просто некрасиво писать фразы типа "Всякие синие да зеленые повылазили выше желтых".

→ Ответить

gen	13 лет назад, # ^ \| +19 Ты так говоришь "синие да зелёные", как будто это что-то плохое. → Ответить

JKeeJ1e30

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

В этом тебе некого винить кроме себя. Мне тоже многие контесты не нравятся, и я даже иногда ворчу что плохо написал-но не ругаю автора. Мне, наоборот, очень не нравятся контесты, где главное-уметь быстро и четко написать код длиной 200-300 строк, потому что я пишу медленно и сажаю много багов. Но в этом не могу винить никого, кроме себя. Да и вообще, как ты предлагаешь математикам, которые есть в каждой команде, тренироваться? Почему каждая задача должна быть задачей "для программирования"? Да и вообще, если бы каждая задача была "для программирования", участвовать в АСМ было бы бесполезно и скучно

→ Ответить

72VanVector_SevNTU

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

Мне кажется, задача С была легче чем B.

→ Ответить

e-maxx

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

+13

Тут уж кому как - мне, например, C далась труднее, чем Е :)

→ Ответить

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

-29

Для синих и зеленых такие задачи C просто подарок. Там не надо уметь особо программировать. Надо посидеть и спокойно поэмулировать на листочке и найти тактику оптимальную. Тут все цвета уравниваются по своим шансам. По идее такие задачи C - не есть хорошо. Однако такое встречается уже не в первый раз, видимо специально, чтобы цвета почаще менялись.

→ Ответить

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

А что тебе мешало так же сесть и проэмулировать?

→ Ответить

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

-9

Проэмулировал неправильно.

→ Ответить

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

Все-таки поправка... на дорешке выяснил, что мое решение было правильным. Забыл перевести при чтении координаты в 0-индексацию.

→ Ответить

Sereja

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

Ну тут такая задача... Я "эмулировал" полтора часа и не мог понять почему ВА на тесте 6. Но до сих пор не могу понять почему такое решение(которое берет АС) правильное.

→ Ответить

PavelKunyavskiy

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

Доказать легко.

1. Заметим, что произойдет если мы сделаем ход на границу.

Если уже во всех 4 углах одна из сторон закрыта, то в любой момент времени нам могут помешать выйти, поэтому мы проиграли. Иначе идем по границе до угла, времени закрыть его у соперника нет, поэтому дойдя до него мы выйдем в один из концов.

Таким образом сопернику нужно 4 хода чтобы нам помешать выиграть, потому нам надо проверить есть они у него или нет.

→ Ответить

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

очень коротко и очень понятно, спасибо

→ Ответить

Gassa

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

+25

Какие-то странные у тебя представления о том, что должны означать цвета. То постить зелёным нельзя. То зелёные — это те, кто умеет решать, но не умеет кодить.

А мне вот кажется, что coding competitions — это скорее Development ветка на ТопКодере. А algorithm competitions — это всё-таки в том числе и придумывание решения, а не только его реализация. И хорошо, что на CodeForces не только первое, но и второе.

→ Ответить

Ferlon

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

+12

Ну так не каждая же задача должна разделять шансы по цветам. Ты давай ещё поругайся на задачи с полуфиналов или из TopCoder, где надо спокойно подумать-порисовать и немного закодить.
Кстати, почему это обязательно те, у кого выше рейтинг, должны лучше только кодить? Они должны лучше выступать по совокупности, то есть и думать в том числе лучше - чётче и быстрее.

→ Ответить

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

Отличные задачи. Спасибо авторам.

Особенно порадовала задача D, давно не испытывал такого удовольствия от решения задачи. Интересная динамика, хитрое уменьшение состояний. В общем задача -- "конфетка".

PS Спасибо двум людям, которые взломали мое незаблокированное решение по задаче C ;)

→ Ответить

permin

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

Да пожалуйста)

→ Ответить

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

Ага :)

→ Ответить

mkagenius

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

+56 and still blue :) again all due to rng_58 and thanx for participating today rng_58. Today again I will learn from codes. :D

→ Ответить

Kenny_HORROR

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

Thanks for a contest. Problem D is pretty good =).

→ Ответить

fushar

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

Problem C is very interesting. I got the correct idea in almost one and half an hour, but mistakenly typed coord <= 4 instead of coord <= 5, then got challenged =)

→ Ответить

dj3500

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

Same here! But luckily I didn't lock the problem, so I could resubmit and lose only ~400 points as opposed to ~1200 ;)

→ Ответить

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

Объясните, пожалуйста, как ещё можно уменьшить состояния в задаче D. У меня такие состояния: i, mask, mod9, mod8, mod7, bit5, less (думаю, комментировать состояния не надо)

→ Ответить

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

← Rev. 3 →

у меня состояния toSet, mask, mod9, mod8, mod7, mod5, less

toSet -- сколько разрядов осталось еще поставить. mask принимает значения до 2^8 (0 мы не учитываем, а на 1 число всегда делится). Насчет последнего параметра (less). Как я понимаю он означает нужно ли нам ограничиться каким то значением разряда или нет (дабы не вылезти за обрабатываемое число). Результат ДП нужно запоминать только если он равен нулю, в случае единицы такое состояние будет вызываться только 1 раз и запоминать его не имеет практической ценности.

→ Ответить

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

Эм... Вообще-то динамика такая же. Только у меня bit5 - 1 или 0: на конце 5\0 или нет. Сложность такая же. Надо поменять местами маску и i, тогда наверное побыстрее будет..

→ Ответить

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

Блин... Вот мне не хватило этой идеи про bit5. Спасибо, хорошая идея. Почему же мне такое в голову не пришло на контесте.

→ Ответить

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

Она у меня появилось, когда МЛ получил. Правда, мне это пока не помогает..

→ Ответить

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

Возможно ТЛ из-за того, что параметров для вызова функции много. На сколько я знаю это все дело кидается в стэк, и может повлиять на время. Я для модулей реализовал структурку с массивом где хранились модули.

→ Ответить

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

можно было сжать маску как в решении yaro... эх, черт.

→ Ответить

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

← Rev. 3 →

еще вот

LL dp[...][...][9][8][7][2][3];

попробуй заменить на

LL dp[...][...][9*8*7*2*3];

и при работе с запоминанием параметры умножать на соответствуеющее число.

UPD

Еще оказывается можно массивчик с запомненными параметрами не обнулять (если не использовать в запоминании параметр less так как описано выше ) :)

→ Ответить

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

Да, уже пробовал. Думаю дело именно в том, что маска не сжата. Работает очень долго на макстесте

→ Ответить

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

Я сейчас уже ничего не обнуляю xD. Чуть больше памяти скушал, просто бит меняю каждый раз на противоположный (посчитали мы значение динамики или нет)

→ Ответить

-dp-	13 лет назад, # \| +4 Привет всем! Таки добрался я до этого сайта и не пожалел. Еще бы если контест почти на час не проспал =) У меня два вопроса осталось... 1. Как в А доказать что это УЕС только на степенях двойки? 2. Можно ли посмотреть чужие решения после окончания и как? → Ответить

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

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

Первый вопрос поддерживаю! Интересно, что это за доказательство.

→ Ответить

-dp-	13 лет назад, # ^ \| 0 Во время контеста это работало, а сейчас показывает только историю, а вкладки "код" нету =( → Ответить

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

+13

Там в истории напротив почти каждой строчки номер-ссылка. Нажимаем на нее и дивимся :)

→ Ответить

-dp-	13 лет назад, # ^ \| 0 Нашел, спасибо! → Ответить

unrated

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

В истории рядом с вердиктом стоит ссылка с номером посылки. Это и есть ссылка на решение.

→ Ответить

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

Что касается задачи A:

Можно доказать динамикой (как, собственно, и решить). Для каждого состояния два параметра номер текущей позиции и величина шага по модулю N. Ну и, соответственно, всего получается N * N состояний. Чтобы не париться, можно понять, что больше N * N шагов не потребуется. Я пошел дальше - просто запускал 10 миллионов шагов.

→ Ответить

Egor	13 лет назад, # ^ \| ← Rev. 2 → 0 Легко доказать что через 2N шагов все зациклится → Ответить

-dp-	13 лет назад, # ^ \| +3 Не, это я тоже так решил дабы времени не тратить. Но по факту получилось что степени двойки, и написать через степени было бы чуть быстрее. По этому интересно как бы это просто доказать. → Ответить

Egor

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

Легко можно доказать необходимость

Рассмотрим любой нечетный делитель p > 1 и посмотрим что будет творится по его модулю. Во-первых, через p шагов мы снова попадем в 0 по нему - следовательно, если мы в какой-то остаток не попадем за p шагов, мы туда не попадем никогда. Но через p - 1 шаг мы тоже будем в 0 - значит по принципу Дирихле какой-то остаток мы потеряем

→ Ответить

Egor

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

Достаточность - докажем по индукции

База очевидна. Теперь докажем 2ⁿ -> 2^n + 1

Пусть N = 2^n + 1. Рассмотрим первые 2^n + 1 шагов. Мы начнем с точки 0 посетим все возможные остатки по модулю 2ⁿ (предположение индукции) и окажемся в точке 2ⁿ. Мы из каждой пары (a, a + 2ⁿ) за это время посетили хотя бы 1 элемент - пусть на i-м шаге. Тогда на i + 2^n + 1 шагу мы посетим второе из этих чисел. Ч.т.д.

→ Ответить

-dp-	13 лет назад, # ^ \| 0 Да, спасибо, похоже на правду. Хотя, конечно, не самое просто доказательство чтоб его в уме можно было быстренько прикинуть =( → Ответить

Egor	13 лет назад, # ^ \| 0 Наверняка боян с какой-нибудь мат. олимпиады Наверняка я его уже решал, но сто лет как забыл → Ответить

mkagenius

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

← Rev. 2 →

In problem C , almost everyone wrote same 2 line solution.

Alas, I did not give it a try.(the idea could have struck me too :( )

→ Ответить

cgy4ever

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

C is really interesting.

Firstly I thought it should be coord <= 2.

But it shows WA.

After thinking more , I realized that it should be coord <= 4.

As for problem D:

The time limit is quite strict for my solution.

My solution got TLE, but when I change the language to MS C++ , I got Accepted.

→ Ответить

littlealex

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

How long will take the analysis to be posted? (just by curiosity)

By the way, excelent contest, nice problems.

→ Ответить

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

Кстати, процент финального тестирования стоило разместить на более видном месте и сделать его автообновляющимся и, наверное, более точным.

→ Ответить

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

О_о а где он был?

→ Ответить