Всем привет!
Сегодня пройдет Codeforces Round #137 для участников второго дивизиона. Как обычно, остальные могут принять участие вне конкурса.
Задачи подготовила группа авторов из Владивостока — Илья Збань (izban), Алексей Евсюков (aevsyukov), Захар Войт (zakharvoit). Огромный вклад в подготовку раунда внес Геральд Агапов (Gerald), большое ему спасибо. Перевела задачи Мария Белова (Delinur). Также выражаем благодарность Павлу Кунявскому (PavelKunyavskiy), который тоже предложил свою помощь в подготовку контеста.
Разбалловка сегодня стандартная (500 — 1000 — 1500 — 2000 — 2500).
Всем удачи!
UPD: Начало контеста передвинуто на 15 минут по техническим причинам, приносим свои извинения.
UPD2: Опубликован разбор. Пока только на русском.
UPD3: Поздравляем победителей!
Во втором дивизионе первые 10 участников:
1: zxl0714
2: resodo
3: mugurelionut
4: hmspmy077
5: CCC
7: loveSakura
8: gcwtft827
9: yuxingdubai
10: b821213
В первом дивизионе, оторвавшись на взломах по задаче С, первые места заняли
1: navi
2: Shik
3: SteamTurbine
Надеюсь, вам понравилось!
Даже не знаю, что чувствовать, когда люди из моей комнаты в ЛКШ делают контест на CF. Какие-то неоднозначные эмоции.
Чувствуй гордость.
Есть, милорд.
Ведь именно эти парни пили твою воду и оставляли отзывы о тебе:)
У пользователей CF есть традиция — минусовать самые крутые посты.
Значит пост не столь крут как тебе кажется)
I am a novice and competing first time on codeforces. Can you please guide me through the blueprints of competition process. Thanks for your help in advance!
You can read FAQ(http://www.codeforces.com/help) or write a virtual contest
Надеюсь поднимусь
Надежда умирает последней ;)
надежда умерает с первым ВА
good luck for every one!
thanks
Codeforces servers went owie. :(
эх
Сколько сокрытого смысла
Я сервер Codeforces, и я не хочу contest №137, я хочу 502 Bad Gateway.
я не понял,кто-то тебя спрашивал?:)
Сервера codeforces нас очень сильно огорчают(
Мне, норм) У меня компьютер последние полчаса глючил и не подключался к инету. Я был очень удивлен, когда время начала увеличил) Прям, под меня стараются люди) Шутка юмора, конечно...
А я из-за переноса времени теперь в магазин не успею и мне нечем будет ужинать :-(
Будь доволен хотя бы этому!!!
Что с сервером??? 500 Ошибку выдает все время
Eat lunch as fast as you can... and wait 12minutes for contest start :D
What's the trouble before?
Сейчас во Владивостоке глубокая ночь же, да? Жизнь за
Нер-Зуламайку Problem Writer!Без двадцати минут три часа ночи. И у нас уже завтра.
Полтретьего, если быть точным :) Мы уже привыкли, пока раунды писали просто
и не на 10 минут передвинули, а на все 15..
Can someone explain test 1 on div2 C problem? Why is it: 2 3 2 1 1 1 1 and not for example: 1 1 2 1
Codeforces rules forbid asking about problems during the contest.
It is related to the clarity of the test case , I think, but nvm :)
You can ask on the contest page
Может я чего-то в этой жизни не понимаю — ошибка компиляции в java 7 из-за комментария на русском :
I can't understand problem C and D mean. :|
I can't understand problem C and D mean. :|
В чем смысл 10го теста задачи C ?
Просто большой сгенерированный тест
Просто большой случайный тест.
нашел неправильный тесткейс для своего кода, валившегося на этом тесте. 2000000/555555. Нашел за 3 минуты до конца, да.
мне одному показалось что B много легче A ?)
Более того, E легче, чем A.
В E вроде как надо учитывать композицию, что-то типа:
Запрещенные строки ab, ba
Если считать втупую, то aba может посчитаться два раза.
P.S. Можно вкратце решение?
Вроде возведение матрицы в степень.
Да, так оно и есть. Уже допер.
Считаем динамику a[i] (a[i] — вектор длины m) — сколько способов получить геном с символом i на конце. Если n=1, то это вектор из единиц, иначе a[i] получается из a[i-1] линейным преобразованием. Матрицу вывести нетрудно: A[i][j] == 1 тогда и только тогда, когда пара (i j) не запрещена. Возводим матрицу в степень n-1, умножаем на вектор из единиц (то же самое, что посчитать сумму ее элементов). Все.
Совершенно стандартная задача.
Буквы — вершины графа. Спрашивают: сколькими способами можно попасть из какой-то вершины в какую-то, сделав
n-1ходов. В инпуте нам сказали, какие ребра удалены из полного графа. Построим матрицу смежности A. Попасть из вершиныxв вершинуyзаkходов можно за(A^k)[x][y]ходов. Ответ на задачу — сумма всех значений(A^(n-1)).Задача эквивалентна подсчёту кол-ва путей длины n - 1 в следующем ор. графе: V — первые m символов,
<=> пара (u, v) не запрещена. Решение последней описано тут.
Спорно.
Could anyone give me an Idea for solving C without having to decompose all the values to its prime factors (this strategy gave me TLE)? Or is it mandatory to do that and my implemtation was simply too slow?
Are You using Eratostenes sieve or naive approach?
В задаче С должна проходить факторизация за логарифм с препроцессингом? Просто не очень ясно, как потом упаковывать множители так, чтобы вложиться в ограничения и на каждое число, и на количество. То есть, интуитивно кажется, что упаковка "в лоб" должна соответвтвовать ограничениям, но как доказать это — совсем не ясно.
Проходит любая факторизация, быстрее чем за корень. Это зависит от того, что вы понимаете под "упаковкой в лоб"
When I finally did dare to lock my C, I found that I can hack 2 solutions with max tests, then the contest ended. Sigh. Seems courage is really important.
Почему 2110913 работает долго?
Видимо, из-за считывания потоками. Хотя авторские решения с потоками укладывались в ограничения
А вот это не укладывается в time limit тоже из-за считывания данных? Как-то странно задача тестировалась и выставлялись time limit-ы тогда.
Интересно что у меня практически такое же решение нормально прошло.
Вот мне тоже интересно почему часть решений с потоками проходит часть нет, ну вот чем ваше решение от моего то отличается 2110915?
Вроде только компилятором :)
Спасибо, интересно. Тогда вопрос к авторам, зачем такое делать?
Чти вот этот ответ и учи STL
Да был не прав, извиняюсь перед авторами.
p.s. И да STL это хорошо но, чем компилятор помогает Scalar?
Разной реализацией STL очевидно, не? Да и вообще компилятор много чем помогает/мешает.
Зато теперь ты знаешь больше о языке, на котором пишешь. Раньше делал от балды, а теперь будешь делать так, как лучше и быстрее. Чем плохо?
И вообще в таком тоне нехорошо говорить.
Да вы правы, действительно есть и плюсы.
There was a slight error in the problem description. The "Input" says columns will be given first then the rows. However, the examples showed that this was not the case. Anyway, the round was good.
Very long systest.
I feel there was not a need for so many test cases for Problem B. Perhaps that is why systests are slow.
Yes it's very slow. Now it reach the first hour submission in one hour to.
Привет, спасибо за контест, было интересно порешать, самые большие трудности у меня вызвала задача C, и A зафейлил из-за маленького массива. Хотел бы напутствовать авторов в будущих контестах завальные тесты (особенно по ТЛ) ставить ближе к началу, печально ждать вердикта и видеть в статусе столбиками вердикты навроде TL 57, TL 49.
Вспомнился случай, который произошёл во время Сборов программистов в Ижевске. Там была задача на какую-то оптимизацию, вроде метода четырёх русских (матрица представляется битами). ТЛ у этой задачи был очень большой, по тем временам очень очень большой, что-то около 15-20 секунд. Мы сабмитили какую-то лажу — ТЛ-ные решения, и тем самым серьёзно подвесили сервер. snarknews — Snark вошёл в нашу комнату и громко так высказал что-то вроде "Тюменская команда повесила сервер, я прибиваю последние ваши сабмиты из очереди проверки, бла бла бла". Было довольно неприятно, что все покосились на нас, будто сабмит задачи это преступление какое. Проблема была в том, что тот макс тест на ТЛ, который таки валил задачу был в нескольких десятках других больших тестах от начала.
По-моему, авторы случайно перемешали отсортированные по сложности задачи :)
Reds( http://www.codeforces.com/contest/222/submission/2109757 ) can also fail div-2's A. Well done problem setters! :)
Ээээ кхм-кхм. B, TL 60. На запрос отвечаю за O(1). Это потому, что cin cout долго работает, да? Ну никак не ожидал в этой задачи TL'а — k до 5*10^5!!!
Потоки с C++ работают медленно, особенно вывод полумиллиона чисел. Была одна задачка, на которой я тоже словил ТЛ из-за потоков. Бага была в выводе 10^5 char'ов.
Конечно здесь лучше более быстрый ввод, но дело скорее всего в
endl, который не перевод строки, а вывод перевода строки и сброс буфера на диск(или запись в поток),fflushв вобщем. если заменишьendlна"\n"будет намного быстрее.А что же тут не так? 2119541
У вас
cinдолго работает. Если добавитьios_base::sync_with_stdio(0);, то ОК. 2120126Утверждалось, что достаточно поменять
endlна\n, я к этому.Ну, вот так, например, проходит: 2120210. Но на MS C++ лучше пользоваться
printf()/scanf().Хуже того, на контесте сдавал решение на VC++, 2111436, TL60, в дорешке сдал тот же код на g++ — 2120279, AC.
По моему, за такое нужно высказать дисреспект авторам. Что мешает поставить нормальные ограничения на простую B-шку, чтобы неаккуаратно написаное, но правильное решение заходило?
Видимо чтобы отсечь неаккуратные решения?
Не забывай, что это B div 2.
У меня зашло на джаве за 480мсек, при ТЛ=3секи, думаю авторы ТЛ выставили вполне нормально.
Речь идет о C++ и iostream. Те, кто говорят про увеличение TL'a (или уменьшение ограничений), делают это для справедливости в пользу сишников. При чем тут ява?
При том, что на джаве время работы зачастую больше, да и ввод/вывод на джаве медленней чем в С++
Ввод-вывод на джаве быстрее, чем cin/cout, если что.
Это GNU C++, а у iama MS C++.
Вы не совсем правы — в вашей посылке другой компилятор. А если добавить ios_base::sync_with_stdio(0) в решение iama, то ничего не произойдёт, т.к. в реализации MS C++ это не реализовано и этот флаг игнорируется.
Да, действительно. Не заметила. Извините.
Is there a particular reason why the two pointer solution gives TLE when using library sort in Java but gives AC when using library sort in C++? Is it Java I/O or the library sort? I see that uwi has an AC Java solution using radix sort, but I am yet to see an AC Java solution using Arrays.sort.
google "java sort hack site:codeforces.com".
in a nutshell:
int[] a; Arrays.sort(a); // — N^2 operations
Integer[] a; Arrays.sort(a); // — N Log N operations
The root of this problem is that Java uses mergesort to sort Reference types and qsort to sort Basic types. So simple anti-qsort test can fail all your attempts when you sort int[] instead of Integer[]
Кто еще решал А без массива? 2111830
какая идея в D?
http://www.codeforces.ru/blog/entry/5251
первое число в ответе всегда 1. у нас больше чем x очков, может у нас быть 100500 очков — да. Второе число можно получить выделив максимальное число таких i, j что a[i] + b[j] >= x. каждый элемент обоих массивов в такой паре лишь единожды присутствует. такие пары можно набрать жадно. посортируем оба массива, теперь для i возмем самый маленький элемент из b такой что a[i] + b[j] >= x.
почему тут ТЛЕ http://mirror.codeforces.com/contest/222/submission/2113563 видел похожий код-проходит
Считывание потоками 1500000 чисел, больше не из-за чего.
На самом деле вывод. Вывод полумиллиона чисел с endl. Дело в том, что вывод endl flush-ает поток. Т.е. вместо того, чтобы писать в буфер, а потом выводить буфер, он выводит числа сразу по поступлении.
скорее всего из-за endl. ИМХО, ТЛ в этой задаче не правильно подобран.
На жаве решения проходят с двойным запасом по времени, куда еще больше? Такой халявы не будет на официальных стартах, лучше здесь напороться один раз и на всю жизнь запомнить что 500К flush ни в какие ворота не лезут, чем потом обламаться на NEERC или ещё где. Большой инпут? -читай scanf. Большой вывод? — пиши printf.
Моё решение за линию на яве завалилось на 60-м тесте... видимо двойной запас — это мало, особенно когда узкое место — I/O.
Более того, авторское решение на Java проходит более, чем с трехкратным запасом, работает меньше секунды
Из-за потоков. У меня же такое решение прошло скорей всего из-за другого компилятора.
Чти вот этот ответ и учи STL
У меня тоже самое. Решение на GNU C++ мое и ваше получает AC. Я не знаю почему это происходит, но очень интересно было бы узнать.
Это происходит из-за разных реализаций стандартной библиотеки в MS C++ и GNU C++. Здесь я привёл время работы и некоторые способы ускорения различных методов ввода/вывода для обоих компиляторов.
So, stupid of me! This cost me E. Wasted too much time on A, so didn't had time to debug :(. Anyway, I feel happy that my approach was correct.
It was a good problem set. Thanks!
я, конечно, извиняюсь, но объясните мне, что происходит в 4-ом тесте задачи В
I think the problems in this contest is so simple that too many people killed all the problems :(
Hi, I have a question on test 8 of Problem D. The test is : 10 5
3 1 1 2 1 3 1 1 2 3
2 1 3 2 1 3 3 3 3 1
If we sort the array we will get: 6 5 5 4 4 4 4 4 2 2 So isn't the worst place is 3 ? But the answer is 5, i don't get this.
You arrange the resulting array in not optimal way.
It's possible to do so: (3 + 3) (3 + 3) (3 + 2) (3 + 2) (3 + 2) ...
and our guy has 5 points, so he's on the 5th place.
Thank you a lot.
My bad. I thought 1 column is the points of 1 person.
In second example testcase from problem statement you could see that this is not true :P
user editorial for the round please?
It's coming soon.
Can someone please explain the correctness of C problem. Actually I understood the approach, but i am not able to figure out why it will work Thanks.
Дважды прибавить/убавить рейт — это сильно)
Хотя, мне все нравится, оставьте так)
upd: Прошу прощения, ошибся темой.
прибавили рейтинг 2 раза)) А нельзя ли это так и оставить, мне нравится быть фиолетовым))
+1
какойто гробовой контест
А это баг, или почему все пишут сюда?
Тоесть?
Комментарии к раунду №138, а в блоге к 137-му.