Всем привет. Меня зовут Михаил Тихомиров, и сегодня я — автор раунда. При подготовке задач мне очень помогли Геральд Агапов (Gerald) и Артем Рахов (RAD), условия на английский язык перевела Мария Белова (Delinur), за что им от меня огромное спасибо.
Сегодняшний раунд пишут участники из обоих дивизионов. В каждом дивизионе пять задач, задачки будут пересекаться, в общем, все как всегда. Разбалловка задач в каждом дивизионе сегодня также стандартная (500-1000-1500-2000-2500). В общем, самый обыкновенный раунд. Или нет?.. =)
Надеюсь, что задачки будут интересными, тесты — надежными, сервер — быстрым, решения — (в основном) правильными, а раунд — рейтинговым. =) Желаю всем удачного выступления!
Раунд завершился, всем спасибо!
Результаты:
div1:
div2:
Теперь полный разбор здесь.
Спасибо! Желаю всем хорошего раунда! Чтоб после раунда никто не шел топиться из-за забытого else)))
Thank you Endagorion~
Всім удалого контесту!!!
Господа, представьте, сколько должно было произойти случайных событий во Вселенной, чтобы кто-то оставлял здесь комментарии с целью заполучить рейтинговые очки! =)
Желать удачи можно и искренне. Разве это делается ради очков
Да ладно? Наверное, это вы тролите так:)
Заинтриговали :)
Wish you best of luck! ;)
Классный раунд, и задачи хорошие, и багов не было. Побольше б таких.
Когда будет разбор?
Делал D с помощью факторизации чисел через решето эратосфена и масива на N сетов. Асимптотика O(7 * M * logX) , Х — размер каждого из сетов, не могу оценить точно. Это зайдет?
а размер не максимум 1?
Допустим простой делитель — 2. И у нас вставляется 2, 4, 6. Тогда во втором сете у меня будет 3 элемента. Как можно было от этого избавиться? Просто если потом приходит запрос на удаление двойки, то не придумал, как запихнуть на ее место четверку.
Если вставили двойку, то ни 4, ни 6 вставить не удастся.
Ой, точно. Блин, как я так...
Вот я... барашек)) Тем не менее, классный раунд!
Тогда такой вопрос. У меня массив на 100 000 сетов. Значит он сначала вызовет 100000 конструкторов или это происходит как-то иначе?
вызовет
Не знаете, насколько это медленно?
Ну если массивы одного размера, то понятно, что не зависит от входных данных и если успел при мелких веротяно успеет и потом.
Это нормально.
ахринеть. у меня отключили свет на экваторе раунда, раздавал инет с телефона на ноут, оба из которых почти разрядились. сейчас посмотрим, что из написанного в такой экстремальной ситуации пройдет)) UPD ну хоть D зашла, отправленная в последние минуты:) хорошо:)
<GRAMMAR_NAZI> ахринеть — это когда в одном слове "ахринеть" две ошибки </GRAMMAR_NAZI>
Спасибо автору за интересные задачи,побольше бы таких! Жаль что времени мало=)))
Thank you Endagorion, nice problem set! Especially loved the Flatland Fencing (problem D in Div1).
А тесты использованные во время взломов будут в финальных тестах присутствовать?
В задаче D (div2) претесты можно было пройти совершенно различными решениями. Не знаю, пройдёт ли моё решение все финальные тесты, но у меня удалось сделать первый успешный взлом :)
4 взлома тестом:
+ 100000
— 100000
И так 50000 раз =)
в тестах С есть тесты ломающие хэши, а то весь контест просидел, думал как без них, оказалось, многие так и посдавали?
Как решать эту задачу без хешей?
если бы я знал, думаете, я бы не сдал?)
Свой вопрос я хотел направить сообществу, раз уж появилась ветка об этой задаче =)
сам решение не писал, ибо опоздал на раунд на 5 минут =_=
как без хэшей — ну бор же. для каждой вершины находим списки соседей, сортим их и пихаем в бор. только на ребре будет уже написан не символ, а число. для скорости бор, видимо, на хэш-таблице надо писать.
итого точное решение за O(MlogM) с маленькой константой
upd. что то переходы на новую строку криво обрабатываются...
Я написал решение с хэшами с 3-мя модулями, но мне почему-то кажется, что есть и нормальное решение.
да да, мне почему-то тоже так кажется
Разве сортировка вершин по списку соседей не заходит?
Это было первое, что пришло в голову, но я как-то побоялся такое писать.
Это же codeforces :)
вроде должно заходить, в сумме же O(MlogM)
UPD TL :(
Если мы про div.1 C, то что если у тебя будет как-то так:
Вот же блин... Массив маленький... А такое проходить должно.
В природе существуют тесты, которые ломают хэши?оО
В природе есть программы, которые генерируют строки с равными хешами при заданой базе за несколько минут:) Но тут еще нужна была равная длина, так что тьфу-тьфу ...
хм, я подумал, что хеши легко валятся, и написал мапу от упорядоченного списка соседей. вроде на грани, но надеюсь, что пройдет
Задачу Cubes вроде нельзя хэшами пихнуть
можно, я лично запихал ее туда по 5 (приврал с 10) хэшам вроде)
В этой задаче спокойно заходит, если брать не по модулю INT64, а по большому простому.
Оказалось, есть такие тесты :( Поподбирал основание, зашло в дорешку.
Один я каждый раунд плохо читаю условия,и из-за этого теряю мест 60 и более? и да раунд действительно классный,автору море лучей добра)
От раунда к раунду будете читать условия всё внимательнее :)
Неприятное (для меня) новшество в системе: когда в коде есть "%lld" в любом месте, посылать очень неудобно, так как выскакивает предупреждение в стиле «вы, вероятно, не умеете выводить int64», перезагружается страница (то есть Back к задаче придётся идти на одну страницу дальше), нужно опять выбрать файл и опять нажать на кнопку. Ещё почему-то при этом иногда лочится посылаемый файл на диске (браузер Firefox), а иногда при нажатии на «Отослать» выскакивает страница с текстом «Access denied».
С таким кодом
я хотел бы сам отвечать за то, умею ли я выводить 64-битные целые числа. Хотелось бы иметь галочку в настройках, чтобы отключить эти неудобные предупреждения.
Можно попробовать
Да, спасибо. Это мне уже предлагали. Но я не хочу писать нечитаемый код. Я хотел бы, чтобы эта проблема была решена более цивилизованными средствами.
Кстати, в VS2010 проблемы больше нет (да и в одной-двух предыдущих версиях, похоже, тоже), равно как и в последнем MinGW. Дело остаётся за малым — обновить софт на Codeforces и/или убрать предупреждение о
I64. А тогда уже можно будет навсегда забыть про всё это и писать код так, как указано в стандарте.А если сдавать под вижак? Вроде оба варианта должны работать
В задаче B(Div 1) нужно было считать, что пока №1 работает — нельзя включить никакие другие?
В условии: "два числа взаимно просты, если их наибольший общий делитель равен 1". Так что нет.
Нет(т.к НОД(1, а) = 1)
По данному определению 1 взаимно просто с любым числом.
Эм, почему? 1 взаимно прост с любым числом, так что его можно включать/выключать когда угодно и при нём можно тоже включать (если не противоречит остальным).
Хм... Какие-то опасения у меня. 2й див начал тестироваться, а 1й ещё нет... Вероятно какие-то проблемы в 1 диве.
UPD. Ок, успокоили. :)
да вроде как обычно
На прошлом контесте так же было — сначала див 2, потом див 1, это наверно сделано специально, чтобы система меньше глючила.
I must say, C of Div.1 is very very unusual for me > <
Anyone could explain the hash-based solution to problem C? It seems to be very intersting.
When will the system test start?
After div2 testing finished I think. Today div2 got test first :)
OK, still far from being red. Nice problem set, anyway I hoped I could do it better.
I just opened solution of zzy_troy for 155D - Colliders. And his solution happened to be the same as resubmited solution of dnc1994 after I challenged him.
Check it out: 1225624 1228387.
I think "someone" has multiple accounts.
UPD: also check out the hacked solution of dnc1994 1226917
UPD2: during the contest it seemed very suspicious to me that he resubmitted using pascal, since the first submission was written in C++
Yes, I remember him from one another round, where the code looked similar to some other account. There must be something going on.
I'm very sorry that it happens. But as you see , I use language pascal. Maybe he (dnc1994) copied my code.
U r dead Mr. SAW.
? what's your meaning?
It is almost obvious that you are innocent here.
Ну вот, был всё время в топ-20, а прошло в итоге только 2 задачи. :(
-7500 in Div 2 ?
When will my rating be update?
Let Div 1 system test be over first.Then ratings are updated
Как это решение решение задачи В в div2 1224894 могло выдержать такой тест-кейс ? 7 1 10000 2 10000 3 10000 4 10000 5 10000 6 10000 7 10000 На локальной машине выдает Seg. fault, на сервере дало корректно 28.
Chapeau :)
Не понравилась C. Какая-то безыдейная и больше подходит для ACM, где есть шанс ее запихать. Допустил 3 ошибки (использование 3 хэшей для перестраховки, вследствие этого использование отдельного класса для хранения этих хэшей, ну и последняя крышка в гроб — использование мапы вместо сортировки).
Тоже поТЛился? Но мы сами виноваты.
А что вам на С мешает сортонуть?
У меня прошло с тремя хешами типа long long — так что задача так сдается. А вот использование map в подобной задаче, это, простите, ваш косяк, причем очень грубый.
В конце концов генерите макстест и тестируйте на стороне сервера.
Чем плох мап в подобной задаче? С ним вполне проходит (всего-то миллион операций). Во всяком случае, если один хэш считать, а не 3.
У меня решения с использованием map/hash_map дают ТЛ (3.0 сек), при том, что решения без них работают 0.9 сек.
Ну, да, им, конечно, учитывая, что оба варианта близки к ТЛ, стоило аккуратно пользоваться (например n раз сделать ++ в одном мэпе, а потом, n раз сделать [] в нём же). Если сделать не 2 миллиона операций (у меня на джаве 3 миллиона за 2.5с ), а 10, то ТЛ вполне логичен.
I am getting TLE in Test Case 30 for the problem Colliders.Can someone tell me where to optimize it.Here's the code ->Link .I cant get it.Thanks in advance.:)
You can try to factor numbers in O(logN) time.
Faster and easier is through eratosthenes sieve.
Подскажите пожалуйста, а как массивы вида long[][] a = new long[n][] в Джаве работают? Куда он тут мои 256мб съел? http://codeforces.com/contest/154/submission/1230351 На плюсах то же самое решение меньше 100мб: http://codeforces.com/contest/154/submission/1230846
Ок, я нашёл проблему.
Если взять считывалку инпута Егора, получается -100мб: http://codeforces.com/contest/154/submission/1231419
Hey i'm curious as to how solutions to C handle cases like aaaabbbbaaabbba I tried a few correct solutions out but they give TLE or 0 as the answer o.O
oh nvm, my bad. got it now. sorry.
Ненависть! Я задачу B сдал со второй попытки, потому что вначале я писал не "Conflict", а "Confilct". Потом минут 10 искал, где ошибка. Правда, она всё равно в итоге заТЛилась на 30 тесте :(
The solution of problem c in div1 is using "hash" ? It's so unusal... And "map" will get TLE?
What exactly do you mean by "map" and how do you know that map is too slow only by a constant factor? At least I could imagine that in some cases map compares people with many friends too often. (As an extreme example: Let's not use a map but sort the people (I guess this doesn't make a huge difference). The runtime depends on the internals of the sorting algerithm: The sorting algorithm might be "stupid" and first compare the two persons with the most friends with each other n times and then do quicksort. This sorting algorithm works in O(n log(n)) if comparison could be done in O(1) but it can take O(nm) when persons have to be compared lexicographically.).
Задача Д класс! Жалко, что написал неправильный перебор для определения выигрышности/пройгрышности позиции(забыл поставить случай ничьей).
мне тоже понравилась, но только она попроще обычной D конечно :)
Ну идея не очевидна вроде-бы, реализация тоже не без мелочей, случаи рассматривать не самая приятная работа.
может быть) наверно мне повезло, что с ходу ничего не пропустил :)
I think there must be many participants ignored the vital constraint in problem A:
I think writer should make it bold. It's codeforces, not readforces...
That happened to me. But he did write it twice....
If you take out that restriction and allow letters to be in more than one pair, can it be solved with DP?
Most of the solutions that I read during the round ignored that restriction and used DP (so does mine). I was surprised when I tried to challenge solution that used the restriction and my test turned out to be incorrect %)
What kind so DP did you use?
D(i,j) — minimum deleted characters for prefix of length i, and last undelete character is equal j.
Interestring, my rating on the contest just went up, now I am 10th DIV2, I was 11th when contest ended. Also, may I know how soon will editorials be posted ?
This contest is my favorites... Every problem are clearly presented... Thank you very much Endagorion
I think all problems is nice.Thank you Endagorion!Finally,pray for myself not to make mistakes.
Is there any way to solve div1-C without hashing?
I think I found an O((n+m)log(n)) solution without hashing. Unfortunately it seems to be too slow by a constant factor. It works as follows:
(1) Let v(i) be the list of friends of i.
(2) Sort v(i). Create the list 1..n. Sort it by length(v(i)).
Then sort each chunk of this list with constant length(v(i)) by v(i) (lexicographically).
, so this step takes at most time O((n+m)log(n)).
Afterwards you can easily divide this list into chunks with equal v(i) in time O(n+m).
This gives the number of doubles (i,j) which are not friends.
(3) Add i to v(i) and repeat step 2. This time you get the number of doubles (i,j) which are friends.
Lost of hashing cost about 1s, and time limited is 3s. Many solution in div1 got TLE, because of the big constant factor.I hacked by someone's big test , and got TLE too.. :(
It can be solved using trie that should implemented using hash-table (it is not hashing:) ).
You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex.
So, we have exact solution in O(MlogM) time with small constant.
You ideas are good one~ Thank you very much!
Is it really necessary to sort if you are using trie?
You should sort all numbers inside every list (because lists like {2,3,1} and {1,3,2} should be equal) and use a trie instead of sorting all of lists.
I have a problem. how about memery limit? For each vertices on trie,have 10^6 chilid!!
use hash-table:)
You can see my implementations 1235766 (2970 ms) and 1235773 (1910 ms).
Are the editorials coming before the next round??
It's finally done. Sorry for the delay.
is there English verson?
Here..
Отличный контест ;)