Всем привет!
Сегодня состоится очередной codeforces-round. Он пройдет в обоих дивизионах, в каждом из которых будет предложено пять задач разной сложности.
В его подготовке, принимало участие несколько человек: KAN, fdoer, Skird, tunyash. Огромное спасибо Gerald, за координацию подготовки задач, множество клевых идей и понятизацию условий. Так же благодарю MikeMirzayanov за отличную систему подготовки задач, Delinur за перевод условий.
Надеюсь, все пройдет гладко и вам понравятся задачи. Про разбалловку вы узнаете перед контестом.
Удачи!
UPD: разбалловка стандартная (500-1000-1500-2000-2500) в обоих дивизионах.
UPD: появился очень кратенький разбор
UPD:
Поздравляю победителей! div1:
div2:
UPD: есть полный разбор на русском.
Надеемся увидеть хороший контест с интересными задачами)
На прошлом контесте была обычная, значит, сейчас динамическая.
Будут суровые челябинские задачи? = )
Вроде, в прошлый мой контест кто-то так уже шутил :) Но он был не из Челябинска.
Похоже что так и есть :)
Score distribution?
Will be announsed in a few minutes before the start of the contest.
я смотрю, tunyash понравилось раунды делать
Давно хотел спросить, а почему информация о разбалловке в анонсе часто публикуется лишь за несколько (15-20) минут до начала раунда? Это делается с какой-то определенной целью? Или же создатели этих раундов настолько долго решают вопрос о стоимости задач?
Скорее второе. Никто особенно не задумывается о разбалловке, пока участники не спросят :)
А что Вам даст знание разбалловки за, скажем, 5 часов до начала контеста? Это поможет Вам лучше подготовиться?)
Надеюсь задачи будут интересными и из них можно будет узнать много нового.И хотелось бы пожелать всем удачи и высокого рейтинга.
usually every time they say : Score distribution will be announced a few minutes before the start of the contest.
it will be dynamic :|
You are missed :D
I wouldn't be so sure.. Well, the organizers have to intrigue us by anything, including the score distribution:)
Standard! :)
Зарегистрировался в втором дивизионе, затем проверяю списки участников(зарегистрированных с одного дивизиона), а там меня нет. Как так?
Как же нет?
Лично я не нашел
Я нашел на 4-ой странице.
Мне кажется, или автор переборщил со сложностью?
Хотя мы в разных дивизионах, думаю, что не кажется.
Мне тоже так кажется (после контеста скажу пару доводов, по которым я не стал решать задачи).
да ты просто задач очканул, так и скажи
-
Я не понял: с какой стати обращение на "ты"? Мы друг друга знаем?
Из двух слов "ты" и "очканул" тебя больше смущает первое ?:)
плюсую!
И со сложностью проблемы, и с балансировкой тоже.
Еще с серваком не все ок. Очереди на тестирование по 10 минут. Вкупе со сложностью просто сносит башню :)
Первый мой контест в первом дивизионе — и ни одной решенной задачи :( Надо больше практиковаться.
Согласен.Без практики никуда.Но и теорию надо знать)
Согласен, грубо говоря 10/2000 = 0.5% участников решили D. Про Е я молчу. Довольно сложный контест по сравнению с предыдущим :)
P.S.: Речь идёт о Div.2
Крутые же задачи.
Сами задачи мне очень понравились, но вот сложность довольно завышена
Задачи хороши, но не для этого контеста :)
Any ideas on what is so special about Div 1 Task B Pretest 3?
The same question about Div 1 Task C :)
ответ:
Спасибо. Все оказалось банально: int вместо long long...
клевый контест, жаль только, что задачи выше В перегробили
Как решалась D(div 2). Я вывел какую-то формулу, если k<=n, то c(n*n,k)*(m-n+1)-c(n,k)*(m-n). Верна ли она?
Мне кажется, или в A div 1 можно было не писать, что не требуется минимизация числа вершин? Решение от этого вроде бы не поменяется ведь.
Ну мое бы перестало работать например. Оно ровно 100 использует на худшем тесте. 97560. Рекомендую проверить. Он забавный.
хм... у меня 87...
Потому что к тебе кэп пришел два раза, а ко мне один.
У некоторых 98756.
Ну они про одно и то же.
Не думаю. У меня некоторая конструктивка, относительно которой я не умею доказывать, что с меньшим числом вершин сделать нельзя. Если бы это условие было, многие потратили бы куда больше времени на доказательство.
Строго я и свое не умею доказывать :) Но кажется, что оно дает минимальное число вершин.
У меня на худшем тесте было 101 вершина: я делал добавлением групп почти полных компонент и у меня возникала проблема в больших тестах (их много, но например 99994), где в конце мне нужно было добавить 3 треугольника, а на это уходило по моему алгоритму 7 вершин, пришлось написать ручками, чтобы было 6 вершин и тогда полный чек не выявил косяков.
Ну да, посмотрел решения других участников и увидел, что не все писали минимизацию. Я думал, что простая жадность после постройки максимального полного графа + добавление нескольких треугольников выйдет за лимит вершин.
задачи хорошие, но сложнее по сравнению с прошлым контестом.
как думаете: задача С Div2 -- комбинаторика
Я жадный алгоритм использовал, вроде должен работать
нет
Моя жадина прошла:-)
Не похоже на комбинаторику.
Ideas for Div2 D ?? I was finding out a pattern that if I fill some N sized array by some arrangment , The same thing I could do with next N + N arrangement . This was going for matrix exponentiation. Altough I could not completely formalize it.
Was I going in the right direction ?? Or there is some other way ??
Lets define F(C) as the number of colored cells in column number C. IMHO, the key observation is that F(X) = F(X + N) = F(X + 2N) and so on.. DP solution can be found, but I failed on pretest 3 as mentioned above.
You mean to say that we could find F(X) by using DP and rest we have to do is exponentiation of F(X) by ceil(N/M)
We can use dynamic programming here .
state would be [cur_pos(0...n-1)][rema(0....n^2)]
base case : dp[n][x] = 1 if x= 0 dp[n][x] = 0 if x!= 0
recurrence : dp[i][j]= sum over x=0 to min(j,n) pow(nCr(n,x) ,ceil( m/n ) ) * dp[i+1][j-x]
P.S : need to make sure that we don't use pow function every time and need to memorize it as base can have at most 100 distinct values
Мне одному Джон Доу кого то напоминает?
http://ru.wikipedia.org/wiki/Джон_Доу не он ли это?
Мне он напомнил героя из ПЛИО.
ПЛИО это конечно круто, но я вспомнил маньяка из к/ф Семь
Не этим ли псевдонимом пользовался Доктор Кто?
Фильм "Семь"?
For div2-A, when n = 3, "2 3 1" seems like a perfect permutation, is there any mistake I made?
P[P[1]]=P[2]=3 which is not equal to 1 as question says P[P[i]]=i
OK, I knew my mistake now, thank you all!
It is wrong , P[3]=1, But P[1] != 3
No, i = 1. So, P[P[1]] = P[2] = 3, but it must be 1, as phantom11 said.
here p[p[3]] = 2 which is not equal to 3!!!
D — суфмас + дерево отрезков + структура, которая говорит, сколько на отрезке чисел, меньших данной? Хорошая задача, но, на мой взгляд, условие про непересечение явно лишнее. Оно не делает задачу более идейной, но прибавляет 10-15 минут тупого кодинга дерева, которого в этой задаче и без того предостаточно.
суфмас + фенвик + спарс. Мое решение не меняется от отсутствия условия непересечения.
отослал за минуту до конца, получил ТЛ6
но в целом не обидно, потому что времени не было нормально писать, наверняка и так где-то набажил..
досдал в дорешку :)
Опровергните идею по Е.
Будем решать в оффлайне. Зафиксируем некоторый столбец и будем рассматривать все запросы, которые начинаются в нем. По очереди рассмотрим столбец (больший или равный данного), в котором запросы будут заканчиваться. При этом считаем динамикой для каждой ячейки второго столбца минимальную и максимальную клетку первого, из которых можем добраться. Плюс ко всему считаем массив "можем ли мы добраться хотя бы до какой-нибудь клетки второго столбца из клетки i первого". И будем обрабатывать запросы следующим образом (на момент, когда первый столбец совпадает с началом, а второй — с концом): если из клетки-начала вообще не можем дойти до второго столбца — No, иначе рассмотрим минимальную и максимальную ячейку в первом столбце, из которых достижима нужная (во втором столбце), если текущая клетка лежит между этими двумя — Yes, иначе No.
Я неудачник! Если в посылке, которая была на контесте, поменять компилятор на GNU C++, то решение получает AC :(
Упс. А почему это работает? то есть, если клетка лежит между двумя достихжимыми, почему она тоже достижима?
Там еще есть условие, что из клетки можно добраться до какой-нибудь клетки второго столбца. Тогда рассмотрим этот путь. Если он не идет в необходимую клетку, то он в любом случае пересекает либо путь от "минимальной" клетки, либо от "максимальной", а соответственно, по объединенному пути можно добраться до необходимой клетки.
а, понял, классно. получается qn? у нас было более сложное решение.
Скорее O(q + n*m^2).
кто-нибудь, кроме меня тестил свое решение на всех тестах?
Я думаю, так делал автор контеста.
По А? Я тестил. После сабмита, разумеется. С чекером за куб заняло минут двадцать, как раз хватило на написание B.
как решать Б лучше, чем n4?
Мой n4 в запуске работает 1.6. Ключевой оптимайз — избавиться от быстрого возведения в степень, преподсчитав все {Cni}m / n.
ну это само сабой, хочется еще быстрее (видимо не дп)
Я не умею. Я долго думал, но не придумал. Попробуйте, вероятно, я чего-то не увидел.
n4 заходит. Самая медленная операция – это (m % n), но её можно сделать один раз.
Я, вроде, умею. В моем коде третий цикл легко заменяется частичными суммами. Разве так не у всех?
Оп, как? Там же на разные степени цешек разные состояния динамики умножать.
Спасибо за раунд, очень понравился) И поздравляю автора, вы выиграли в соревновании: Кто сложнее придумает контест :)
System Test still pending :/ ... I am too anxious!
Спасибо за интересный контест! Побольше бы таких.
how long does it take generally for system testing to complete?
I have seen very few system testing before. In my experience they all took around one hour. But today's system test seems really fast. I guess it will be done in half an hour. It's a new experience :D
Testing is so fast today
And now it's slow.
It seemed to have slowed down at the end...
Я все понимаю, люблю интересные задачи, понимаю нелегкий труд проблем-райтера, но это реально чересчур сложные задачи.
Was difficult
2343173
Random? Или в этом есть какой-то смысл?
Зарегились 603, хоть что-то посылали 371. Только 60% писали раунд.
вот таких людей много
Very difficult div. 1 problems! Even for tourist, rng_58 and Egor!
Score distribution should be 500 — 1000 — 2500 — 2500 — 2500 =)
500 was not usually 500... It was difficult and not trivial. So, I think that score distribution should be 1000 — 1000 — 2500 — 2500 — 3000;(
Контест получился хорошим.Я узнал много нового.
Ох уж этот 12 тест к С...
Всех, кроме tourist, в Div 2! Даже оттуда не все задачи могут решить!
Solved only AB and second place...
congrats!
wuhao21 solved AB and 161st place! :\
so interesting XD
Does this describe your feelings? :-)
Muhaha ...
GJ man
It's the trend! There was a contest last week where Egor solved only 250 and came first :P
Problem setters are trying to make problems harder and harder, while the number of reds are becoming less and less :)
And ASPIRINKA hack :) Without this you should be 12st :(
That sounds crazy..... Next Div I round is written by me >_<...I promise it's VERY EASY LOL...
So bad for me, my train from Saratov (we participate in ACM ICPC competition there) arrives home just one hour before contest and I won't be able to come home in time...
Everyone in China knows difficulty of YuukaKazami's contests. I'm not saying that they are "very easy".
orz
I thought that problems is not so hard. About ten people solved C, but there were many pitfalls in it. One guy solved E, but he had some bugs too.
ooops...
По моему пора на сборах вводить контесты от участников....
и давать преподам?
ребята не зря съездили в А0, однако
past contest is much easier than this for div. 2
Тупорылый контест
мало решил?
"Ужасный контест. На самом деле, очень плохой контест. Я думал намного лучше будет, намного лучше будет все и очень плохой контест, просто очень плохой контест. Я думал намного лучше все будет. Сколько раз решать ходил! Было намного лучше. Ну на этот раз как-то не удалось. Во-первых решил мало, да и контест не очень."
По-моему что-то случилось с сервером, т.к. уже ооооочень долго тестируются последние 2 посылки...
Screencast. Начиная с 24й минуты тот еще треш
Открывать вкладки в новом окне быстрее щелчком средней кнопкой мыши :)
Спасибо, кэп. На тачпад не завезли
Ещё можно удерживая Ctrl нажимать по ссылке левой кнопкой.
Тогда тачпад иногда интерпретирует перемещения мыши как движения колесика, и начинается фантасмагория с размером шрифтов
Во-первых, то шутка была, во-вторых, раз уж это так тебя задело, есть Ctrl+Click.
Peace. Меня это не задело, мне просто такой комментарий показался странным
А чего тут странного? Просто первая мысль, возникающая при просмотре этого скринкаста :)
На самом деле кое-куда завезли, срабатывает при нажатии двух кнопок одновременно.
Is there someone who can tell me the direction to solve Div1.C ?
Vertex |D(n-1)| + 1 is cutpoint. Because of this, if min(a,b) <= |D(n-1)| + 1 and max(a,b) >= |D(n-1)| + 1, path will contain |D(n-1)| + 1. We should solve same problem for pair (a, |D(n-1)|) (a, 1) (b, |D(n-1)|+1) and graphs with orders k-1, k-1 and k-2 respectively.
Hi, Div2 judge is stuck. please fix it. thanks
А по C предполагалось решение быстрее чем за O(t*n)?
да,
.
Все я понял я тупой надо было просто брать min(n, 80) :-(
Upd: прошла((( я реально тупой Upd2: кстати спасибо за раунд. задачи клевые
НЕ могу понять почему в задаче С ответ на тест где n=6 и a=1 и b=13 ответ 2.
Есть путь 1-14-13.
При n=6 количество вершин 13, разве не так?
1 вершина для n = 0
При n=6 количество вершин — 21, 13 вершин — при n=5.
Hi, I have a doubt in C div 2. For k = 3 why I can not draw a graph with 4 nodes and these relationships, (1 — 2 — 3), (1 — 2 — 4) and (2 — 3 — 4). Maybe I did not understand very well when statement says "A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". Thanks in advance.
Then there will be cycle (1-3-4) and in total there will be 4 cycle but not 3.
Thanks, I got it!!!! Have a nice day.
Try to draw this graph. To have cycles 123, 124, 234 you need edges 13, 34, 41. Which creates a new cycle 134.
Thanks!!!
"A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". 1 is connected to 3 (from 123), 3 is connected to 4 (from 234) and 1 is connected to 4 (from 124), so your graph actually have 4 cycles of length 3 (123,124,234,134). CMIIW!
Edit: sorry for reanswering a question, when I write this hza's and BOBAS' comments aren't there yet!
Thanks!!!
Did anyone else had a problem when challenging? I challenged someone and the verdict was something like "Judgement protocol not found or unavailable." This lead me to try to challenge the same code again, but then the previous challenge turned out to be unsuccessful... There goes 50 points :(
Или мне кажется, или в первом дивизионе переборщили со сложностью задач.
Хотя нет.Задачи хорошие.
is this contest unrated ?
I don't think so
There is no reason to be unrated !! hard problems isn't acceptable reason as i think ..
2 problems with no one solved them during the contest for both divisions!!! seems strange !!
Можете объяснить, почему моё решение 2348402 по D (Div 2) не заходит в тайм-лимит?
In div2 problem B , Can it be solved using binary search (for finding the value of x) ?
I think no , because binary search property isn't applied here as there is no value of x the equation is true above and false below
I don't think so.....
x^2 + s(x)*x
x = 8, 8^2 + 8*8 = 128 ; x = 9, 9^2 + 9*9 = 162 ; x = 10, 10^2 + 1*10 = 110 <- It drops here ; x = 11, 11^2 + 2*11 = 143 ;
If the increase in value was uniform, then we could have used binary search. But now we can't be sure on which half the correct value lies.
I believe you can't, since it's perfectly possible to have x * x + x * s(x) > y * y + y * s(y), even though x < y. For example x = 9, y = 10 : 9 * 9 + 9 * 9 > 10 * 10 + 10 * 1
yes, if you use some delta to check the rightness of answer. my solution here
the binary search in your solution isn't responsible for the result .. the loop after the binary search do all the work i think !
binary search lowers the answer interval to [x-delta; x+delta], it is simpler than some solutions where is the answer within [sqrt(n)-delta; sqrt(n)+delta]
Слишком трудный контест для див2
I'm happy ... +149 points!!!
Me too. I was progressing during four last contests, I gained 317 points in total and finally I'm in the first division :).
не смотря на то, что я не люблю графы, контест очень даже понравился
В задаче С div2/ A div1 не слишком слабые тесты?
Конечно, трудно угадать все решения участников, но делать набор тестов с N= 1..12, 99000..99025, 99999,100000 и еще 4-5 случайных тестов — маловато.
Например, моя эвристика падает в TL на тесте N=112.
upd. Минусуйте меня, я не то решение гонял на тестах... Финальное проходит и N=112, и все, что я в него догадался пихнуть, проблема снята.
ну вот. это плохо, конечно. я просто не видел особых решений, помимо своего, поэтому не было особых соображений о том, какие надо делать тесты. а у вас там совсем что-то хитрое. соглашусь, это косяк.
Максимум времени на тест — 1сек, всего возможных тестов 5*10^4. Немного терпения — и за 14 часов вы узнаете точный ответ на свой вопрос. )
Чего 5*10^4, разве не 10^5?
Запамятовал условие. Ну значит 28ч, суть не меняется.
Просто основное что нужно проверить, это правильность построенного графа и не использовано ли более 100 вершин. Первое проверяется случайными тестами и максимальными, второе проверяется максимальными (ну то есть например 99994). А то что у вас падает на N=112 это просто что-то очень специфическое, что в данном случае просто очень сложно обнаруживается.
Я не говорил о том, что надо в набор тестов включить все 10^5 вариантов. Но, чтобы повалить часть "специфических" решений, можно вместо 46 тестов сделать 100 и в появившихся накидать разного хлама (если не осталось осмысленных вариантов). На скорость финального тестирования это повлияет не сильно, а проверка будет полнее (имхо).
P.S. Это очень странно, что моя задача работает больше 1с на тесте N=112, но мне лень прогонять её на всем диапазоне. Хотя и есть шанс, что на "средних" тестах оно будет валиться часто.
Looking forward to the editorial.
That moment when No one could solve C&E(Div. 1) :
Problem Designers: Problem??
will the Editorial be published?
it's published
всем удачи во всех ваших делах )