Всем привет!
Сегодня состоится второй раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд для вас готовили: sdya, Seyaua, Gerald и, как обычно, задачи на английский переводила Delinur.
Приятная новость для тех, кто не попал в лучшие 400 участников в предыдущем раунде — сегодня каждый может поучаствовать вне конкурса. При этом, раунд будет рейтинговым как для официальных участников чемпионата, так и для внеконкурсных.
Официальным участникам напоминаем, что:
- Все участники чемпионата должны быть не моложе 18 лет на момент регистрации
- Финал чемпионата состоится 16 и 17 мая в Москве в офисе компании КРОК (50 участников)
- Проживание во время финала будет оплачено компанией КРОК
- Для граждан Российской Федерации: организаторы покроют транспортные расходы по территории РФ, транспортные расходы не по территории РФ — по согласованию (возможно, частично)
- Финалисты должны подтвердить свое участие до 2 мая
И небольшой бонус: лучшие 200 официальных участников чемпионата получат футболки!
Желаем всем получить удовольствие от решения задач ну и, конечно, удачи!
UPD: Разбалловка по задачам сегодня будет немножко отличаться от стандартной: 500-1500-1500-2000-2500 для первого дивизиона и 500-1000-1500-2500-2500 для второго.
UPD2: Мы приносим свои извинения за технические неполадки во время раунда. Посовещавшись, мы решили, что соревнование должно быть рейтинговым. А результаты соревнования будут учитываться в отборе на финал чемпионата КРОК.
А на какой раунд регистрироваться официальным участникам чемпионата из Div. 2?
Очевидно, на официальный.
Очевидно, вопрос задан не просто так. "Рейтинг должен быть от 1,700 до 9,999 для возможности регистрации на это соревнование"
Здесь был глупый вопрос.
Так бы и написали.
В официальный. Сейчас регистрация на него открыта для всех прошедших.
А на аватарках у sdya и Seyaua кто — sdya или Seyaua?
А вдруг это и не sdya, и не Seyaua :)
Аватарки одинаковые и судя по всему это Женя)
Я уверен, что Женя.)
I'm assuming div2 people who qualified to Round 2 should participate in the non-Div2 round?
In last 3 raunds I've lost 204 points of rating, may I find some luck in this contest ))))
It's good that there is division 2 too
It's good news that participants from div 2 can participate in this contest ))))
I pray for irakli_p to increase his rating this time.
thanks )))
"A little bonus: top 200 official Championship contestants will receive t-shirts!" why only official ? give top 200 contestants from both official and unofficial.
http://i1.kym-cdn.com/photos/images/original/000/210/119/+_2acc5a8841f8752904d37f90a8014829.png
Я зарегистрировался на контест. Но в разделе соревнование вместо зелёной надписи "зарегистрирован", красная надпись предлагает "зарегистрироваться". Видимо это ненормально.
В див2 будут такие же задачи?
Скорее первые 3 задачи с Div.1 будут совпадать с последними тремя задачами Div.2, по крайней мере в прошлом году было так :)
Думаю задачи будут одинаковые, но ограничения разные.
Баг: я зарегистрировался на контест вне конкурса, но красная кнопка "Зарегистрироваться" у меня не пропала.
Почему по ссылке "КРОК-2013" открывается блог из двух постов? Почему туда не добавили посты о первом и втором отборочных раундах?
Ну я как всегда опоздал на регистрацию на целую минуту.
У меня одного КФ глючил?))))
Наверняка только у тебя. И контест на 10 минут только у тебя продлили.
нет, у всех, особенно первые 7 минут
КРУТОЙ РАУНД. Спасибо авторам!
Спасибо за красивые задачи, очень понравились. К сожалению, они мне оказались не под силу :'(
F5 power
Как решать B, C?
Upd: у меня в B работал перебор за 3 секунды для теста
5 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Насколько я понимаю, это макс. тест. Мне это должно намекать на то, что я его чуть-чуть недооптимизировал или то, что ограничения подобраны настолько хорошо, что перебор не проходит? :)
UpdUpd: уже объяснили, что я не прав.
В C задача сводится к решению уравнения 3(a + b)(a + c)(b + c) = n в целых числах. Можно решить перебрав первый множитель за
UPD: Ну если n не делится на 3, то решения сразу нет)
Вот как это можно было заметить, не прибегая к wolframalpha и прочим читерствам? Я минут 30 на бумаге думал, пока наконец не сдался и не пошёл в wolframaplha...
Ну я, например, на бумажке раскладывал. Применяешь формулу суммы кубов к a3 + b3 и разности кубов к (a + b + c)3 - c3, а дальше (a + b) выносится и там уже просто.
Участвовать в школе в олимпиадах по математике :P
Там это заучивается на уровне подкорки, что и через 10 лет на автомате раскладываешь такое на множители в уме.
Я участвовал в школьных олимпиадах по математике :) Значит, либо фигово участвовал, либо в России олимпиады какие-то другие, либо моя подкорка умеет забывать за 7 лет.
Я участвовал, но на контесте пришлось заново придумать =)
Ну, я, судя по-всему, уже видел это разложение, потому что оно у меня сразу написалось на бумажке. А так — ну, скорее всего надо на множители разложить. Так, у нас общий делитель 3 — выносим. Так, у нас сумма коэфициентов 8 — значит, 2 * 2 * 2. Ну а симметричных 2 * 2 * 2 не очень много
Я вот как-то заметил. С помощью простого текстового редактора. Без WolframAlpha и даже без бумажки.
Ну я прекрасно понимаю, что есть полно людей, которым ещё и не такое очевидно :) Просто посдавали задачу на порядок больше, чем можно было бы ожидать, если бы её сдали только такие повелители.
Ну в мат. центре спб такое детям в 8 классе объясняют (то есть чуть ли не самый боянистый симметрический полином). Например, на идею подставить a=-b и увидеть ноль (делимость на (a+b)).
А еще есть хорошая (не самая простая) задачка: докажите, что (a + b + c)333 - a333 - b333 - c333 делится на 3(a + b)(b + c)(a + c) (для натуральных a, b, c).
в кольцо многочленов по модулю простых множителей очевидно, по модулю 3 цэшки все поделятся
ignore it
удалила дубль.
Можно в лоб раскрыть (a + b + c)3, после множества сокращений, вынося степени C, получаем 3 * (a + b) * (c2 + (a + b) * c + a * b) = n. Ещё один шаг и получаем искомую формулу. Хотя задачу я все равно сдать не успел.
Если попробовать составить квадратное уравнение относительно a, это сразу получится.
Я делал так (на бумажке). Если раскрыть скобки, у нас останется 24 слагаемых (27 минус a3, b3 и c3). Вынесем множитель 3, осталось 8 слагаемых. Теперь предположим, что многочлен третьей степени факторизуется, и при раскрытии скобок этой факторизации ничего не сокращается. Тогда сколько должно быть скобок и сколько слагаемых в каждой скобке? Довольно логично попробовать 8 = 2·2·2, то есть три скобки по два слагаемых. В силу симметрии остаётся проверить один вариант, он подходит.
Да, под восемью слагаемыми я имею в виду a2b + ab2 + b2c + bc2 + c2a + ca2 + 2abc: последнее, естественно, с учётом кратности.
По С превращаем Вот так, далее вроде бы должен работать перебор, если достаточно хорошо его пообрезать со всех сторон. Я перебирал значение первой скобки (понятно, что это делитель n/3, и не больше корня кубического из n/3), и внутри — значение а и b. Если зафиксировать а и b, и перейти к t=n/(a+b)/3, то получим (a+c)*(b+c)=t;
Тут делаем еще одну замену, x=a+c; получаем квадратное уравнение x*(x+b-a)=t;
Дальше вроде бы очевидно.
Не ясно, вы перебираете сначала a+b, потом a, т.е. (10^14/3)^2/3 , что кажется никуда не влазит( или как?
Не каждое значение a + b будет делителем
I_love_Tanya_Romanova, вижу, вас можно поздравить с красным!
Спасибо.
В задаче B динамика с использованием бит-масок, если я конечно не ошибаюсь.
DP[номер текущей строки][номер текущего столбца][маска уже имеющихся цветов]
А переходы откуда? В смысле, из каких состояний?
Перебираем каждую маску и цвета(если текущая клетка не закрашена), если цвета в наборе нет:
DP[i+1][j][curmask + 1<<color] += DP[i][j][curmask];
DP[i][j+1][curmask + 1<<color] += DP[i][j][curmask];
Ну и в конце надо перебрать все возможные маски и цвета клетки n,m и если цвета в маске нет — добавляем DP[n][m][mask] в ответ.
Я это мгновенно закодил на контесте. К сожалению, такое решение неверно. Хотя бы на таком тесте:
Получается, что
dp[0][1][{1,2}] == 1dp[1][0][{1,2}] == 1Но
dp[1][1][{1,2,3}]не равно сумме тех двух значений.Так мы посчитаем число раскрашенных путей, а не раскрасок
По ML и TL не пройдет
k = 10, при таблице n+m-1 > k — ответ 0.
Память в "худшем" случае занимает 5*6*1024 * 8 байт (используя long long).
Извиняюсь :)
У меня мгновенно работает на этом тесте что-то такое:
поставим в первую строку и последний столбец числа 1, 2, ..., (n+m-1) Если у нас там были какие-то цвета, то переназначим их. Дальше будем перебирать отсекаясь, если табличка стала неправильной. Для финальной таблички посмотрим, сколько способов переставить цвета.
Я написал такую динамику [x, y, mask] — где стоим и маска 610. Маска означает для каждого цвета минимальный номер строки где этот цвет присутствует. Но это медленно. Дальше я сделал хак, что все цвета не лежащие на поле одинаковы, поэтому можно перебирать только нормализованные наборы и потом домножать на коэффициент. На твоем тесте это даже с mapом работает очень быстро, но если в последнем столбце подобавлять числа, то опять медленно. Nerevar сказал, что он делал то же самое но каким-то образом смог нормализовывать не только числа которых нет в таблице но и все остальные. И это вроде уже быстро работает. Странная задача B, если это ее авторское решение.
У меня очень похоже, только я в качестве оптимизации фиксировал цвета начальной и конечной точки
Я написал такую же динамику, но работала она долго. После долгой медитации придумал такую оптимизацию: все цвета, которые уже не встретятся после текущей позиции, мы сортируем в нашей маске. А для всех цветов, которые встретятся, находим номер самого левого столбца и учитываем его, когда пытаемся поставить этот цвет. С этим отсечением динамика зашла за 15мс.
в B у тебя решение быстрее чем за O(ответ)? для теста
4 4 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ответ (если не брать по модулю, и я нигде не набагал) = 31391539200
У меня на этом тесте вроде такой же ответ
Интересно:) Нет не быстрее, просто я глупый и не подумал, что 5 6 — не макс. тест.
В B отлично заходит перебор, надо только его в k! раз соптимизить. А именно, определим операцию "канонизации" раскраски так: возьмём все цвета, которых не было во входных данных, выпишем поле по строкам и посортим цвета в поряде появления там (т.е. например, если поле начинается как 3989, а неиспользованные цвета все, это превращается в 1232). Посчитаем количество таких полей перебором, для каждого прибавим к ответу количество полей в его классе эквивалентности. Если начальное поле относительно пусто, то это оптимизация в ! раз, а иначе даже тупой перебор быстро работает, т.к. ответ небольшой.
Upd.: как пишут ниже, это убивается тестом с полем 5x6, у которого часть клеток снизу слева зафиксированы. Так что решение лажа, странно, что оно зашло.
У меня похожий перебор: если пытаюсь раскрасить клетку в цвет, которого еще на поле не стоит — запускаю перебор дальше, и запоминаю ответ. Когда начинаю пытаться покрасить эту же клетку в другой цвет которого так же нет — перебор уже не запускаю, а просто вспоминаю уже подсчитанное значение.
Эта оптимизация довольно легко прикручивается к самому тупому перебору.
Эммм, не вводите народ в заблуждение недоказанными решениями: (в данном случае, опять слабые систесты). Ваш перебор на таком тесте, допустим, получает заслуженный Time Limit.
На самом деле, я сначала тоже так написал, а потом пришлось ресабмитнуть нормальное решение. Нормальное следующее: нужно встречающиеся цвета, которые уже есть в табличке, сопоставлять цветам шаблона, который перебираем. Так уже очевидно, что дольше всего работает на пустых таблицах. Ну или еще глупее: генерировать цветовые шаблоны для пустой таблицы, а потом уже сопоставлять с исходной, частично заполненной.
А вот на таком тесте падает несколько случайно взятых сданных решений.
Эх, и люди пишут лажу, и авторы ее не отсекают.
То, что люди пишут лажу это нормально. Обычно на контесте нет времени доказывать количество операций в переборе с отсечениями. А макс тест не очевиден.
Но насчет слабых систестов согласен. Видимо у авторов не так много фантазии на разные неправильные решения. В отличие от 2к участников.
Да, конечно. В переборе с отсечениями — это нормально (я и сам подобный перебор отправил, пока головой не подумал). Но что забавно: это именно та лажа, которая с большой долей вероятности может прийти в голову (что подтверждает как раз 3-4 TL из Top-50 на этом тесте). То есть я никого не виню, мне, скорее, наоборот интересно, было ли у авторов такое решение.
Ага, верно, на этом тесте (и на указанном ниже) ТЛ (не успевает, правда, всего в константу раз ~2; учитывая, что это джава и bottleneck — обращение к 3хмерным массивам, такое решение на C++ этим уже не убьёшь). А вы пробовали на контесте кого-нибудь челленджить? Если бы авторы добавили такой челлендж к систестам — результаты бы сильно поменялись.
Вспоминая пост про недоказанные решения — я видимо начал входить во вкус загона фигни. Второй день подряд заходит правдоподобная лажа по довольно сложной задаче =) < trololo > Так вот он, секрет успеха на контестах </ trololo >
Илья, на плюсах — да, этот тест проходят, а вот второй уже нет (уверен, можно и еще убойнее придумать). А загон фигни — это, несомненно, весело и приятно, особенно на ACM-style контестах.
Кстати, я ни разу на встречал обсуждений про неправильные решения на TC (подскажите, случалось ведь и там такое?)
Ну моё java-решение на 2ом тесте локально работает 3.9с, а учитывая, что bottleneck в обращении can[x][y][z] (которое на джаве работает раза в 3-4 медленнее, чем на плюсах), — должно зайти; ну и понятно, что в константу раз там очень много что можно соптимизить, так что все такие решения не убьёшь.
Я сходу не могу вспомнить ни одного случая прошедшего challengeable решения на топкодере (впрочем, там бывают задачи, где вход генерится псевдорандомной последовательностью, и совершенно непонятно, можно ли сгенерить что-то, близкое к худшему случаю). Возможно, это связано с тем, что челленджи добавляются к систестам.
Мне с некоторых пор ссыкотно на cf челленджить по TL (если там конечно не n2 при n = 105). Смотришь, 10^9 операций. Ан нет, огребаешь -50. Сервера то реактивные.
Да ладно, реактивные? Я часто сталкивался с проблемой, когда решение на CF-серверах работает раза в полтора дольше, чем локально. Впрочем, может там только процессор реактивный, но не память. Или кеш мелкий. Кстати, где-нибудь написана конфигурация тестирующих машинок?
Я имел ввиду реактивные по сравнению с другими onlinejudge. Хотя может это просто субъективное ощущение.
Насколько я помню на opencup обычно не заходят решения за 10^8 а тут это в порядке вещей.
Субъективно на топкодере решения работают даже быстрее, чем локально. На OpenCup с некоторых пор обновили сервера, теперь там тоже всё быстро.
Очень странно, на ТС у меня обычно работает дольше (не считал на сколько) а на КФ почти в полтора раза быстрее))
Я правильно понимаю, что у всех периодически на некоторое время кф переставал работать? (в начале контеста особенно) Из-за этих проблем я получил где-то -20 баллов по A, тк вынужден был минут 5-10 ждать, когда система заработает, чтобы отправить решение...
А в условиях того, что B и C сдали немного человек, это дало мне +40 мест. Отлично
Да, почти все логично с подсчетом потерянных 40 мест. За исключением того факта, что у других точно так же периодически не работал СF и они точно так же потеряли примерно те же очки.
Прикол в том, что те, кто отправил решение на x минут раньше меня, получили отрыв не в 2x баллов, а в 2x+20 баллов(что в данном контесте существенно). И естественно, я не единственный участник с похожей проблемой
I think, this contest should not be rated, due to the network problem.
When the contest first opened on my pc, many people had already submitted the first problem
yeah... so i think this contest should not be rated...
If they said it's going to be rated, it will be rated. End of story :)
All contests are intended to be rated, but sometimes things go wrong and in these cases, the best to do is to not validate the contest.
difference between over 160 contestants is for submission time for problem A and due to the network problem many contestants read the problem A after 10 minutes. so i think the contest should be unrated.
The same happened here.
I agree. For over 200 contestants the difference between them is set by the submission time for A, which today was related more to luck and F5ing skill rather than coding.
The main argument for making round unrated are network problems and late submissions of problem A. But is it normal solving only the simplest problem A and making all the contest result depending on first few minutes in which one sends it? Something is wrong with competitors not solving anything else. Sorry that I write that, being myself far from a strong participant.
No guys, the result of a soccer game is not changed after the game finished because the referee gave a wrong penalty to one of the teams. If they have said "it's going to be rated if and only if we won't have network problems", then fine, but in our case it should be rated :).
Programming contest is not a soccer game. People watch soccer game mostly for fun then for competitive. But here we want a fair contest first. And the network problem is hard to realize during the contest about how serious it was.
Why do you have to take it that serious? Come on guys, it is not even a Final round or something similar. Of course we all don't want these issues to happen, but when it does, just deal with it in a positive way. Make your life and others' easier.
Indeed, but they don't start the match until everyone's on the field, do they? :)
What is the solution for E? (div1 C)
А почему не получается посмотреть чужие решения?
нельзя до конца тестирования
Hard Contest.... Very Hard Contest! :)
Три задачи в контестах 293 и 299 совпдают. Контест 299 начался на 5 минут раньше. Контест 293 был перенесен на 10 минут позднее (на 19:40 MSK), а потом на 5 минут ранее (на 19:35 MSK) (я опоздал на 2 минуты в итоге). Вопрос в следующем — что за абсурд, и будет ли отборочный раунд отменен?
Да, к сожалению, сложности были. Честно говоря, какая-то магия — Codeforces существенно не менялся несколько последних раундов, и таких сложностей не бывало. Будем разбираться, что была за проблема. Мы считаем, что на таком проблемсете (довольно сложном) 3 минуты в доступе к задачам не нарушают существенным образом релевантность результатов. Приношу извинения за неудобства.
Лагает и лагает, с кем не бывает, дело то не в этом. Я хотел обратить внимание на странные действия людей, которые переносили раунды. Почему был перенесен только один из двух связанных раундов (с пересекающимися задачами)? Почему раунд был перенесен сначала вперед, а потом назад? Это не сложности с сервером. :)
Писал чуть ниже. Так как были проблемы со стартом, то решил перенести вперед раунд, чтобы все спокойно стартануть. Забыв про div 2, перенес только основной раунд на 10 минут. Потом увидели, что div 2 уже идет, а до начала основного довольно много времени. Что делать? Ждать было нельзя, так как кол-во людей в неравных условиях заметно бы возросло. Перенес основной раунд, чтобы он стартанул в 35 минут. В результате, к сожалению, около 3х минут могли получить преимущество те, кто зашел в div 2.
Ух ты. Повод добавить в админку codeforces проверку на случай переноса связанных контестов. :)
По-моему, релевантность очень неплохо была нарушена, особенно если учесть не три минуты разницы, а все 8 — некоторые успели увидеть таймер, который обещал начало соревнования в 19:40. Разница в 16 баллов между задачей A, сданной в 0:13 и 0:21, это разница в 93 места (между 154-м и 247-м). Ну и сверху таблицы тоже, наверно, задержка сильно повлияла, если учесть, что там эти 16 баллов надо еще помножить на количество сданных задач.
in div2 problems I think there is no tricky cases , how could many contestants make successful hacking ???
I viewed all solutions in my room (room 3) but I couldn't find a wrong solution, even there was no successful hacking attempt in my room.
I made two hacks, there was O(N^2) solutions for A in my room
I think you are lucky :) congratulations for your hacks
my solution also hacked.. i dono whats wrong :(
I also couldn't find a solution that can be hacked...That's my first time to attempt hacking.It is a little interesting.
there was a lot of TLE solutions for problem div2 B. but it did'nt allow to make such a big test. why?
I think you should use test generator
how should I use that?
in my room some contestants wrote gcd solution for problem A, but didn't check that gcd exists in input array
nice to meet you. and thanks for the hack )))
Then how these codes pass sample test?
because if gcd==1, then the answer is -1.
I hacked two codes for the problem C with this input: 3 000000 100000 And same than previously said: O(N²) solutions
Может кто-нибудь ответить на мой вопрос по третьей задаче?
Я весь контест писал В. И задачу не написал, и над остальными не подумал, и раунд слил. День удался.
Точно так же у меня, надо было на С подумать :(
Плюс один. Еще я минут пять искал подвох в див2.А, потому что она показалась мне какой-то подозрительно простой. Потом написал ее, попробовал отослать и только тут понял, что решаю не то.
Аналогично. А открыл я его по той причине, что до начала турнира Div2 показывался во второй строке, а после начала — на первой.
Как я тебя понимаю :)
Жесть контест. Задачи гробы, сервак весь контест лежит, а вначале я ещё и не в тот див зашёл и задачи не те решал, ибо кликнул на первый контест по списку, а он магическим образом оказался див2, а не див1, как это было ещё до контеста.
P.S.1. У меня еле-еле сервак дал посмотреть задачи вначале, потом еле-еле дал отправить решение по А, итого из первых минут 40 мне удалось загрузить страниц 5, остальные так и не были загружены. Только потом тоже периодически сервак висел. Я думал после таких лагов контесты отменяют...
P.S.2. А задачи хороши. В C был близок к решению, но увы..
Та же фигня с див2-див1. Открыл условие, удивился, что в pdf, написал задачу, хотел отправить, замечаю, что див2.
А как их можно было открыть, если они только в div2 были? Когда codeforces стал хоть что-то вразумительное показывать, div1-контест был уже отложен на 10 минут, и смотреть условия задач в div2 в этом случае было несколько неспортивно :)
Я кликнул "войти" у первого контеста. А это оказался div2.
Красные шутят :)
Забавно, первые десять-пятнадцать минут неофициальные участники не могли отсылать решения.
Imho, this contest was one of the worst-balanced contests i have ever seen. A is too easy(comparing to other problems), C is easier than B (but their costs are same), and both B and C are too difficult for >80% of participants...
I don't mind writing such a contest as usual round, but it's very bad idea to give it as qualification round
I think the idea is that, if you want to qualify, you should be able to do some really hard problems..
Задачи контеста div. 2 были не особо сложными. Я ожидал на порядок выше по сложности задачи.
Но ведь Вы же даже С не решили?
А в Б заходил перебор с тем, что мы заполним один из путей цифрами 1, 2, ..., (n+m-1)? А потом будем отсекаться по корректности поля.
Problem D,E is too difficult for Div.2...
E is not as hard as could be.
I am happy, my C (div 2) solution passed the tricky 6th pretest!!!
But you know. admit you know. it's gonna fail on systest.
I don't know. By the way, I only said that my solution passed this pretest. lol, I got AC!!!
congrats xD.
when will system test begin ?
when will system test begin ?
what about system test ?
it seems there is no one to run it :D.
Admins are busy in the discussion of "whether contest should be rated or not"...:D
Plz the contest should be rated . It is my career best rank . I do not want to lose the increment in rating .
Why it's still pending system testing?
Всем добра!
Codeforces is really getting worse a contest after the other! The contest was a real pain! Every 5 minutes the site goes down, also the system test takes too much time to begin..
THIS IS CODEFORCES! A long time ago, it was always like today's contest. :)
so experienced but green.
I sometimes go to div1, but I love div2!
If you view his profile you will notice that he is an old contestant!
When is system test bigin ?I hope it bigin soon today!
Что за бред? Почему у людей которые сдавали задачу А на делфи не проходит 43 тест по времени?
Потому что в дельфи хреново читаются строчки
У меня TL43, и это нерандомизированный qsort (да, я знаю, что я извращенец, что там нет никакого qsort).
это особая кодерная магия)
Осталось найти 7 читеров или не желающих ехать на онсайт — и день удался.
Я в том году прошел на онсайт со 165 места среди официальных участников (в онсайте было так же 50 мест). Так что у вас все шансы. =)
В прошлом году вроде не оплачивали проезд. И отношение к турниру у многих было наплевательское. Там с 200-какого-то места проходили.
классная С — не забудь о вольфраме.
начать див2 на 5 минут раньше и спалить АБС див1 — вот это тру.
весь контест сервер лагал — не не, codeforces не бета.
Почему нельзя посмотреть решения других участников ?
Was in top20. My best result. But then my solution of C failed. And this is the reason.
Fail...
S — F == 1 is draw when you don't have '1s' in the same position. Well, here is my solution.
nice!!!
Дорешивания нет.
we i can't see other solution ?
Sorry, I mistakenly post the comment in russian.
I really don't think this contest should be rated.
Yes, I'd like that too. But unfortunately, we all had the same chances. Some of us did really bad (I'm pretty sure Petr would like the contest to be unrated too :)).
I'm surprised at how many red coders ranked really low. The contest difficult was high and strange. I tried problem A, got WA on Pretest 6, then moved on to problem B and got stuck there. With only 15 minutes remaining, I moved back to A, fixed a few things and got it accepted near the time limit.
Horrible performance for me this time...
I saw the problems 10 minutes after the contest begins.And then tried A and got WA,a few minutes later passed it.And then stuck on B for about one hour,then I move to C,and complete the code just after the end.I'm said.
IMO decision on whether the contest should be rated or not must not be based on one's bad performance; let's stay objective.
Arguments for the contest being unrated: lags for the first ~20 minutes (and therefore slightly increased variance in scores, because of additional time to refresh the page); statements for A, B, C available in div2 while div1 contest was not started (and therefore cheaters could start solving problems ~6 minutes earlier).
Arguments for the contest being rated: variance in results because of lags is insignificant (and lags were fixed quickly), most of participants do not cheat, and if someone cheated, most likely it did not help him (at least I hope so).
Sorry,_I really don't think this contest should be rated._ just means that I just don't hope this contest to be rated because my bad performance,not objectively.I agree with your point mostly.And anyway,the contest has been rated.
Я, как и многие, открыл не тот раунд, думая, что это и есть контест, который надо писать.
При этом мне сразу понравилась E, я ее прочитал и начал кодить.
Это считается читерством?
Или после этого я должен был благородно отказатся писать контест?
Sorry for the Russian language in English thread, feel free to ignore it.
Очевидно, не считается, это ведь не умышленно было сделано. Неужели действительно у большого количества народа была такая проблема? Я, например, всегда смотрю, в какой раунд захожу, т.к. div1/div2 контесты часто совмещены.
Well, let's make the server available in random seconds during the contest. Yes, everyone has 'the same chanes'. But will it be fair if someone guess these seconds and get positive score and another don't? I don't think so.
We all 'were in the same conditions' but these conditions were very random and made results valid +- 50-200 points only. That's up to +- 20 places (around 40th). I think it's enough for making this round unrated (however, it can remain eliminate round for the championship).
any chance to receive a shirt for ranking 205?
I don't know about shirt but I surely know something about a little differently spelled xD
А давайте возьмем на онсайт первые 50 мест и проведем еще один отбор, с нормальной работой сервера и более сбалансированными задачами, чтобы отобрать еще 50 человек! Кто за?
Уж точно не организаторы) А вообще я за, особенно если еще и оставшимся 200 футболки)
Why we can't practice now?
same problem. why???
При этом, раунд будет рейтинговым как для официальных участников чемпионата, так и для внеконкурсных.Почему обновился рейтинг только официальных участников?
UPD Обновили. +91 :D
У некоторых неофициальных точно обновился, по себе могу судить=)
Так ты див 2 писал, а тут про див 1 говорят.
This Cheered me up during the contest.
Весь контест сервер работал хуже, чем какой-нибудь codechef в худшие времена.
Не лучше ли было бы после падения сервера на старте отменить div2 раунд совсем, а не начинать его, да еще и вовремя?
Откуда произошел фейл на старте и лаги в процессе — загадка. Серьезных правок Codeforces не было несколько раундов подряд, последние раунды прошли отлично при большей нагрузке. Последний раунд был проведен 3 дня назад, а с тех пор code freeze. Остались логи, буду смотреть и думать. После первого фейла я сдвинул начало раунда, забыв о div 2. В результате произошел несинхронный старт. Причин решить отменять div 2 не было (тем более что я забыл о его существовании).
so now it is rated only for offical?
I participated in contest unofficially and my rating didn't update.
Check it now.
Откройте дорешку пожалуйста
Ты слишком быстро пишешь комментарий:( Я даже обновил и прочитал, но все равно твоего не было:(
А где дорешка?
I have software problems hacking solutions. Today I had time, locked my solutions, but just couldn't open the sources. I use chrome, have adblocks disabled and have the latest flash player. It's really frustrating. :( Can anyone suggest me what I should do?
Ratings have been updated. Interesting :)
@admin there is a bug in the ratings.
when i click tourist in the top rated column in the right side, then old rating is there in top rated column . same happens when i click on petr.
however it works fine for other participants.
EDIT : it is ok now.
Посмотрел решения на C++ по div1D у топ-20. Свалил штуки три тестом:
Эх. =\
А в чём подвох этого теста?
Из тех, кого я смотрел, было два решения, выводящих nan и одно почему-то 0.3333... Не знаю, в чем там дело.
А мое решение долго выводило 0.666**8**..., потому что я вычитал одно большое (порядка 1012) число из другого и мне не хватало точности. В итоге я поставил везде long double и понадеялся на слабые тесты, но там такого даже близко не было, заходило и с double.
Да, у меня довольно хитрая бага. Спасибо за инфу.
what is test 33 in div 2 problem C. it's like 100000 9 .........................................................................
is it all contain '.'s ?
since the correct output is "NO" then clearly it have at least 9 adjacent "#"s
Though I am not sure, in Problem D, assertion fails on 13th case. Is the given polygon convex really?
Edit: So, convex polygon means they can have three collinear points on side? If so then the definition should have been provided properly. Why should one assume 3 points on side will be collinear?
It's common definition, that some figure is convex if and only if for every two points A, B inside it, segment [AB] lies inside figure too. For the convex polygon, where three vertices lie on the same line that condition is satisfied, so it's correct to name that polygon convex.
Common way is to name convex polygons, where any three points aren't collinear strictly convex.
I asked if 3 points of polygon can be collinear during the contest, and got positive answer. Wikipedia agrees that there can be collinear points in convex polygon. Distinction between "convex" and "strictly convex" would be a good practice in statements, in my opinion.
I think, people may continue to debate on definition of Convex Hull for all day long.
I am giving some more reference to support my statement: http://mathworld.wolfram.com/ConvexPolygon.html
Look, they said about sign. We assume sign to be + / -, not 0.
http://www.mathopenref.com/polygonconvex.html (2nd google search result)
I think, there is not any strict definition of Convex Hull, it is debatable topic. And as far as I have seen, it is common practice to mention whether it is strict or not in the problemset.
i know how it feels bro
That golden days . sigh!!!!!!!!!!!
Мне кажется, что раунд следует сделать, как минимум, нерейтинговым. Результаты очень плотные, даже среди тех, кто сдал больше одной задачи. Таким образом, очень многое решает время сдачи, а оно получено с относительно большой погрешностью.
Во-вторых, по-моему, следует изменить критерий отбора на финал КРОК. Либо провести другой раунд, либо расширить квоту. Простой расчет: будем считать, что из-за сбоев сервера, человек потерял до 10 минут (в частности, у меня между посылками, отличающимися 2 символами, прошло более 4 минут + кто-то мог прочитать задачи на 5 минут раньше старта). Организаторы правильно сделали, что продлили контест на 10 минут — так все, кто хотел что-то сдать без лагов за 2 часа, успешно сдали с лагами за 2 часа 10 минут. Однако, большинство участников в районе 50го места сдали задачи A + (B или C). За 10 минут их суммарная стоимость упала на 80 баллов. Мое предложение — пригласить на финал всех участников, кто отстал от 50го места не более, чем на 80 баллов (ну или какое-то другое адекватное число). Не знаю, конечно, есть ли у КРОК возможность провести "расширенный" финал.
Учитывая наличие большого количества далекоживущих иностранцев в топ50 (а дорогу им оплачивать не будут) — с большой вероятностью те, кто немного отстал от 50го места смогут поучаствовать в финале
Надеюсь, так и будет. В первой сотне иностранцев почти половина — если они откажутся, то так и все, кто 2 задачи сдал, на финал поедут :)
Бюджет сформирован и даже всего +5 человек это уже 10%. Плюс с помещением в прошлом году было довольно плотно. На 5 минут раньше старта прочитать задачи никто не мог — максимум 3. 10 минут это все-таки оценка сверху, так как лаги составляли ровно 1.5 минуты (я их в самом деле замерял). Т.е. из твоих 4 минут примерно пара минут по делу. Да, к сожалению, еще пару минут мог потерять из-за лага. За минут 45 до конца все лаги были полечены. Кажется, не круто обижать тех, кто хорошо выступил и, решив задачи, занял высокое место. Это же как accepted отобрать. И, в самом деле, наверняка, многие иностранцы не смогут приехать — так что квота уползет вниз.
Ну... Открыл хистори своего диалога с товарищем, в котором интересовался у него, действительно ли все так плохо, как я это вижу. В 7:33 я увидел названия всех задач div 2, в ту же минуту смог скачать условие задачи A (так же, как и многие, не заметил, что див. 2). Такие дела. Так что стартануть можно было раньше все же не на три минуты.
Старт контеста в итоге был в 35 минут
Да, тогда, действительно, будем надеяться, что откажутся многие иностранцы, чтобы никому обидно не было.
У меня по сумме намного дольше 1.5 минуты приходила ошибка сервера. И просто намноооого дольше было сообщение о загруженности сервера.
Но я понимаю, что даже перепровести раунд, очень тяжело, не говоря уже о том, чтобы договориться с организаторами расширить квоту.
А москвичам разве нужна гостиница/покрытие расходов на проезд?
Screencast
just a show off, there is nothing to learn from this screencast
It would be pretty poor show-off, considering my start. Actually I just capture everything I write from laptop (as oposed to 2 monitor configuration on desktop). I do not have enough willpower to rewatch my screencasts before I post them, hence at the time of publishing I do not know whether there were something interesing or not
if you do not know whether there were something interesing or not, then dont post them, though i am getting negatives , but i know truth hurts
just be calm.
nobody force you to see Screencast, bro ;)
just be calm.
nobody force you to see my comments, bro ;)
i am trying to increase your contribution and wanna see you in first position
div 1 c:the problem ask you to calculate the number of solution of equation (a+b+c)^3-a^3-b^3-c^3=n and (a+b+c)^3-a^3-b^3-c^3=3(a+b)(a+c)(b+c) so the equation is n/3=(a+b)(b+c)(a+c) put x=a+b y=b+c z=a+c and x<=y<=z my solution is to enumerate all the x and all the y it seem as a o(n^1/3(n^1/2-n^1/3))=o(n^5/6) but it is really fast and I accept the system test.Is it a right way to do this problem?
My solution: 1 <= x <= y <= z and x,y,z should be the lengths of the edges of a triangle, that is z < x + y. Also, we should have that x +y +z is even. Now: N = 3xyz. N >= 3*y^2 and N < 3xy(x+y) <= 6y^3. So we got the bounds for y: sqrt[3]{N/6} < y <= sqrt{N/3}
The bounds for z : y <= z and z is such that N > 3yz(z-y).
Iterate over all y and all z with the above conditions and compute x = N/(3yz) and see if the conditions stated above happen. If they do, increment the result with the total number of permutations of this triplet.
My sol: submission/3606646
Имя Ксения в задаче D было выбрано случайно?
Change from IGM to GM to IGM to GM to IGM in last 4 contests :)
great indeed
Не надо перебирать все. Достаточно собрать в массив делители n/3. В две секунды влезает даже если собирать до sqrt(n), для решения достаточно собрать до sqrt(n/6).
Когда появится разбор задач?
Editorial please!
If there's no editorial, maybe someone can explain approach for problems D and E?
PROBLEM E: we can solve it using divided and conquer algo. just consider the paths go through the root,the paths in the subtrees is sub problems,so we can solve them recursively. for every root , we can run a dfs to get tot pairs (depth_i,sumofw_i),now the problem transformed to this:give you n pairs (ai,bi) , find the number of pairs( ai,bi aj,bj ) so that (ai+bi <= L && bi+bj <= w) ,we can sort the pairs first ,and then use algorithm like two pointers to solve it (sort the pairs first)
ps:the root can't choose arbitrarily,because the depth of divided and conquer shouldn't be very big,so every time we should find the center of the tree(when it was deleted from the tree,the maxsize of the components is the smallest) overall the complexity is n*logn*logn theres is another similar problem for practice http://poj.org/problem?id=1741
Actually, if you just sort the pairs and iterate over them with two pointers, you'll end up counting some paths more than once, because you only need to consider pairs in different branches so that the path goes through the root (pairs in the same branch will be counted in the sub-problem of that branch).
I'm still thinking how to solve that part...
Yes , you are right ,I forgot to say that point... the way is simple , just use a function calc(u) to count the pairs of nodes
under the root of u,and minus every calc(son_of_u) . you can see my code here the vector<pair<int,int> > ch[] stores the information of every son of u
What is the solution for problem B and C Div 1
For C, notice that:
Number of divisor of an integer less than 10^14 is small (I remember it's around 20,000), thus you can brute force (a+b), (b+c), and check if a, b, c are positive integers.
Maybe someone can explain approach for problems B(div.1) ?
Still no editorial?
In the meantime, could someone give me a hint for D? What I tried is to find y_low and y_high for every possible x such that segment formed by (x, y_low) and (x, y_high) lies inside the polygon. The rest parts are just some formulas. However, my implementation got a 2e-6 precision error for a large test and I am not sure which one is wrong, my approach or my code.
My approach gives even more precision error. But with long double on GNU it get AC.
I wonder if there exists solution for problem D (expected square area) without limitation on lattice points.
can you give me some hints for problem E? my best solution is in N*(logN)^3 and i don't know if it is fast enough...
Про футболки какая-нибудь информация известна?
Я передал все данные для рассылки в КРОК, их компания-партнер, как мне сказали, всё разослала.
а теперь их кто-нибудь получил?
Я до сих пор не получил. Есть ли те, кто получил, или те, кто обладает какой-либо информацией?
Мне вот что интересно. Казалось бы, зачем компания проводит контест? Ну вроде бы, показать себя, заявить, что они вот такие клёвые есть, они ищут IT-шников, у них клёво в офисе, etc. Т.е прорекламировать себя, чтобы кто-то пошел работать. А в итоге они что показывают? Может они и зарплату так же "быстро" платят?