Всем привет!
Я автор сегодняшнего раунда.
На протяжении раунда вы снова будете помогать жителям Тридевятого царства в решении повседневных задач.
Хочу поблагодарить Артема Рахова за неоценимую помощь в подготовке раунда, Марию Белову за перевод задач, Михаила Мирзаянова за отличную систему CF и всех участников за то, что не оставляют это событие без внимания.
Больше полных решений и высокого рейтинга всем! gl & hf
UPD: Раунд завершен, поздравляем победителей и призеров обоих дивизионов!
Div-1
1. tourist
3. Egor
4. Fefer_Ivan
5. fhlasek
6. Coder
7. RAVEman
8. neal
9. WXYZ
10. whhone
Div-2
1. vyvtjp643
2. songlj
UPD: Опубликован разбор задач. По техническим причинам русская версия разбора будет опубликована позднее.
Hi Sergei!
Привет!
Я автор сегодняшнего раунда.
18-ого января есть еще CFR 103(div 2) и 14-ого числа ИОИП с условиями приближенным к областной, если не 11 класс, то можно просто поучаствовать(по ссылке все сказано).
А так - удачи :)
UPD: не посмотрел страну в профиле, я подумал об областной в России, а не в Белоруссии.
P.S. ИОИП? Не, не слышал... =)
Удачи вам :)
p. s. Хотелось бы что бы это не сказалось на системе.
да в 100 раунде тоже был рекорд по регистрации - 2800, а участвовали 1800 вот вам и рекорд
див2 бежит впереди паровоза - время до начала раунда див2 на 1 сек меньше, чем див1
P.S. пока писал , пофиксили
participants > 2000 in div2
registrans maybe?
блин(( я конь( не заслал правильное решение... пойду убьюсь ап стену
P.S. ну правда читерское решение прикалком, так что ниче страшного))
а вообще эта задача и расчитывалась на перебор? или дп по профилю?
почему?можете замощение показать?Значит неправильное решение у KADR =)
Надо расставить всех шахматных коней на поле nxm клеток. Коней надо ставить на один цвет, что бы они не били друг друга. (если черных больше то на черные если белых то на белые)
Общая формула (n*m+1) div 2. Отдельно случай 3x2 который не подходит под эту формулу. Надеюсь систесты пройдут.
Обламилась на 56 тесте. Случай 583 2.
2x2 у меня 4.
Я не полностью описал решение. Вот строчка с кода
if (m<2) or (n<2) or ((m=2) and (n=2)) then writeln(n*m)
Я лично убеждался стрессом с перебором на всех тестах :)
Ваша логика обвалится на тесте 2 5 (ответ 6).
Самый лучший раунд за последнее время.
И взломы были(6 взломов по D(B div 1) сделал, а потом самого взломали в придачу :D), и возможность сдать задачу E(C div 1) просто перебрав варианты(чуть-чуть не успел).
Спасибо за контест!
а что за случаи были в D(div2)?
p.s. и собственно на чем в ней ломали?
при n или m равном 1
при 2 2, 3 2, 2 3, 2 6, 6 2
Кстати, в вашем коде искать, где решение - отдельный челленж.
Have seen B before and D is based on known idea which was used in IPSC 2010 task K.
I expected more from this author.
Больше половины условий про прямоугольные клетчатые поля - знакомый синдром, когда придумываешь задачки. "Квадратно-гнездовое мышление". =)
Просмотр решения и взлом - двойной клик по количеству баллов у кого-нибудь из комнаты по какой-либо задаче.
I compared the maximum number of T-shape thing with tourist's solution. All my answer was correct. I hope my printing the board was correct too :(
Edit: final test passed :D
Разве не работал перебор?
Am I the only one who wrote the compilacated code for problem C (div 1) and didn't even pass pretest? :( http://mirror.codeforces.com/contest/142/submission/1040136
My solution is fast enough to run all 81 possible test case in 1s :)
May be the limit should have been min(m,n) <= 9, max(m,n) <= 20 ?
Я первый в комнате заметил набор тестов (2; n) как взламывающие (правда, ценой блокировки собственного неправильного решения), отломал три решения, а потом пришёл neal и начал у меня уводить взлом за взломом прямо из-под носа! Я буквально сидел и F5чил, и сразу бросался вводить неправильный тест, но он меня как-то обгонял. Похоже, либо у него реакция запредельная, либо у него какой-то свой софт, который следит за него за эвентами вида "появилось решение". Даже не знаю.
по мойму neerc-style это neerc-style, это применение алгоритмов с интересной идеей
Задачи на математику - это есть какое-то непонятно что выведите формулы и забейте ее. Задачи которые тут на применение здравого смысла(A,B) или алгоритмов(функция гранди и подобное)(D). Задача С - какой-то непонятный перебор или динамика. Тоже алгоритмы если хотите. Где математику то вы нашли? В том что у числа мало делителей в A?
Кстати, если сильно хочется B - поиск минимального независимого множества в двудольном графе. Собственно я так и решал, только поверил на слово что полное парасочетание существует.
I liked this round....Was logical and mathematical one...........:)
not ST yet...:)Заметим, что компонента связности разбивается на двудольный граф. Строим его. Прибавляем к ответу размер бОльшей доли.
Блин я не могу уснуть.
Для произвольного двудольного графа это не работает:
Что в конно-шахматном графе такого крутого, что на нем работает?
Мне одному кажется, что раунды становятся все хуже и хуже? Div1, по крайней мере. Весьма "нехороший" сотый раунд (эх... юбилейный, блин), а теперь еще одно неудачное мероприятие.
3 первые задачи - 3 свечи. Думаю, при прямых руках можно все 3 отгуглить.
При этом разница по сложности между первой и второй... невысокая (разве что подводные камни второй, за них единственный +). Третья задача сильно отличается от первых двух, опять получился контест, который для всех ниже красного, получался удачным при условии хорошей сдачи даже не первых 3, а первых 2 задач.
А взломы... Ну это хорошо, когда есть что ломать... Но тут сразу видно, как довольно необходимое ограничение на взломы "только внутри комнаты" портит баланс.
Просто интересно :)
Можно я?
1) Взломы есть, но не случаеподобные. Т. е. я считаю, что тесты 2 3 и 2 7 в B должны быть в претестах (а без них задача просто превращается в боян)
2) Если есть задача, в которой ответ выводится за O(1) размышлением с ручкой/листиком/бумажкой/салфеткой, то она - А.
3) Задачи не столь боянисты. А именно: B - просто гуглится, да и боян страшнейший, а D - прямая сумма двух общеизвестных вещей (ещё бы я знал одну из них, но это, видимо, мой промах - похоже, я проспал одну из лекций в ЛКШ.А)
Видимо, вот.
Всякие тупые описки/опечатки.
Ладно если есть какой-нибудь принципиальный случай в сложной задаче. Но когда задача по модулю этого случая ничего из себя не представляет, и только превращает контест в карнавал взломов - по-моему это не дело.
2) Если есть задача, в которой ответ выводится
Никто не спорит, что такие задачи бывают интересными, что таким задачам место на определённых соревнованиях. Я тоже такие люблю.
Но в контексте сегодняшнего соревнования, повторюсь: сегодня она не представляла собой что-то особо интересное (моё субъективное имхо, конечно же), поэтому ставить её на B было как-то нелогично.
В текущем формате схема "если ломаем, то на чем-то одном, и всех" - явно не то, так как разброс по комнатам сильно влияет на результат. Рулетка получается.
И переход по сложности должен быть более плавным. Или вторую решают меньше, или третью - больше.
Как уже было сказано, боянистость задач - вот главная беда. Остальное - дело вкуса. Вот, пишут, четвертая - тоже боян :)
1,4,9...
Ah damn. I think you are right. What a silly oversight.
Thanks.
Не удержался.
Вы код Пети или Гены часто читаете? Там иногда можно и D, и E в 20 строк встретить.
Аааа, все, неправильно прочитал ваш пост, все в порядке :-)
Насчёт большого макстеста - можно вбить генератор в программу. Но, да, неудобно, что даже генераторы посылать нельзя.
Можно перебирать число a до корня кубического, b до sqrt(n / a) и затем просто находить c, если n % (a * b) = 0. А затем для чисел a, b, c можно за O(1) пересчитать min, max.
P.S. Это не самое хорошее решение, просто это самое первое, что пришло мне в голову :)
Нужно среди всех возможных разложений числа n на 3 сомножителя найти максимальный и минимальный ответ.
Для этого найдем все делители числа n и покидаем их в вектор.
goryinyich вы понимаете, что вы своим контестом убили уже двоих!
Троих как минимум
Обновление рейтинга устроено как проверить что все хорошо, нажать кнопочку, подождать пока обновится что-то в базе. Какая-то из фаз застряла, думаю первая.
Не угадал, третья. Что-то уже обновилось, а что-то нет.
Иначе нужно искать геодезические на конусе (это не очень сложно, если знать как они в принципе ищутся), если нашли, то знаем кратчайшее расстояние между двумя точками по боковой поверхности конуса. Если одна точка на дне, то нужно минимизировать функцию одной переменной (перебираем точку на границе), если обе точки на боковой поверхности, то двух переменных, т.к. кратчайший путь может проходить по дну.
Задача B (div1) D(div2) - кривая. здесь подробнее.
Во 2.div в задаче B на тест 1000000000 я думал ответ будет 1000, 000, 000.00, а не 1,000,000,000.00, в условии было сказано "цифры целой части числа разбиваются для удобочитаемости на группы по ТРИ разряда, начиная с младших разрядов, группы разделяются символом «,» (запятая).", ето разве не так - 11111111,321,123?
Случай n = 1 очевиден.
В случае n = 2 граф разбивается на четыре пути, начинающиеся в клетках самого левого квадрата 2 × 2. Нам нельзя брать две соседние клетки в любом пути, поэтому для каждого из них ответ ⌈(длина пути) / 2⌉.
При n ≥ 3 в графе есть гамильтонов путь (кроме случая m = 3, но ответ будет верен и там). Поэтому по указанной выше формуле ответ ⌈ nm / 2⌉.
Это не строгое обоснование, это скорее для успокоения совести. =)
Rendering to html failed: Transformation failed: Unclosed math text.
Всегда мечтал сказать это.
You can improve this even more.
It seems to me that it's greater to use clock(), but not as mentioned above, but somehow like this:
const int ITER = 1000;
const float MAX_TIME = 2.8;
int iter = 0;
...
if (!(++iter % ITER))
if ((float)clock() / CLOCKS_PER_SEC > MAX_TIME)
return;
...
It's better because we don't know, how much iterations our algorithm can do in time-limit; in my variant it will work exactly MAX_TIME (+/- EPS), and won't slow much because we check time only each ITERth iteration.
this submission shouldn't have passed it was missing a case and I added it here
here a test case:
the output should be
-1, but it outputs