Всем привет!)
Сегодня состоится очередной раунд Codeforces #143 для участников второго дивизиона. Наверное, нет смысла напоминать, что ребята с рейтингом больше 1699 могут поучаствовать в нем вне конкурса.
Авторами задач для данного мероприятия являются Холкин Павел (HolkinPV) и Кузнецов Николай (NALP). В подготовке контеста также участвовали Кудряшов Игорь (Igor_Kudryashov) и Агапов Геральд (Gerald). Отдельную благодарность выражаем создателю прекрасного ресурса Codeforces Михаилу Мирзаянову (MikeMirzayanov) и нашей переводчице Марии Беловой (Delinur).
Распределение баллов по задачам будет определено через некоторое время, следите за изменениями).
Желаем всем получить удовольствие от соревнования и почерпнуть для себя что-то новое и полезное.
UPD: Распределение баллов по задачам будет стандартное 500-1000-1500-2000-2500.
UPD2: Раунд окончен. Благодарим всех за участие. Шесть человек, занявшие первые места решили все 5 задач, поздравляем их с отличным выступлением.
1) teoy
2) gomineral02
3) mrNobody
4) Ryannnnnnn
5) marschenly
6) KuchumovIlya
Разбор задач будет опубликован через некоторое время.
UPD3: Разбор опубликован, его можно найти здесь
Одна только просьба — расположите задачи в порядке возрастания предполагаемой сложности. В прошлом вашем контесте задачу Е решили в два раза больше людей, чем задачу С.
Возможно так и предполагалось?
Хорошее предположение — чтобы задачи В и D были примерно одинаковыми по сложности, а баллы за D в 2 раза больше, чем за B. Нужно было делать динамическую разбалловку — тогда все было бы справедливо.
Задача В раз в 10 сложнее D.
Опять не вышло.
Надеюсь задачи будут интересными.
Надежда умирает последней!
270 new user and keep growing.
Следим за изменениями с надеждой на привычную разбалловку.
upd. УРА!
First Codeforces round on Sunday since a long time!!! This should happen more frequently!! Thanks to authors!!! Good luck to new users!!
Thank, U for this words "Good luck to new users!!!".
Задачи отличные!
И главное — массово решаемые.
У меня одного недоумение насчет D? Почему эта задача D?
Постарайтесь прочесть условия всех задач! (с)
потому что это должна быть А.
А сегодня на своем месте.
Согласен, текущая А соответствует уровню задач "А" 2 дива. Но и текущая Д попадает в эту же категорию сложности, хотя она чуть сложнее сегодняшней А.
Отличное соревнование! Первое, в котором 4 решения прошли претесты и, я надеюсь, пройдут и системное тестирование.
наконец-то отличный div 2. раунд
Was Problem D really that easy or have I done some mistake ??My code
If I am correct then I think the problems should have been aranged as A , RightShift( B,C,D ) ,E
I agree with you. But I appreciate it as a test to come up with such an easy idea for a problem of 2000 points after writing harder solutions for 1000/1500 :-) [I am aware that those who open D first have got extra points ;-)]
I´m totally agree with you problem D was really easy and problem B was a little bit tricky
Really nice competition, though it was kinda surprising that the 4-th task was solved by 6 IF-s, i mean at standart score distribution it's expected to be sorted by difficulty. :)
What an amazing Round. 5 Problems are very nice. Thank Authors very much :)
Отличный контест. Спасибо авторам. Но почему в последние минуты на задачу В давало "Неправильный ответ на претест 1"?
Классный раунд...!!! Большое спасибо авторам....!!!!!
А какой ответ в E на тест:
?
2any simple solutions of B?just some words about solution pls
Well you can notice that the number that's resulted at the end is a1-a2+a3-a4+a5... where 'a' are the numbers from the initial array. And i suppose you can find em easily knowing that, didn't have enough time to realize that solution.
yes had exactly the same idea,but somehow could not realize,my bad...
S1=x1+x3+x5+... S2=x2+x4+x6+... n1=n div 2+(n mod 2) n2=n-n1 d=S1-S2 n1<=S1<=l*n1 n2<=S2<=l*n2
Look over possible S1 and S2 values. If it is possible to take such S2 and S1 that d=S1-S2 then answer exists else it doesn`t. In case of its existance some efforts to output the sequence are required.
thanks :)
Почему-то если люди решили в контесте больше задач, чем обычно, то он становится классным. А если, ни дай бог, меньше, то все, контест — уг.
Именно. Мне нравятся задачи, которые для меня интересны, то есть не на "побыстрее напиши" и "шесть ифов".
E вполне нормальная была.
Имеются в виду все задачи. Круто, конечно, что последняя является последней по сложности, в наше время это редкость.
Ну а если по всем задачам то ,по — моему, D слишком простая, а B слишком сложная, а если их поменяли бы местами то было бы нормально.
Спасибо авторам, отличный раунд! Понравились задачи B и С, из разбора Е наверняка можно будет почерпнуть новую информацию.
D стоит 2000, ага. Задачка на ветвление.
Ребят, кто делал Б динамикой? Весь раунд ловил 4 тест..
Извращенец.
А как надо?
Понять, что число d = k[0]-k[1]+k[2]-k[3]... И раскидать его по 1 на массив.
Я это понял и решил писать динамику:)
Что значит, раскидать по 1 на массив.
Если еще не получен искомый массив — пытаемся на 1 приблизить его к ответу. Для этого ищем элемент массива и увеличиваем его на 1.
Начинаем с массива 1 1 1 ... 1 1. +1 к элементу на нечетной позиции — ответ +1, на четной — -1.
Решал так. Пусть d=**a**-**b**(из условия). В ответ сразу войдет a, поэтому подбираем его от 1 до L, причем так, чтобы |b| был минимален, этот b будет d для следующего шага. Повторяем n-1 раз. Причем на последнем шаге b должен быть еще натуральным. Минимум мы ищем для того, чтобы в случае большого первичного значения d у нас была возможность его уменьшить к (n-1)-ому шагу, в противном случае — разложения не существует.
Очень печально сдать А на 1 минуте и затем больше ничего не решить >_<.
и ты не один такой((((
А D? Она же почти как A, 6 if'ов
Ну эти 6 ифов не так очевидны, да я честно говоря, не ожидал такой халявки на Д. Думал там какая-то фигня с реализацией окажется и забил(. А зря ведь
Зачем думать? Писать надо.
upd. /sarcasm/
Писать не думая О_о. Я думал что мой друг выдает бред, когда говорит, что код это не главное, а главное что есть идея и пофиг, работает она или нет. Я жестоко ошибался...
не согласен, думать надо!
Думать надо над решением, а не о том, что возможно, скорее всего, в этой задаче все сложно и её будет очень трудно писать.
Надо брать и писать. На листочек формулы.
Достаточно лишь представить из каких точек мы "видим" плоскость. Сразу становится понятно, что подходит все полупространство, находящееся левее/правее (выше/ниже) данной плоскости.
Я почему-то смотрел неравенства в системе, но не додумался рассаматривать их по-отдельности >_<
Сейчас просматривал решения людей, у которых упала 1 задача. Наткнулся на решение участника korvin42: 2313221. До сих пор в недоумении: почему это упало?
P.S. В задаче B есть опечатка: не "время", а "времени")
Массив до 100?
А! Точно)) Не повезло человеку)
Посмотри на размер массива.
Бредовый раунд
Мало решил?
да
Нет! Раунд ОЧЕНЬ классный)
Много решил?
Ну, я умею решать все 5. Во 2 набажил, 5-ую не успел написать, так как пропихивал 3-ю, которая падала на 7 претесте. Сейчас посмотрю в чем бага(
Когда будет разбор? Сегодня дождусь?
the order should be A,D,B,C,E
can't agree more.
Maybe author have harder solution rather than using 6 if conditional
Давно у нас 500=2000? Писать B было намного сложнее, чем D. По-моему, расстановка A-D-B-C-E чуть больше соответствует истине.
Возникает естественный вопрос — почему не используется динамическая разбалловка?
Потому что она — недоделанная ***ня.
Потому что результаты контестов с дин. разбалловкой больше зависят от случайностей.
Если тут две задачи примерно одинаковой (для определенного решающего) сложности, то человек точно знает, какую ему следует решать. В случае, когда кол-во баллов зависит от кол-ва решивших, ему приходиться угадывать.
Тогда другой естественный вопрос: зачем ставить задачу для 7 класса на 4 место? Впрочем, вряд ли тут кто-то знает ответ.
Потому что это — геометрия. И не во всех школах(более того, почти ни в каких) преподают такую геометрию в 7 классе, ага.
Не так давно в DivII была одна геометрия даже и поближе, чем D...
Ну тут такая геометрия, что любой человек, умеющий ориентироваться в пространстве, сообразит, как это надо решать.
Это скорее к авторам. По неведомым данной ветке форума причинам, они посчитали ее стоящей 2k баллов.
По-моему, довольно-таки частая ситуация, когда решающих одну задачу меньше, чем следующую. И вроде бы это нормально — угадать всегда сложно.
Но чтобы так через две задачи — это оригинально. B даже кодилась сложнее D, та и идея вроде бы не проще.
(Я, как полная идиотина, додумался прочитать условие D где-то на 1 30. Счастья-то...)
Расскажите как B и С решались, пожалуйста, подробно если можно.
C-префикс суммы + дихотомия!
А можно немного подробнее, если не сложно?
С можно проще — двумя указателями.
Сначала сортируем.
Пока можем (стоимость не привысила
k) — двигаем первый указательxвправо, при этом иногда увеличивая стоимость: еслиa[x] != a[x-1]тоs += (x-y-1) * (a[x] - a[x-1]). Пытаемся улучшить ответ.Затем пока стоимость больше
k— двигаем второй указательyвправо, уменьшая стоимость наa[x] - a[y].Линейное решение + время сортировки.
Можно решать без префикс-сумм с помощью двух указателей.
B в лоб. Очевидно, что d=a(1)-a(2)+a(3)-a(4)+..., ну или S1=a(1)+a(3)+..., S2=a(2)+a(4)+..., d=S1-S2. Можно легко посчитать макс. и мин. значения, которые можно получить: Заметим, что в S1 элементов q=[(n+1)/2], а в S2 — p=[n/2]. Тогда max=q*l-p, min=q-p*l. Для существования ответа необходимо и достаточно min<=d<=max.
А дальше можно просто придумать, как построить s1 и s2 подходящим образом. Я, например (на примере положительного d) брал это d и поступал след. образом:
пока d>l-1, ставлю на нечетное место l, а на четное 1, и из d вычитаю l-1 (ну, разность между этими элементами). После этого получаем d<l-1, что позволяет поставит необходимое число (d или d-1 в зависимости от честности n) в соотв. ячейку, а дальше дописать единицы.
Явно существует путь проще, но я его не нашел.
Сам не против послушать решение C.
C:
Отсортируем массив; понятно, что число из ответа изначально есть в массиве. Давайте для каждого числа узнаем ответ для него. Пусть это ai. Так как у нас есть только прибавления, нам интересны только числа меньшие ai, т.е. до него. Запустим бинпоиск, чтобы найти максимальное количество чисел, которые можно сделать равными ai. Можно доказать, что выгодно брать суффиксы из последовательности a1, a2, ..., ai. Осталось научиться проверять можно ли числа на подотрезке превратить в ai, это легко выяснить, зная сумму на этом подотрезке.
Код в точности по этому описанию.
Спасибо.
Классное решение!
Я решал так. Отсортируем массив за O(n * log2n) быстрой сортировкой. Далее, воспользуемся методом двух указателей. Сначала оба указателя на 1 элементе. Потом сдвигаем правый указатель на один элемент вправо и двигаем левый, пока k ≤ count, где count равен количеству действий для доведения всех чисел с l по r до a[r]. Все решение работает за O(n * log2n) + O(n) = O(n * log2n). Код с таким решением.
Для меня задачи показались не совсем очевидными (решил три, С и E не сделал), удивляюсь как много людей начало решать столько задач в див.2, неужели все стали такие крутые.
Nice problem set and competition, though, I believe System test was fast because of El Clasico :D
Agree....
почему у меня здесь 2319144 ВА на первом тесте? upd: поставил r:=0; и оно почему-то прошло 2319298. почему?
Числа должны быть в пределах от 1 до L.
числа должны быть не больше l.У вас дано, что l=2,а вы выводите 456988, что явно больше 2
Hi! How can this submission get AC on problem C: http://www.codeforces.com/contest/231/submission/2319083 But it gets the wrong answer on this test:
Correct output must be: 1 1, but its result is 2 2. Is the test case weak ?
Контест получился хорошим.Но не менее важно дорешивание.
The problemset was good. Not very easy and not very hard. Liked it really much.
как в java сортить массив, и при этом быть уверенным, что она работает не n*n в худшем случае?
писать сортировку руками
я уверен это не лучшее решение
шаффлить массив не?
В java есть Arrays.sort и Collections.sort. Обе в худшем случаи работают за n*n
Если у тебя с сортировкой проблемы, то дальше будет еще сложнее...
Больше чем за год активного использования Arrays.sort не было ни одного TL-я. Использовать встроенную функцию — это благо, естественно при хорошем понимании, как реализовать это руками. (и до сегодняшнего контеста я верил, что в яве сортировка хорошая(в т.ч. если верить докам))
В доках кстати и не написано, что она (для примитивных типов) в худшем случае за NlogN работает.
Эти тесты — особенность Codeforces как игровой площадки. Надо быть к этому готовым. HashMap, например, тоже опасная штука.
а вроде написано. "This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance."
On many — не то же самое, что on all
Если не сложно — что опасного в HashMap? (можно вкратце/пример/ссылку?) А то неприятно удивляться таким нюансам :)
Всего лишь работает за квадрат
Массив примитивов — никак. Надо делать рандом шафл.
Можно случайно перемешивать массив (см. мое решение).
Хоть один конструктивный ответ. Спасибо!
Главное следить, чтоб рандом временем инициализировался, а то ведь можно массив отшаффлить обратно :)
javaзадроты
Куда денешься, если не хочешь быть похаченным своим собственным антиквиксортом ? :)
Как я и думал, следить ни за чем не надо (вот код дефолтного конструктора):
Напиши руками mergesort или heapsort и скопируй его к себе в шаблон
Ого, сегодня на этом попался ivan.metelsky
C упала на тесте
:facepalm:
Has anybody here solved B using Dynamic Programming?
yes.
Great. I thought it was too slow to get Accepted. The time complexity is nearly O(10^8). However, I got AC.
If time complexity is O(10^8) be sure you'll get AC. :D UPD: Of course on Codeforces
I don't know, i've got a lot of TLE's with time complexity O(10^8). Before SPOJ gets a faster processor, it was a bit hard to get AC with this time complexity. Anyway, CodeForces has a fast judge.
контест -- СУПЕР Задачи легки на понимание А первая задача -- ХАЛЯВА
Халява — это D. A хоть на 500, она и должна быть такой.
Кому-нибудь халява, а кому-нибудь и дебры.
Great competition!
Хороший раунд, но разбалловка, конечно, странная... Я задачу B почти полтора часа кромсал, все варианты рассматривал, а D за 10 минут 6 ифами сделал. Может за нее 2000 баллов дают, потому что она для новичков страшновато выглядит, если не читать условия?
very nice problem set, thank you very much ^^
I think there were lots of WA's on problem C. Maybe reason is there were no alert about not using %lld specifier on C++. So lots of people didn't use 64-bit integer. and maybe 64-bit integer was not neccessary on authors solution.
UPD: The only thing different with this comment and mine is downvotes and upvotes :D
Numbers that you need to find are fit in 32-bit type, so I think the warning about %lld was not necessary.
I made 2 successful hacks on submissions which did not deal with overflow in multiplication. It seems to be the most common mistake I think.
Отличный контест. Только задача В мне показалась намного сложнее чем Д. Возможно это субъективное мнение.
……
Are you happy ? :)
Как получить кучу восторженных откликов за контест div 2? Предложить в нем 4 простые задачи и пятую с более-менее очевидным решением из нагромождения классических алгоритмов.
Нет, наверное, и вправду стоит хотя бы изредка делать такие контесты. Но все же С и D лучше было дать посложнее. Потому что для меня радость от решения задачи как-то коррелирует с временем, в течение которого я над ней думал.
C — очень хорошая задача, а вот B я так и не понял, как делать, во время контеста)
B и D, думаю, следовало поменять местами.
C — довольно интересна, D слишком легкая как для D, но в целом контест довольно хороший. А у меня радость от решения задачи пропорциональна (сложности) / (время, которое я потратил на решение).
Куда спрятали разбор?
UPD: Спасибо, вернули. Не пугайте ;)
Читаю и ору с себя:/
Все пишут про халявную D и 6 ифов. Я умудрился написать в ней пересечение прямой с плоскостью и рассматривал варианты: если прямая из точки обзора до центра плоскости не пересекает другие — значит можно добавить к сумме. По-настоящему халявная А и довольно идейно простая С. А предположив, что надо было кодить в B, поплевался и начал решать другие задачи. Да и вроде бы это кодить и надо было. Странный раунд :/ Неудивительно что 195ый(долбанная Д — такая простая для всех).
I really got surprised when I saw problem B is dp, ...!
Greedy is accepted too.
How can we Dp problem B. Can you show me ???
dp f[i][s]=true means that where are a[0]...a[i] left after some operations(a[i] is not the origional one), and a[i]=s(probably negative)... we can enumerate a[i] from 1 to l to check if condition f[i+1][s2] is true, here (s = a[i] — s2).finally check if f[n-1][i] is true for some i from 1 to l
The hyperlink of editorial is linked to russian editorial again:( hope you can fix it:)
Хороший контест, спасибо!) Правда, то, что кактус вершинный, я понял только что.))
I think that problem C was extremely harder than problem D!