Всем привет)
Сегодня состоится очередной раунд Codeforces #163 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса.
Задачи для вас подготовили авторы: Артем Рахов (RAD), Кудряшов Игорь (Igor_Kudryashov), Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за систему Codeforces, а также Марию Белову (Delinur), которая перевела условия задач.
UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.
Надеемся, что соревнование окажется удачным для всех участников. Желаем высокого рейтинга и хорошего настроения)
UPD2: соревнование завершилось, надеемся оно вам понравилось)
Поздравляем победителей:
1) Aharon
2) marcoskwkm
3) ChaosLogic
4) Imsbuno
5) Conny
UPD3: разбор задач можно найти здесь)
А почему пост не на главной?
Не успели поставить.
За последние 5 раундов(включая этот) 3 раунда были Павла.
Это не лично мои раунды, у нас целая команда, которая иногда отличается своим составом) Мы все придумываем задачи, обсуждаем и делимся идеями, в общем стараемся для сообщества)
Молодцы =)
Надеюсь задачи будут интересные!
всем успешных взломов
Im first, so i need most of neg votes.
; )
: )
last CF round of this month :(
I wouldn't be so sure:)
Considering Petrozavodsk training camp will start shortly — quite probable
I wish everyone good luck and high rating too! ;)
u will surely get some positive votes for this :P
I think that this round is going to be great. Good luck to everyone!!!
Are you the wall sockets guy?
What does that mean?
everyone's waiting for score distribution. wish well for all participants.
А я правильно понимаю, что скорость тестирования после раунда, зависит от того проверяют ли решения участников во время раунда на всех тестах, но показывают только по претестам, а потом прогоняют на успешных взломах? И если да, то от чего это зависит?
Вроде бы все решения на авторских тестах успевают во время контеста протестироваться, а после контеста тестируются только на взломах.
По крайней мере, когда мы проводили раунд, мы могли видеть настоящие вердикты всех решений, без учета взломов. Не думаю, что имеет смысл делать тестирование на авторских тестах заново.
То есть на прошлом Div1 / Div2 раунде тоже тестировалось все еще во время контеста, тогда почему же такая разница в скорости, неужели из за тестирования на взломах? И даже если только из за тестирования на взломам, то неужели их по 100+ было. И еще один вопрос, а почему бы не тестировать и на взломах заранее тоже? Ну то есть после каждого успешного взлома, прогонять все AC на работоспособность на этом взломе. Тогда в течении тестирования, вообще ничего не надо будет тестировать, а просто быстро открыть результаты.
what do you mean by dynamic scoring system??
dynamic problem scores
Its like asusual.. am right??
No, usually max. problem scores is static.
Points depend on number of solvers.
good luck evryone! :)
Ithink some of people from countries expect iran doesnt like iranian people:( becausa they give all iranian people negetive mark!
Don'be so nationalistic-thinking! first of all, that's international community. Secondly, there's no flags around your ava — that's is not the main question! :)
almost 2800 Registered participants (including ones who are not in the competition). I think this round is the one having the highest number of participants (counting people registered before contests only). anyway good luck
Does that include people who are from Division 1?
it is based on number of Registered participants, so including division 1 people (but they are out of competition)
i just count for div 2 contests only, excluding rounds with div 1.
Всем хорошего настроения вне зависимости от результата! Всем Удачи! =)
А зачем при динамической оценке сложности сортировать также по сложности с точки зрения авторов? Интересней было-бы, если бы они были перемешаны.
очень интересная D :)
it was a awful contest x(
always pessimistic, aren't you? :)
Worst contest ever,
Top 30+ solved only A, B
and guess what?! from top 30+ down to the last ranked contestant, all have solved A, B only!
i think problems are very interesting, but hard.
It is not the worst contest ever! It just too hard to Div2, but problems were realy interesing.
So when the first two problems are fucking easy and the rest three focking hard is normal?:D
I think too. It`s not worst, but for most of Div 2 participants not interesting, because they compete only in speed of coding.
It is not the worst contest ever! It just too hardLooks like the very definition of the worst contest (ok, ok, not worst ever, just very bad)
Why am I unable to see the pretest values in which my submissions failed? Did i miss something in the newsfeed?
Because the contest is still running
In the last contest I was in, I could see the test cases for which my code fails even while the contest was running.
Maybe it was practice, not contest?
It is always unable to see pretest values except tests from the problem during the contest.
Seems my memory has failed me. Thank you guys for clarifying.
2200 participants during the contest with 0 Successful hacking attempt,system testing will be so fast :)
I saw one around 5th page in standings (althrough that was from Div 1 coder)
Congratulations for the contest, the difference between place 1300 and place 100 is less than a 100 points.
как решили задачу C. Ниже диагонали
Я решил в лоб. Расставлял единички снизу вверх, справа-налево, причём, количество единичек в строке i+1 должно быть >= чем в строке i
Я для каждой строчки запомнил самый левый элемент, отсортировал. Затем для каждого столбца запомнил самый верхний и тоже отсортировал.
A-B-E-E-E...
I think that hardest problem was div1 E level.
Not really. Quite straightforward interval tree, but requires some coding. Good for Div 1 D
I don't know how can we multiplicate all numbers by (i-l+1)^k quickly. That numbers are distinct and they are not some good sequence, as for me.
Actually if we calculate
for all j up to k, we can then calculate required sum
Would you please explain this problem in more detail?? Thanks!
Let
, and 
. Then 
(you can do calculations yourself)
Thanks very much!
I think C, D, E have the correct letters assigned, but for Div 1.
Can anyone tell the algorithm for D? Be free to answer in English as well as in Russian
Интересует тот же вопрос. Вначале я просчитывал путь от каждой вершины до каждой Флойдом, затем пытался расположить кафе на всех дорогах наилучшим способом. Сначала тернарником. Работал медленно + ВА10. Потом написал вычисления наилучшего способа вручную. ВА9
Тернарник не работает, потому, что функция не выпукла. Там получается кусочно-линейная функция (зубчатая). Я думаю, что мое решение достаточно понятно для чтения
Ясно, спасибо
Только не говорите мне, что С-шка очевидная халява!
Что за 10 тест в задаче D?:(
Контест хороший, но не сбалансированный.
да авторы уже давно не говорят что он сбалансированный? думаешь почему они динамическую систему делают?) последние раунды див2, задачи выглядят ABDDE
Скорее AADDE
именно
Traditionally authors wish Successful Hacks .. Is this the first round I am seeing with no successful hacks ??
Hats off to the author for problem C. Looks so interesting and yet is so difficult to think.
D — поиск абсолютного центра?
прочитал С — подумал, какая-то мразь, а не задача, но потом норм, классная задача, жаль сдать не успел.
Расскажите решение С пожалуйста
Может как-то проще можно.
подозревал что решение не сложное и почти дошол до этого
Unexpected difficulty level was unexpected.
yeah! from rank 200 to 2000, all of them solved 2 problems and they have been sorted by their typing speed!
and reading speed!
actually in problem C we just need to sort all rows as increasing amount of 1's and sort the columns as increasing amount of 1's
note that sorting columns won't change any thing in rows and vise versa
so we don't need more than 2000 move
I missed a really important constraint no of cells having ones are no more than n — 1. :(
Sigh, I missed the second part...
Actually you can not sort in O(n) time , you have to also tell the positions which were swapped. For the second part , you can sort by any trivial algorithm for sorting in O(n*n). Note that I was missing one important thing , No of ones in columns won't change if I swap the rows. So I can just count no of ones in columns also and do the same thing as done to rows.
i think we don't need more than n-1 moves.
do not be so accurate!
I only wanted to show that sorting won't exceed the limit 10^5
it has been sorted, but it's not a correct answer.
You have to take care of equal case , If equal then do the sort lexicographically decreasing.
Why ternary search is incorrect in D?
Read above Egor's comment
Because function within edge is not convex. It is segment-linear, with segments alternating y = x + b and y = -x + b
Please explain the second part y = x + b and y = -x + b ??
Function for each edge is segment-linear (i. e. edge can be divided into segments, and on each segment function would be linear). Generally linear function is y = kx + b, but in this case k is always either 1 or -1, and this values alternate throught edge
Как-то очень странно похожи решения задачи D двох лидирующих участников 2 дивизиона...
http://mirror.codeforces.com/contest/266/submission/2989351
http://mirror.codeforces.com/contest/266/submission/2992482
Пахнет командной работой. 2989351 2992482
UPD: Уже наказали.
I think these div2-only contests are not really for div2 participants, only. I mean, they're more likely generic ICPC contests, with very easy problems and very hard problems. The final scoreboard today clearly shows that problems C,D and E are not equivalent to div1-A,B and C, as they usually are in regular, div1&2, 7-problems contest. For instance, problem D, that should be equivalent to a div1-B, was solved by 8 coders only — 6 of them were div1, out-of-competition ones. Although we know most div1 coders don't register for div2-only contests, we won't see only 6 coders solving problem B in a regular contest. So I think these div2-only contests are not really equivalent to div2 regular contests. Should they be?
edited
Yupp exactly same :P
Same codes?
http://mirror.codeforces.com/contest/266/submission/2992482 http://mirror.codeforces.com/contest/266/submission/2989351
Indentation spaces are not same :P
Nop, there is not the same count of '\t' on the two codes ;) Edit: too late :/
请使用英语。
He just asks to use english! Why so many negative??? Whats wrong with you, guys??
^ ^ Thx.I just comment for fun.
ჰე ჰეი მეც მიყვარს ეგეთები :დ
не надо ничего взрывать
Эта шутка совсем не смешна.
No, you are not allowed to drink vodka here!
Нет, здесь нефти нет.
http://translate.google.ge/?hl=en&tab=wT#auto/en/%E8%AF%B7%E4%BD%BF%E7%94%A8%E8%8B%B1%E8%AF%AD%E3%80%82
после этого контеста, у меня вознимает вопрос: через какое место/как написаны вектора? получил тле по Д, заменил вектора на массив — < 0.5 сек, я пихал 4n элементов в худшем случае, где-нибудь можно прочитать, как работает вектор?
http://mirror.codeforces.com/blog/entry/6377 Вот тут обсуждалось чуток и ссылки на обсуждение есть.
How long does it usually take for ratings to update?
It's a matter of high blood sugar, or rather it's gonna be.
Как повезло то! Не успел дорешать третью, но все равно перешел в див1!
Решил А и В -> Перешел в 1-ый дивизион. Как-то неловко и стыдно даже
Аналогично, причем я знаю что мой уровень это не Див1, скорость набора решает )
решил три, остался во 2-ом дивизионе:)
I think this contest is really a coding speed test for div 2 participants. I finished the first two problems less than 10 minutes. After that, I read the description of problem E. At the first glance, I thought it had something to do with segment tree. However, right after looking at the sigma notation, I just gave up. I played 2 games of League of Legends.
And surprisingly my rating still increased after the contest.
And i played 2 games of Dota :D
Could anyone tells me, why dis the problem D can not use Ternary Search Algorithm ? I alawys get wrong answer on test 36 ! Many thanks ! this is my
my code links : http://mirror.codeforces.com/contest/266/submission/2993280
You should read egor's comment.
You should divide each edge into several segments, and use ternary search on every segment. Just like what Egor have mentioned above. And you can also see more details in my submission. 2995464
No need for ternary search, actually
Yes, you are right. I found the function within each segment is unimodal, so I used ternary search to find extreme points, but I did not realize that it is possible to get extreme values by direct calculation. Thank you so much. I will correct my solution.
почему, например, этот код не получает RE при n=50? код. у меня он падает на MS VS C++ 2008
? Массив от 0 до 49 включительно, при n=50 цикл покрывает четко эти границы — от 0 до 49.
там же при i=49 обращаются к элементу a[i+1], т.е. к a[50]. Разве нет?
ну ну, а '\0' символ? для строк нужно выделять len+1 массив, последний элемент — как раз для нулевого символа
There is a grammar mistake in problem C. Some cells (n - 1 cells in total) of the the matrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:
please give me some hint about problem D ?
Geralt' черт соска не красива делает