Привет, Codeforces!
8 апреля 2016 года в 18:00 MSK состоится очередной одиннадцатый учебный раунд Educational Codeforces Round 11 для участников из первого и второго дивизионов.
<Изменения в последенем абзаце>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.
Не стесняйтесь присылать как простые (и даже очень простые), так и сложные задачи (но обязательно интересные). Просьба присылать задачи к которым вы знаете решение, с понятным условием (наличие легенды исключительно по вашему желанию), а также сопровождать условия одним-двумя примерами, чтобы можно было быстро убедиться в правильности понимания условия.
</Изменения в последенем абзаце>
Комплект задач был предложен участниками сообщества. Задачу А предложил Ali Ibrahim C137. Задачу B прислал Srikanth Bhat bharsi. Задача C предложена Mohammad Amin Raeisi Smaug. Задачу D очень давно прислал Sadegh Mahdavi smahdavi4. Задача E является последней (четвёртой) из предложенных пользователем Lewin Gan Lewin. Задача F последняя (если не ошибаюсь третья) из присланных пользователем Kamil Debowski Errichto.
Благодарю их и всех кто присылает задачи! На данный момент я прочитал и ответил всем кто мне присылал задачи (кроме, возможно, присланных в течении последней недели). Надеюсь я никому не забыл ответить, все задачи у меня записаны и я о них не забываю.
Задача F подготовлена пользователем Kamil Debowski Errichto. Остальные задачи подготовил я (Эдвард Давтян). Спасибо Маше Беловой Delinur за проверку английских текстов условий. Задачи вычитывали и тестировали пользователи, предложившие их, соответственно Ali Ibrahim C137, Srikanth Bhat bharsi, Mohammad Amin Raeisi Smaug, Sadegh Mahdavi smahdavi4, Lewin Gan Lewin, Kamil Debowski Errichto. Большое им за это спасибо!
На раунде вам по традиции будут предложено шесть задач. Надеюсь они вам понравятся! В данный момент я рассматриваю возможность повторения задачи E с большими ограничениями, в качестве задачи G. Как вы смотрите на такое?
Good luck and have fun!
P.S.: Тот самый автобус из задачи B.
UPD 1: Взломы идут полным ходом. Разбор задач на русском языке готов.
UPD 2: Соревнование закончено. Поздравляю победителей tribute_to_Ukraine_2022 и uwi! Также поздравляю halyavin с победой в гонке хакеров — 93 взлома!
After looking at bus, I thought problems will be about Scooby Doo!
I hope you would all benefit and learn something new from my problem :D
Good Luck and Have Fun!
Well, I barely solved all problems the last time. I will unlikely have time to solve another one.
Is that a necessary condition for contest to be good to have sufficiently easy problems so that you can comfortably solve all of them :P?
Actually I think this time the contest will be a little easier than usual. The problem E can be solved for larger constraints, so it is not an another one, it is the same with larger constraints :-)
I'm always thinking that educational round is prepared for my next rating-increasing round.
Я считаю, что если решения на задачу будут сильно отличаться (из-за больших ограничений) то вполне хорошая идея сделать и задачу G.
How to solve F?
How to solve E?
After a bit of observation (actually I just write every sequence for n = 2, m = 3), I get this recurrence: f(i) = f(i - 1) * (2m - 1) + mi
Answer is f(n) + mn
Oh，how to find it? I can't understand it.
why (2m-1) ??
For E, wrote a bruteforce solution and looked at few answers for small values. Then found very simple relation when N increases.
Alternatively
f[n] = (3 * m - 1) * f[n - 1] + (m - 2 * m^2) * f[n - 2]. Worst part, I calculated the coefficients but did not believe in them.My solution
Nice! How to get the first formula and how to transform it into second?
It is the author solution. I'll post the editorial soon.
can I find out whether declared the best crackers?
http://static.md/000ba9bca1e2a135b53a7868a29932f6.png
How do you figure out that "simple relations"? :D
I've also bruteforced for M = 2, OEIS'ed it, and found a similar formula.
When I fixed M = 5, increasing N seemed to multiply the result by 9, and looking at remainders showed powers of 5. For M = 7 multiplier was 13, so it is 2m - 1.
This was the first time I wrote CHT which works correctly on the samples :D BTW, how to solve E?
what is CHT?
convex hull trick, maybe?
Yes, convex hull trick :)
F?
Yes.
If you want to try, attempt to find a simple closed form for E. You can then solve this if n,m <= 10^9 instead.
One can just use fast power algorithm.
In F I was getting WA on test 29 and then changed double to long double to get accepted :(
It was supposed to be solved with 64-bit integers.
Yeah, I put long long after getting accepted with long double. It's just my first time with CHT and I was trying to be fast so simply put double everywhere and then I saw I need it only when computing the intersections' X coordinates :)
I got hacked on A for the stupidest reason ;_;
What?
I got hacked because the integer I inserted is the largest prime<=10^9 which was I think 99999931. But I should've inserted 1.
you can simply insert 1 .... because it is co-prime with any number
Нашел ответы для мелких тестов и подобрал формулы для динамики — понятия не имею, почему она работает так.
dp[1] = 2dp[i] = dp[i-1] * (m*2-1) + m^(i-2)ans[i] = m * dp[i]Could anyone explain me why this code gets TLe for problem D? 17241743
tl;dr
How to solve C in O(n)?
You can use two iterators — left and right border.
You will have the best answer only if you changed zeroes such that after this action you get one long line.
So you can move right iterator while
countOfChangedElements <= kWhen
countOfChangedElementsis more thankyou should move left iterator whilecountOfChangedElements > kOn each iteration you should update an answer (if
(curAnswer = r - l + 1) > maxAnsweryou should updatemaxAnswerandmaxL, maxRindexes, because you will also need to print a resulting array)Two Pointers.
If you decide to convert segment [L , R] into all 1's , the operations required would be the count of 0 in range [L,R].
We can then extend the right pointer until the count of 0 does not exceed K.
I did it in nLogn should also pass
Thanks :D
You're welcome :p
When the hacking stage will start ?
It has started.
Забавный факт про GNU. Вот две идентичные посылки:
Секрет в том, что в этом коде используется std::unordered_map. Заменим std::unordered_map на std::map:
Казалось бы, unordered_map должен работать немного быстрее, что и происходит на Visual C++, а вот GNU ведет себя странно.
Только при условии использования нормального хеша. Тот, что в указанном сабмите плохой.
Пример с исправленным хешем: 17245178 (GNU C++11, 2058мс).
То же самое решение работает за 1500мс в Visual C++ 2010. На самом деле основной секрет в том, что то, что заявлено как GNU C++11 — это на самом деле MinGW, и у него есть проблемы со скоростью кода.
Кстати, есть ли причины, по которым на Codeforces нельзя использовать современный нативный С++ — компилятор? Например, Visual Studio 2015.
Хэш-функция, конечно, плохая. Например, при равных X и Y у вектора, хэш будет всегда давать 0. Но это свойство не зависит от стандартной реализации хэша для int. Поэтому и возникает вопрос, почему Visual C++ справляется лучше, пусть даже на небольшом конкретном наборе тестов.
По поводу MinGW можно пруф, для меня это новость... Это получается чекера на linux вообще не существует, и все тестируется на windows? Иначе какой смысл в MinGW?
Касательно Visual C++ 2015, он еще не полностью стабилен, багов много, их активно фиксят в апдейтах. Хотя я бы от него не отказался. Можно было бы 2013, там поддержано значительно больше функций С++11/14. Единственный косяк, там нет поддержки move-конструктора по умолчанию (это влияет на правила генерации других конструкторов), но это не особо критично.
Возможно, в студии другая имплементация хеш-мапа, с лучшей константой в случае коллизий.
Про компиляторы есть в правилах: http://codeforces.net/blog/entry/4088 Насколько я понимаю, все тестируется на windows.
Я пишу в VS2015, каких-то очень критичных проблем в смысле спортивного программирования пока не замечал. 2015 еще хорош тем, что у него есть Community Edition. Я не юрист, но мне кажется, что его можно бесплатно использовать на Codeforces.
How to solve D: Number of parallelograms http://codeforces.net/contest/660/problem/D ?
for every pair of points (xi, yi), (xj, yj) we find midpoint (xi + xj) / 2, (yi + yj) / 2. Now for all midpoints we make map cnt[(x, y)] — count of pair for which (x, y) — midpoint. Answer is sum (cnt[(x, y)] * (cnt[(x, y)] — 1)) / 2 for all (x, y) in map.
Can you explain further more ?
Hello,
my version is almost similar, see here — function "par"
The thought is, to do "vector addition" from all pair of points, and store them somewhere (in an array — "R" in my case).
Here, we can sort it (or as Naduxa said, store it in the map) and find number of "pairs" which can make parallelogram. The pairs, which can do so are those pairs, which are "equal". So now, we know the number of those (from the sorted array /or/ map) and use Gauss's formula (given above) == N*(N-1)/2
Hope it helped a little bit ^_^
Good luck — feel free to ask additional questions :)
Can you please explain how to get the formula N*(N-1)/2? Thanks
The number of pairs out of N items is equal to the number of ways to choose 2 items out of N items. With knowledge of combinatorics, we get N(N-1)/2.
There is an alternative way. Recall that 1+2+...+N equals N(N+1)/2. The first item has N-1 items to pair with. The second has N-2 items to pair with, for the first item has paired with it already. And so on, until the last item which has zero items to pair with; all of the previous items have already paired with it. Therefore, there are N(N-1)/2 pairs in total.
А зачем до окончания фазы взломов в тесты к задаче D добавили тесты из взломов?
Можно узнать будут ли объявлены лучшие взломщики ?
weak test cases on A ?