Всем привет!
Приглашаем вас принять участние в Codeforces Round #245, который состоится 11 мая (воскресенье) в 19:30 по московскому времени. Это уже четвертый раунд, автором которого являюсь я. Несколько последних раундов помогли мне подняться в десятку лучших по вкладу на Codeforces. Большое спасибо вам за оценки; я старался изо всех сил, чтобы этот раунд был не хуже, чем предыдущие.
Раунд подготовлен моим другом Petcu (задача D1 E) и мной (все задачи кроме D1 E). Мы старались сделать задачи как можно более разными. Поэтому я надеюсь, что каждый найдет себе задачу по вкусу. Главный герой в легендах задач Iahub – на данный момент лучший участник Румынских сборов по подготовке к IOI.
Раунд бы не состоялся без помощи: Gerald Agapov (Gerald), Damian Straszak (DamianS), Dan Alexandru (DanAlex) и Vlad Badelita (vladb). Традиционно благодарю Mike Mirzayanov за систему Polygon и платформу Codeforces, а Delinur за перевод задач на русский.
Желаю вам высого рейтинга и удовольствия от решения задач!
UPD Распределение баллов
Дивизион 1: 500 1000 1500 2000 2000
Дивизион 2: 500 1000 1500 2000 2500
Приношу свои извинения за все проблемы, которые возникли во время раунда (от неоднозначности условия задачи Б до неожиданно простого решения задачи Д).
UPD
Победители Div. 1:
Победители Div. 2:
UPD Разбор задач
Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants.
Good to see another Romanian made round. And it's even 1/3 Mures (my home region)
Thanks for the contest! Long time no see:) And tonight I' ll try my best to reach purple( well, not pupil) God bless me:p UPD: I' m so surprised to realize that tomorrow is my birthday too, what a coincidence!
Happy birthdays ..
и еще всем с днем победы!!!
A contest after 9 days. :) GL HF!!
We really expect to see what the life of a very good Romanian competitive programmer is like :)
По привычке сразу же прочитал имя ГГ наоборот)
Забавная привычка.
?етеатич етирвИ ан оглод как И
I think the problem statements about programmer will be very different && interesting. May be 's counting girlfriends, scheduling for date with girls or some games with girls... haha, just kidding.
Что за беда с CodeForces? Почему такая очередь на тестирование? Уже начинаю побаиваться за раунд предстоящий...
дааа, действительно долго тестируется, учитывая что ваша последняя посылка была 2-го мая
Im bored
Why there arent so much comment?
A rare occasion: the points' distribution appeared more than 1 minute before the contest :D
And yet another: there are exactly 1000 registrants in div1!
It seems E question will be easy
I dont want to be first again man
Easier it E(Div1)
Ok ,i'll solve
As you know no problem for me :)
Div 1 начало в 19:40
Div 2 начало в 19:30
UPD. исправили
As usual, delayed :D
why the 10 minutes delay?
Because I had to do my dinner.
Although it was not official, still thanks for consideration Codeforces.
And I needed some time to wash off the sand, running back from the beach :)
I think, server is busy.
Delayed?
Like other contests its delayed
Delayed :(
Good start!
Same as usual
delay delay delay
I think the "usual time of CF Round" should be 7:40 instead of 7:30
Then all of the contests start at 7:50 :D
If so, I think the "usual time of CF Round" should be 7:50 instead of 7:40
Then all of the contests start at 8:00 :D
Just a few recent contest.
Another time... 10 minutes delayed...
For me it showed that it has started.
So, do it!
Looks like somebody important rang and said he was late to register.
maybe tourist ?
nope.
Exacly 1000 participants in div1 :O
Wow, at the same second! :D
What, 999?! I thought it was final..?
Exactly 1000 div1 registrants! :D
It shows 999 to me.
now it is 999 registrants in div1...... I think someone cancel it....
1000 coders for div1 !!!! what an amazing contest~!!!! thanks for the delay!
Exactly 1000 people registered for div1.
Ровно 1000 зарегистрированных в div. 1. Забавно
А участвовать будет 650, наверное
почти угадал!
exactly exactly exactly
It's contest? :)
I don't know
"As the problems are varied, we hope you'll find at least one problem of your taste."- are you kidding, fchirica?
leaving contest arena, this contest is not for me. :(
Is Div.2 really Div.2...?
Я один считаю, что такой контест -- неуважение к ветеранам?
*в первую очередь
А в чём, собственно, выражается это неуважение?
Если я все правильно понимаю, ему не нравится, что автор и его герои из Румынии.
Хотя как из этого следует неуважение к ветеранам — не понятно
Могу предположить, что неуважение к ветеранам заключается в задачах-боянах
И какая же задача по вашему боян?
Мне кажется дело в иллюстрации к задаче Bdiv1/Ddiv2, рисунок в которой похож на свастику
участники из Индии ветеранов не уважают вообще, получается :)
Там была иллюстрация? О_О
Если самому рисовать, так получается
(версия конспирологическая) В задаче div1 B есть свастика
Всего лишь интернет-мем. Порой так говорят на что угодно, не стоит заморачиваться.
Я такого мема не видел и решил поинтересоваться. Вдруг у человека есть замечания по делу.
Это своеобразный юмор. Чуть ли не локальная шутка. Не обращайте внимания.
I dont understand the problem A div2. Who are the red and blue balls??. I am crazy with this problem. Please, for the next competitions that you should better the content of problem. Now, I see the clarifications of problem A, is very late and I lost many points, WDF!!!!
Wrong answer on pretest 2
Wrong answer on pretest 2
Wrong answer on pretest 2 . . .
:|:|:|
Небольшой баг: во кладке "задачи" у меня показывает, что D решена, хотя в комнате она взломана.
Как решать D(div. 1)?
Минимальное евклидово расстояние между двумя точками.
Прикольно, действительно)
Интересно будет посмотреть, какой процент людей писал это. Подозреваю — у большинства перебор.
Перебор? То есть, сейчас на систестах будут массовые TLE?
Почему TL? Можно ограничить длину отрезка-ответа сверху каким-то числом, и перебирать только "короткие" отрезки. Грубая оценки длины сверху ~10000; вероятно даже меньше. Это должно зайти в 2 секунды.
Даже на джаве? слезливый умоляющий взгляд
Ну, отрезков длиной 10000 в худшем случае 90000. (90000+) * 10000 = 9*10^8. И как это в 2 секунды зайдет?
Легко и непринуждённо. Сервера-то быстрые (крутые i7), операции очень простые, доступ к памяти подряд.
Долго, однако, нет систестов... Неужели подгружают старые машинки, чтобы вершить правосудие :-)
116/296. Справедливость восторжествовала.
Мне кажется, все потому, что многие неправильно скопипастили алгоритм с е-макса. Считать-то нужно квадрат расстояния, и это нужно учесть сразу в нескольких местах.
Вопрос к тем, у кого все заходит легко и непринужденно. Почему 6600227 дает TL, а 6600228 получает АС?
6591662 — зашло.
6594975 — на Java тоже вполне легко всякая чушь пихается)
Причем это вообще ни разу не корректно.
Блииин, ну точно. И ведь ещё сидел, думал, как это к геометрии свести, и такую очевидную идею не придумал(
А можно немного пояснить? ^_^
http://e-maxx.ru/algo/nearest_points наверное, вот это ;-)
А что мы берем за точки?
Хм. Пусть x[i] = i + 1, а
. Копипастим алгоритм отсюда, изменяем его так, чтобы он искал квадрат расстояния, получаем АС.
А, точно, благодарю =)
What is the solution for problem A Div.2??? A is the hardest problem today:)
sort
Oh, No. It's a very stupid bag :(
Sort point by coordinate and 0 1 0 1 0 1 0
1) Sort points by coordinate. 2) Simply put 1 0 1 0 1 0 1 ... 3) Sort points by order in input 4) Write them to output
I wrote only 1 0 1 0 1 0 1... without sort :(
I did it and got Wrong answer on test 3. But when I sort, I get Accepted.
why sort?
Counterexample (without sorting gives the wrong answer): 3 0 3 1 2
Omg it seems so obvious now...
Hint[1]: you can totally ignore the segments...
Hint[2]: sort
Я правильно понимаю, что в Div1 A если не применять операцию на вершины по два раза, а в конце получить целевое дерево, то количество операций будет минимально?
вроде да
Неужели из фразы "они должны встретиться ровно один раз" также следует, что и их пути должны пересечься ровно один раз?
Не следует, но об этом было оповещение.
Было-то было, только благодаря ему я задачу и сдал, собственно. Просто хотел уточнить.
Иначе можно разбить на отрезки: (А двигается до места встречи, Б стоит), (А стоит, Б двигается до места встречи), (А идёт к финишу, Б стоит), (А стоит, Б идёт к финишу). Пути могут пересекаться в нескольких клетках, мировые линии -- только в одной.
"должны пересечься один раз" тоже непонятно, лучше — "у их путей должна быть одна и только одна общая клетка"
Я что-то не понял, в Div.1 B прислали клар, а условие не исправили?
У меня было также. Больше часа перечитывал условие B (в т.ч. c F5) и пытался найти у себя баг.
И только за 15 мин до конца раунда, на странице списка задач ("Основное") заметил этот клар.
Мне кажется, или обычно принято исправлять текст условия после клара?
What the heck is A? Could not come up with any idea :-s
0101010101 And sort them by id afterwards
why can't we use all balls of the same color?
Because for example if interval is 1..3, and balls are at 1,2,3 and all of them are black, and no red, then inequality |3-0|<=1 is incorrect.
thanks, I misunderstood the task, I thought ri, bi are coordinates of the balls (facepalm)
So I was not the only one to think on the same lines :)
Though I made the correction but could not get an AC because of the sort thing.
I think D should've been B. (div1) Or A. Ok, not A, but it's seriously easy to solve. I saw several solutions that made use of the fact that |A[i]| ≤ 104 —
solutions, which pass maxtests (easy to make here) in slightly under 2 seconds.
Really? >_>
Really :(
Unfortunatelly, I've tested this approach during challenges only — it passes in 1.3s in my implementation.
I rewrote LLI_E_P_JI_O_K's 6595981, ran it on "40000 40000x10000" and got 686 ms using the CF Custom invocation. On my computer, it takes 1200 ms on that test and 3200 ms on "100000 100000x10000", so it should be 1830 ms on CF, +- something in the order of 10 ms.
Unbelievable if O(N*max(A)) solutions could be passed systest.
not max(A) but min(A) (although it's not key ...
min(A) = -10000 => O(-1e9) ??? Faster than every algorithms?
min(abs(A)) ......
At the beginning, I was expecting it might be something related to dp convex hull (yeah, it's problem D) and tried to play around with the formula to solve it. And you probably know how it feels when I finally got the solution...
Really sorry for that. Didn't notice such a solution. =(
Why have O(nlogn) solutions timed out?
Right O(n * logn) solutions haven't timed out ;)
I mean that as someone has already noticed it's easy to make a mistake in this algorithm in this problem by writing somewhere dist2 instead of dist or vice versa.
Yeah you are correct!
Even if we suppose that simple solutions (such as O(N|A|max) solution with some heuristics) doesn't work, I think D was too well-known for a D. It was just the classic closest pair of points problem. Some participants might have copied the implementation of this problem and submitted..
I try to hacking a submission when the countdown show 15sec, then when the hacking is running contest going to be ended, what happen with my hacking? It show "Status: challenge-other"
Подскажите, пожалуйста, решение E (Div. 2)
Заметим, что вершин с c[i] = 1 должно быть не меньше половины. Если меньше — сразу выводим "NO".
Очевидно, что мы будем подвешивать вершину с меньшим значением c[i] под вершину с большим значением. Ну так отсортируем вершины в порядке убывания c[i] и напишем несложный переборчик (каждую вершину будем пытаться подвесить под предыдущие в отсортированном порядке). Доказанная мной асимптотика такого решения —
. Судя по всему, можно доказать и лучшую асимптотику.
UPD. Уточняю: единички подвешиваем жадно.
А можно решать более быстро. Сначала отсортируем по возрастанию. Посчитаем такую динамику,можем ли мы из префикса длины l получить лес с размерами деревьев s1, s2, s3...sk соответственно, то есть соответствующему некоторому разбиению числа l на слагаемые. Переходы, вроде как, понятны. Разбиений числа 24 полторы тысячи. То есть решение за O(nf2(n)), где f(n) — количество разбиений на слагаемые числа n.
Идея интересная. Хотелось бы только посмотреть, насколько длинный код в итоге получается.
Решение действительно замечательное. Но у меня, например, не получается быстро находить разбиение числа 24. То есть их вроде как немного, но из-за рекурсии и помещения их всех в set это занимает около 3 секунд...
Надеюсь, что вы ищете только упорядоченные разбиения, иначе неупорядоченных действительно очень много. Плюс — можно не класть в сет, а класть в вектор и потом делать бинпоиск по нему. Чтобы это работало еще быстрее можете посчитать некоторый хэш от вектора и уже делать бинпоиск по ним(ровно как класть в хэшмап, или просто в мап с таким ключом). У меня работает моментально все, к сожалению на контесте я не довел решение до конца из-за глупых баг. Как только доделаю, обязательно выложу.
ADD: решение сдать на кф пока не получается из-за очереди, но должно работать.
ADD: Accepted on codeforces
Why doesnt this work for A?
If we alternate the points 0 1 0 1 0 1 then no segments can have the difference more than 1.
That's right. Sort them by id(input order) then
A / Div. 2 sucks.
Looks very hard for A, knowing that the same problem was used for Div1-E just with a little restriction change.
Edit: My excuses, the problem is actually different, I misunderstood.
Блин, настолько жёстко меня ещё раунды кф никогда не имели Оо
Ребят, а кто-то может сказать, в Div. 1 D бывает длина ответа больше, чем 1000?
Не бывает ответа длины больше чем 10000, ибо всегда выгоднее взять длину 1
А есть пример, на котором достигается длина >1000?
Вроде как так: 99000, 99001, ..., 100000, -99000, -99001, ..., -100000.
Очевидно, что (100000 — 99000)^2 + 4 меньше чем 2000^2. Но доделать видимо можно, да
странно, у меня зашло такое решение, в котором отрезки до 1000 только рассматривались
А в тестах такого не было :)
Ну это и не странно. Судя по всему авторы вообще такого решения не ожидали. А придумать тест оказывается не просто.
Не знаю как тут вообще, но сдать первую за минуту до конца, это перебор уже;)
Вообще супер. Продолжаю традицию сливать контест и при этом занимать с каждым разом всё более высокое место, лол
Nice contest, A was an exemplary A problem, not too hard, not too easy. Speaking about B, things change, a little bit hardcore to implement, otherwise a classical DP problem. C was way easier than D (look at the number of submitted codes for C, it's pretty low). C probably is some backtracking and for D I'm really curious about the solution. At E I smell an idea similar to http://acm.timus.ru/problem.aspx?space=1&num=1129, but much more elaborated. Clearly, the score distribution was a little bit wrong. Hope my rating won't decrease by too much. Overall, I liked this contest a lot. This should be taken as constructive criticism. Everybody makes mistakes. ;)
You mean C was harder than D*
Couldn't understand problem A (Div. 2). I think an example would have been great in the problem statement...
Look at this from left to right, in case you print 1 0 1: 0 1 1 so segment [2,3] will have |2 — 0| = 0, which violates.
So, the problem is just with the problem text. If he had taken the time to write it properly, there wouldn't have been so many WAs for such a trivial problem.
Thank you Chirica!
Really nice poblemset ;)
I just needed 2 more minutes to submit C :(
System test!!!!!!!!!!!!!!!!
I missed to watch systest.
(
)
Translation please. Thanks.
How fast have you submitted the A problem?
Just that three words means this long sentence?? Russian language!!
Not really unexpected, considering Slavic languages have something called conjugation and declension (note that I just googled the english words :D).
It's just one example... If you compare the today's problem statements, the Russian versions are longer than English, less words, but more characters and syllables.
In Hungarian, "I love you" is one word, 'szeretlek', but its length in syllables (3) is same as in English. Does that really makes Hungarian more concise than English?
"Did you solve the first one quickly"?
Решение для див2А, вроде бы верное. Заведём set, будем хранить в нём границы отрезков. Посортим set. В итоге получили, новые отрезки. Если в новый отрезок попадает чётное количество точек, то заполняем их цветами поровну. Если нечётное, то заполняем красными на одну больше, при этом, следующий нечётный отрезок заполним синими на одну больше и т.д. Тогда, очевидно, что какая-то последовательность таких отрезков, образует какой-то исходный отрезок и исходя из алгоритма заполнения, в нём будет выполняться требуемое условие.
изи парень.
Ты бы еще Дейкстру написал
LoL=) Сейчас бы ещё, что я написал заслать=)
Выше в комментариях есть решение. Задачка на внимательность. Отрезки, по сути, не важны. Просто красим точки так, чтобы в порядке следования по возрастанию координаты цвета чередовались: 0 1 0 1 0 ... Сортируем все точки по координате, запомнив номера. Потом проходим по этому массиву и номерам этим поочерёдно присваиваем 0 1 0 1 ...
Div.2 B вообще ни о чём задача. Ни алгоритмов, ни решений не надо — бери и моделируй, что сказали...
Можете подробнее рассказать, как решать эту задачу?
Просто перебором. Вставляем шар в позицию i, удаляем все последовательности шаров длиннее 2 (одного цвета). Так до тех пор, пока не останется таких последовательностей. Делаем это n раз, выводим разность длины оригинальной последовательности и самой короткой получившийся.
Как же плохо порой не дочитывать условие нормально, я подумал что шар можно вставить 1 раз...
Спасибо!
Кажется, там как раз всего один шар можно вставить.
Насколько я понял, Qumeric имеет ввиду не поочерёдную вставку шара в n позиций, а перебор n возможных вариантов вставки в каждую позицию.
Да, перебор. Извиняюсь за нечеткую формулировку.
Выглядит так, что в задаче D(div1) при взломах правильный ответ считается при условии 0<=i,j, а не 1<=i,j, потому что при 1<=i,j первый элемент массива никогда не войдет в сумму g(i, j), а оптимальный ответ на тест
показывается 4. Но такое возможно только при i=0, j=2 или наоборот. Очень странно, что на вопрос об этом был ответ 1<=i,j.
Я сейчас запустил все наши решения. Они дали мне 26, можете сказать id взлома. Все должно быть ок.
Ой, да, я не то посчитал. Сорри
Это же надо было так облажаться в DIV1-B (6597358):
maxAns = mv;maxAns = std::max(maxAns, mv);
на чем у всех падает div1 B? на том, что не учли, что они не могут встретится в 1 или последней строчке и в 1 или последнем столбце?
Ага(
spent over thirty minutes finding a test case that gives - 1 on problem A Div 2. Gave up and submitted and it got accepted. I guess there was no such test case.
Is there any such test case? Please mention it.
There's no such case. If you color the points 01010..01, any interval will end up with the same quantity of 0s and 1s (size of interval is even) or |#0 — #1| == 1 (size of interval is odd).
А будут ли видны тесты?
Just adjacent xs and ys enough for D. Such a tests...
Take look to this.6597823
I think tester should explain this.
WA7 в D на решении с перебором
I also had WA7; now I fixed it, and now I have WA8
And what does WA7 mean?
I hadn't checked right border of array
Why the test cases hasn't been visible yet?
У меня в C внезапно прошла жадность (6596036): сортируем вершины по невозрастанию и, начиная с корня, к каждой вершине подвешиваем жадно максимальные, которые в нее влезут (их должно быть хотя бы две или ноль).
Как это доказать или опровергнуть?
Например, тестом:
Спасибо, и правда, валится. Я думала про примерно такой тест, но поленилась проверять, все равно не успела бы исправить. (Авторы систестов, видимо, тоже где-то поленились, так что им тоже спасибо.)
How do I check on which test case my submission is failing? Once I click the solution link, its showing test case number "Runtime error on test 34" but not the test case.
Click the solution number, and click the "#" sign above, and you'll get this: 6595417
UPD: Sorry, it used to be there. I don't know where it is now.
UPD2: It is shown now.
...where you also wouldn't be able to see tests :)
the tests for problem D are very weak
6592992 should get WA with this test case n = 1003
501 elements with value 10000 , 1 element with value 5000, 500 elements with value -10000, 1 element with value -5000
(my generator code : http://paste.ubuntu.com/7448665/ )
Unfortunately, the announcement for problem B modified what was asked in the original statement. Instead of requiring that the two characters meet at a single cell, their paths should have only a common cell after the clarification, which is a stronger requirement (since their speed may be different).
This was surely troublesome for those who started the contest with problem B (like me)...
After the contest, xhae had told me that the following paths are feasible to the problem description, but not to what the problem author requires.
A: [1,1] -> [1,2] -> [2,2] -> [2,3] -> [3,3]
B: [3,1] -> [3,2] -> [2,2] -> [1,2] -> [1,1] (edited, Thanks to marspeople! It was previously [2,3] instead of [3,2])
(spent exactly same time on all cells)
In this case, they only meet in [2,2], but this was not included in the solution (since the intersection of both paths is {[2,2], [1,2]}). The problem description is not clear enough. actually wrong.
I think you meant B: [3,1] -> [3,2] ...
Yes, the problem becomes totally different with the added clarification
What are tests 18 and 14 in Div1.D? I have two solutions (6592810 and 6597945) and they both got TLE on corresponding tests, while running the latter on the 'Custom run' page shows me stable 900ms running time.
I think in the following line the difference should be squared:
if (p1 >= 0 && pts[i].proj — pts[p1].proj < ans — eps) {
I had a TL18 with a similar bug.
Thank you, that's definitely a bug.
However, I'm still wondering about the latter submission (and that's my main concern), which was tested via 'Custom run' on several test cases and still got TLE. Do you have any cool ideas about it too?
Nope.
So, I decided to write something stupid in Div 1 D since I haven't thought of solution.
Seemingly, I couldn't construct an example with large length, so I tried to stop my search after something bigger than sqrt(100K). As I like round numbers, I only checked length up to and including 400. Which, unsurprisingly, got WA.
After the contest, I tried using binary search to determine what the actual maximum length was on the test data. Imagine my joy when I gradually found out that the answer to that question was 401.
But, seriously, I am disappointed that this task was included in the contest if the authors were unable to find a case large enough to fail these naive solutions. Even though I liked the task intended solution with conversion to geometry.
I have a standard solution to "closest pair of points": sort the points and sweepline, keep the ones already sweeped in a
. I know that if K = 50, this approach hasn't ever failed me, so I use it :D
map<>; when processing a point, try all points with close y-coordinates, up to the K-th closest in both directions, then add the processed point into themap<>. Time complexity:What's wrong with the standard divide and conquer?
It's a bit harder. What I'm talking about is basically a bruteforce+smart condition.
Your bruteforce can be turned into a simple correct solution:
xand maintain a set of points that have already been processed sorted byybestAnswer— closest distance among pairs of processed pointscurrentPoint.y - bestAnswer < y < currentPoint.y + bestAnswer, delete points withx < currentPoint.x - bestAnswerand updatebestAnswerI just need to remember something like "an
solution similarly relies on there being few numbers close to the processed one, so there shouldn't be evil test data for my approach either" :D
This worked for me too for a long period now. ( even with K smaller ) It is very usefull in a Olympiad fromat as you always make many points in short time. :)
never mind!
401? I also binary searched and got 1002... Look at those solutions: http://codeforces.com/contest/429/submission/6598773 (1001 fails) http://codeforces.com/contest/429/submission/6598792 (1002 passes)
I would guess that you're getting WA because your initial value of best is too low.
This is not the case: http://codeforces.com/contest/429/submission/6599177 g(i, i+1) <= 10^8 + 1, so 10^9 is not too low.
Agreed. Hmm, that's interesting...
Here's 400 failing and 401 passing from me. I cannot yet spot the difference in our codes.
UPD: Oh, OK. There were some extra cases added afterwards (from community, I guess). But 401 was enough during the competition then.
Ah, I understand. You're really unlucky :P. But my case is similar, I set bound to 320 :P. I thought about making it larger, but on my computer it took 1s to process maxtest, so I have left it on 320. But cf servers are much faster than my laptop, for 1000 it took 0,3ms to process maxtest using my solution, if I would have known that before, I would enlarge my bound and got AC xd. But we shouldn't complain, in fact we were "cheating" and we don't deserve AC :P.
I only checked up to 100 numbers back + 100 closest positions (larger and smaller) in terms of prefix sums. I didn't know how fast the CF servers were, so I wanted to avoid TLE. Sadly, this got WA on test 39, with < 500 msec. When I increased the limit to 500 I got AC (with a running time of about 1.8 sec). Anyway, I don't think it's easy to create test cases to fail something like this.
"Anyway, I don't think it's easy to create test cases to fail something like this." — it is.
5000 (k x 10000) -5000 (k x -10000)
for some big k.
B слетела из-за крайних точек.
С слетела из-за того что решил добавить отсечение по времени если не пройдет претесты.
А вообще, спасибо автору за интересные задачи :)
Хорошо хоть в D взял 1000, а не 400, как eduardische:)
Div.2 B. I used easy solution with regexps, because there were no big data. Insert x in every possible position, and While (find 3+ equal numbers){delete them}, Calc what is left. Solution with Perl 6597887.
This guy is lucky as hell: http://codeforces.com/contest/429/submission/6591828 He set max difference j-i to 1005 and got accepted but if it will be changed to 1001 it will fail (smallest number which can be set is 1002).
EDIT: I don't know why, but I can't reply to those posts below :( Compare those solutions: http://codeforces.com/contest/429/submission/6599177 (my solution, 1001 fails) http://codeforces.com/contest/429/submission/6598792 (my solution, 1002 passes) http://codeforces.com/contest/429/submission/6598182?locale=en (eduardische solution, 401 passes)
EDIT2: Explanation of that phenomenon is here: http://codeforces.com/blog/entry/12254#comment-169126
Nope, 1000 is just fine. http://codeforces.com/contest/429/submission/6597981
No, the difference of 401 passes, as I mentioned earlier.
Hmmm, and what about http://codeforces.com/blog/entry/12254#comment-169072
Maybe some new tests were added? My solution also fails with 1000, but works with 1010...
Тесты будут видны?
Hi,
Does Codeforces usually allow users to see test cases after the contest ends?
I see that test cases for problem B (DIV 2) are visible now, but not for problem A (DIV 2). Will it be a matter of time until test cases for problem A get released, or does Codeforces sometimes not release them?
lol
What's typically too deep for a recursive solution? I figured 10^5 would cause a stack overflow, so I wrote Div1 A non-recursively (and somehow wrote a bug into it that way).
Codeforces sets the stack to 256 MB, so it's not easy to overflow it with recursion. You'll likely hit a time limit before that.
Ahh, I wasn't aware it was that high! Thanks!
j = 1001
WA 47
http://codeforces.com/contest/429/submission/6599410
j = 1002
Accepted
http://codeforces.com/contest/429/submission/6599408
Nice
Why are the test cases not showing up till now ?? -_-
Round Stats
About div1A/div2C How is this test case valid ? http://codeforces.com/contest/429/submission/6589121 test 35
which is
10
1 10
1 9
10 2
10 3
3 7
3 8
9 4
9 5
5 6
1 0 1 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0
But in the question it was given The root of the tree is node 1 But in the test case it states an edge from 10 --> 1 ???
Then node 10 is a child of node 1 (the root) !
No the test case assumes that the edges are bi-directional and the optimal answer is found assuming 1 to be a child of 10.
Also the 1st test case has edges,
2 1 and 3 1, which are opposite to 1 10.
I solved the case by hand, assuming that node 1 is the root, and it is showing correct answer !
Hmm .. you maybe correct about what you are saying Let us assume that if the input contains a b then there is a directed edge from a->b , like in this case 1-10, which justifies 1 being the root.
But see the sample test here,
It has the following edges in the input:
2 1
3 1
which tells us that there are edges from 2->1, which contradicts of 1 being the root. I hope you understand what I am trying to say.
Actually this is how I've generated the tests , but some of them were added later. But it didn't came to my mind that this will make any difference or someone will get confused. Though , the statement was clear sorry for the inconvenience.
My friend, why do you assume that the trees are directed?
Typically trees are undirected (unless otherwise stated in the problem), and the input specification just states that a pair ui, vi means that there is an edge between those two nodes. It doesn't mention any particular direction.
Problem statement states that 1 is the root of the tree.
Doesn't that mean if the tree is rooted so it has to be directed ?? Because root of a undirected graph doesn't makes any sense.
I frankly have no answer to your statement that "root of a undirected graph doesn't makes any sense".
My recommendation, if you'd like to consider it, my friend, would be to invest a few moments studying the definition of a tree. Wikipedia's entry is fairly well-written and I think it will helpful.
Yes, you're actually right in saying that since it has a root, it must be directed (by definition of rooted tree). However, naming the root isn't enough to uniquely determine the direction of each edge (since they can either be all towards or all away from the root), the edges they give you are just a list of the edges present in the tree (without direction), and it's up to you to assign them a direction that makes sense.
Wonder why they can't simply give us parent index for each vertex. Would be a lot less trouble for everyone involved.
The problem statement goes as follows:
“Each of the next n - 1 lines contains two integers ui and vi meaning there is an edge between nodes ui and vi.”
Note that it mentions an undirected edge between two nodes, not a directed edge from one node to another. So, the statement does not imply the nodes will be given in any particular order (from the root, or lexicographical, or whatever).
What were your solutions to C? First important observation is that there are at least n/2 leafs. I got AC with some weird backtracking, which tries to build (n/2)! different trees (but its search space is in fact lot smaller, but I can't come up with a better estimation). but after the contest I came up with a solution O*(2^n), but 4^(n/2) is in fact a better description of that :P. Consider a dp with array dp[n/2][3^(n/2)] (^ means power not xor ;) ). We divide non-leafs into 3 groups — nonactive and used, active and used, nonused and for given dp[k][mask] where mask denotes the division of nonleafs into 3 groups. This state is reachable iff we can build a forest where set of vertices are used vertices, set of roots are used and active vertices and where k leafs were used. But when checking if fixed state is reachable we have to search many states, possibly 2^(n/2). So whole algorithms runs in O*(6^(n/2)) ("*" means "*poly(n)", it is standard notation), which is in fact O(*(4^(n/2)) algorithm. Why? I will leave that to you as a nice exercise.
As far as I got you, my solution was similar, but instead of having those 3-states I was attaching children to the nodes in some order, so instead of having 3rd state I had a variable in my DP solution which shows up to which non-leaf node I have already assigned childrent.
DP[mask][assigningTo][remainingLeafs] in my solution is whether we can assign nodes denoted by mask to the nodes from [0 .. asssigningTo] interval using additional 'remainingLeafs' number of leafs. Internally when calculating this DP I was simply checking all the submasks of the given mask.
Here is the solution: 6599572
My DFS solution runs in
time. I built it based on simpler solution, that runs in: O(3n) time. Let's start with sorting nodes by number, given in input. We encode our state as pair i,j — means that we have considered first i nodes, some of them connected and mask j contains all nodes, that have no parents. First note that i is redundant, since the last one in mask is obviously the last node considered, so i equals last bit +1. Let's consider all subsets of this mask and pick each that have at least two bits set and required sum. It is known that total amount will be 3^n. And if we precalc all sums and bitcounts, we will be able to solve problem in O(3n)
Now let's remove all leafs from mask. Then we will have state i,j — we considered some first nodes and now we have i leaves without parents and inner nodes described in mask j.
All of those accepted solutions are a big shame for tests preparers:
http://codeforces.com/contest/429/submission/6599749 greedy for C
http://codeforces.com/contest/429/submission/6591828 checking pairs of points with small j-i in D
http://codeforces.com/contest/429/submission/6597823 — checking pairs of points with adjacent xs and ys in D :(
For (Div. 1) B, when brute forcing the meeting point after pre-computing the dp tables, my original solution (which got WA on test 23) checked every possible cell, including those on the border. Then, after contest, after viewing some of the accepted solutions, I changed it to only allow them to meet at interior points. So for this case:
3 3 1 1 1 1 1000 1 1 1 1
my new accepted solution gets 8, while my old solution got 1006 (corresponding to them meeting at the left middle cell and then one of them proceeding to the middle). I'm probably just missing some detail in the problem statement, but why is that invalid?
If by "left middle cell" you mean (row 2, column 1), it wouldn't be a valid meeting point because they can't get out of that cell without both moving to (row 2, col. 2), or stepping on a cell previously visited by the other person.
There was a clarification stating something to the effect that both paths have to be completely disjoint, except for the cell in which they meet.
So, in a 3 × 3 grid, the only valid meeting point is (2, 2).
Oh okay, I somehow missed that clarification, but I see it now. Thanks!
What's the solution to 1E problem. I read the code, I see what it does. However, I don't understand what is the idea behind the problem. How do I proof that doing it like this always scott_wu or SergeyRogulenko always returns a solution?
Consider a sorted list of all starting and ending points of every segment. It doesn't matter in which order we place points that have the same coordinate: see below why. Starting points of red segments and ending points of blue segments would be marked with +1, and starting points of blue/ending points of red will be -1. We need to make sure the sum in every prefix is between -1 and 1. This means the sum at all even points will be 0. This means points 2k and 2k+1 must have different signs. Also, obviously, two ends of the same edge must have different signs. We got a graph that we must color in two colors. Now note that the graph has two kinds of edges, and edges of the same kind can never share a vertex (by construction). This means that there are no odd cycles, so we will always find an answer.
The problem A div2 make me crazy!
I used O(min(abs(a[i]))n) past the problem D ....
The data for D is weak. My AC solution gets this case wrong:
1 10000 ... (2000 times) ... 10000 -5000 -10000 ... (1999 times) -10000 -5000
My AC solution: http://codeforces.com/contest/429/submission/6596958
Generator code for this test case: https://gist.github.com/jonathanpaulson/1d5fb7825395185dcd5d
It is difficult that make this problem's data. But my solution is ugly. In this case 100000 10000 10000…… (100000 times) my sulution will TLE.
I feel so stupid trying to solve E for an hour until the time ran out then doing C in 15 minutes after the contest =\
About problem 429A, a recursive version solution got RE while a iterative version passed.
http://codeforces.com/contest/429/submission/6605357 http://codeforces.com/contest/429/submission/6605261
Is this a limitation of a interpreted language, so most people chose compiled languages to do the recursion?
You seem to have set the stack to 100k, which seems to be enough at least for that particular test (but would probably fail on the maximum one). I would avoid python here. It barely works on topcoder, and they have WAY smaller datasets. If a correct solution to any problem takes half a second in C++, it would take like 5 seconds in python.
Yes,it is a huge limitation. I don't prefer to use python for a recursive solution that has a depth of more than 1000(the default recursion limit in python) ... Though the stack size in codeforces is very large, but python requires more!
In my experience:
sys.setrecursionlimit
just sets "desirable" limit. If stack space ends before this setrecusionlimit is reached, python interpreter just dies silently. Also Python reserves a lot of stack space on each iteration. In one examples of mine I needed just 3,000 recursion limit and it died on my local machine at around 2,500. I didn't even receive any error messages — python just stopped execution and finished. 100K I think is impossible for Python even with very large stack space.