Привет!
Вот и пришло время очередного раунда Codeforces, а именно раунда номер 129. Он состоится 11.07.2012 в 19:30 (по Москве). В этот раз задачи для Вас готовил я. В далеком прошлом я уже был 4 раза автором задач для Codeforces, тогда задачи были в основном о счастливых числах. Но ничего не вечно, поэтому в этот раз не будет задач о счастливых числах и тематика задач будет различной.
Помогал мне готовить задачи Геральд Агапов (Gerald), Александр Куприн (Alex_KPR), Аксёнов Виталик (Aksenov239), а традиционно задачи перевела Мария Белова (Delinur), за что им всем спасибо.
Надеюсь задачи вам понравятся и все пройдет гладко и я преждевременно не опубликую разбор, который сейчас у меня в блоге.
Держитесь!
Спасибо всем за участие. Результаты оказались следующими:
Div1:
- tourist (теперь tourist первый в мире таргет Codeforces, с чем его поздравляем)
- winger
- RAVEman
- rng_58
- RAD
- bmerry
- Shik
Div2:
Разбор задач можно найти здесь.
Так рано анонс, это радует)
Надеюсь, что сам контест тоже порадует.
Этот пост не содержит в себе никаких мыслей, заминусуйте его, пожалуйста.
Although there is no lucky problem but the round itself is lucky. 129=7+74+44+4 isn't it? :)
actually, it's unbelievable!
129=7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+4+4+4+4+4+4
129 = 4 + (7 + 4) * (4 + 7) + 4 — symmetrically lucky
And if we go deeper...
(7 + 4) * (4 + 7) = 74 + 47
(7 << 4) + 7 + 7 + 7 — 4
So one problem of the round was detected: return the number of ways, one can make 129 with lucky numbers :)
129=4+4+4+7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+4+4+4
Joke repeated twice becomes twice funnier!
He permutate digits. Now expression is palindromic :) And obviously more lucky :)
hope this time problem set will have good English translation.. I have seen that sometimes GOOGLE TRANSLATOR give better translation.. that time i am trolled.. :|
Good luck in the lucky round!
Как решалась С лучше, чем за квадрат? Судя по количеству ее решивших, я не вижу что-то ОЧЕНЬ простое...
нам нужно для каждой пары равных символов посчитать в скольких строках они могут совпасть.
Переберем символ в первой строке, бинпоиском найдем первый такой же во второй строке после. Разделим наши суммы для символов до него и после. Они свернутся
Допустим, хотим посчитать в скольких парах строк i и j будут сравниваться, если i<=j то count = i*(n-j+1). Теперь переберем номер первого символа i и найдем сумму всех ему равных во второй строке: A[i]=B[j], S=n-j+1, j>=i. Это можно пред посчитать заранее. Аналогично когда i>j. Еще нужно делить сразу на кол-во возможных пар число, которое добавляем (может выйти переполнение).
Да, предпосчет очевиден. В который раз меня уже губит то, что я вместо вывода формулы на бумажке пишу брутфорс и в итоге не остается времени...
Правда ли что это решение E:
строим общий суфмас для всех строк хешами за nlog^2. Потом проходим по нему двумя указателями поддерживая чтобы на отрезке [l,r) были "представители" k строк, добавляем lcp всех строк на отрезке(а значит первого с последним)(посчитаный за лог хешами) — lcp с предыдущего добавления.
Нескольких секунд не хватило, чтобы сдать C. Отличный контест, попотеть пришлось, и немало.
На чем ломали C? А то мне как-то страшно за свое вроде бы безбажное решение )
На переполнении int64 (сам не ломал, поэтому точно не уверен).
И только? 10 взломов у malcolm...
Да, и только.
У меня НЕТ переполнения, я гарантирую это.
Ну как же нету, есть)
Интересно, где же?
Числитель дроби не умещается в long long.
Вообще-то, я проверял...
Аааа, я тупой. Он же до 200 000, а не до 100 000...
Да я тоже так думал и массивы поставил величины 100000 =(
промежуточные переполнения
nice short problem statements ; easy to understand ..Liked the contest :)
no background stories FTW
Классные задачи. Автору респект. Жду тестирования.
cite from DIV2.D (second sentence of statement):
He has n cards, each has exactly two colorsand the last one of input section:
The color of the front of the card may coincide with the color of the back of the cardIn my opinion word exactly mean that both colors must differ...
IMHO, problem statements in this contest are completely clear, and you should just read them carefully
If it wasn't mentioned that the color of the back may coincide with the color of the front, then it would be unclear, but it's clearly enough mentioned and if you didn't read it , it's your own faulth for not reading carefully.
I only point that problem statement without word exactly would be better.
Yea, I understand , but why catching for one word when everybody understood the task properly and it was obvious enough what they ment :)
Благодарю за задачи, раунд замечательный! Особенно E понравилась.
Должно ли в E заходить решение за n·log2(n)? Конкретно: построим суффиксный массив на строке a1#1a2#2...#n - 1an, найдем LCP. Теперь для некоторой строки мы хотим узнать, какой наибольший ее префикс удовлетворяет условию (то есть принадлежит как минимум k различным строкам). Делаем бинпоиск по длине префикса, смотрим на LCP, получаем некоторый отрезок в суфмасе. Теперь нужно узнать количество различных чисел на нем. Это делаем персистентным деревом отрезков. Вроде бы оба логарифма (бинпоиск + дерево отрезков) довольно быстрые, в три секунды должно отлично зайти. Еще было бы интересно послушать решение суфдеревом.
Казалось бы, можно решить
суфмассивомсуфдеревом. Построили для такой же строки (может быть, потребуется сделать все разделители различными, чтобы не пересекались). Для каждой вершины посчитали количество достижимых '#'. Если >= k — сделали пометку. Пробежались по всем '#', посчитали сколькими способами можно добраться в неё из помеченной.Суфдеревом, ты хотел сказать? Да, действительно. Только сейчас понял, что насчитать количество различных чисел в поддереве можно в офлайне. Я чего-то затупил и не сразу понял, как это делать. По модулю этого все понятно. А разделители у меня все различные, сейчас это отмечу.
Да, # нужно сделать различными. У меня такое решение, а суфдерево строю по суфавтомату.
Все так, только без персистентных структур — нам не нужно количество различных в подотрезке, а только не меньше ли оно за k. Для этого для каждой позиции i с помощью сетов найдем минимальный индекс j такой, что подмассив [j;i] содержит ровно k различных (пусть это F(i)). Потом для какого-то отрезка [l;r] проверка это будет просто: l ≤ F(r).
Хм, и правда. Персистентное дерево я набил быстрее, чем придумал, как логарифм выкинуть :) Кстати, зачем при подсчете F(i) сеты? Вроде бы можно насчитать просто двумя указателями, поддерживая каждый раз массив cnt[i] (сколько раз на отрезке встретилось число i). Впрочем, этот логарифм сетов на итоговую асимптотику все равно не влияет.
Вообще говоря, количество различных чисел на отрезке — это тоже классическая задача для дерева отрезков. Давай научимся учитывать от каждого класса эквивалентности только самое правое число попавшее в отрезок. Чем оно характерно? Тем, что ближайшее к нему справа уже находится за пределами отрезка. Ну так давай заменим каждое число на позицию ближайшего справа равного ему — тогда запрос примет вид "количество чисел на отрезке [l, r], которые больше чем r" — его ты, наверное, умеешь делать.
Макс, а я думал, персистентное дерево отрезков — как раз классическое решение :) Я научился это решать, когда мне "Откат" с ВКОШПа рассказали. Ну, в любом случае, перситентное дерево я напишу быстрее, чем partial cascading (решение твоей задачи за log; если не ошибаюсь, именно так называется). Да и работает персистент быстрее, насколько я тестил, хотя здесь спорить не готов.
Проклял в задаче D тест:
сдал... на 450 =D жесть... а столько времени убил.
Контест классный!
Авторам спасибо!
Ждем от вас еще!
Есть более короткий тест с тем же смыслом:
Could anyone give a hint on how to solve 204C - Маленький Слоник и Фурик и Рубик? Thanks!
First of all let xi and yj be the same letter in string X and Y respectively. The number of substrings of the same length in X and Y that contains xi and yj is: (1+prefixSize(min(i,j)) * (n-suffixsize(max(i,j)) in 0-based array Now for any matched xi and yj characters, find the number of all such substrings. this code runs in O(n^2) and obviously wouldn't fit in time. Consider that if j<i the above formula becomes (1+prefixSize(j))*(n-suffixSize(i)). So for each letter iterate over i and keep the summation of (1+prefixSize(j)) for all j<i using dynamic programming and multiply it by ((n-suffixSize(i)). do it again for j>=i and divide these values by the total number of sunstrings. be aware of overflow!
Контест отличный! Спасибо авторам.
Late system testing :( ?
Cound witua tell us when will the system testing start?
Название задачи E div 2, C div 1 повеселило. Маленький Слоник и Фурик(Furko) и Рубик(Rubanenko)
Меня тоже :D
мне одному интересно, почему у iroro место проживания финляндия, она же вроде из россии?
Могла переехать — почему бы и нет.
На этом всеросе она ведь была? А Финляндия стоит у нее уже достаточно давно.
Насколько я помню, у нее там родители, не?
Нет :) Смысл в том, чтобы реже находиться при поиске
Мне стыдно, прости :) Я перепутал тебя с Анатой, а Швецию с Финляндией :)
Какой смысл скрываться, если не секрет?
Ну, я себя обычно спрашиваю, «какой смысл не скрываться» :)
Это более дефолтное действие?
Да :)
Кстати уведомление о взломе опять пришло очень незаметно. Заметил чисто случайно, не найдя себя в ожидаемом месте таблицы комнаты. Не хорошо это.
У меня нормально все было, прямо в центр экрана вылетело.
Баг репорт:
У yeputons сейчас написано по C: Решение было взломано после блокировки.
На самом же деле, сперва оно было взломано, потом заблокировано и сейчас еще может зайти.
Ну и вообще, в таких ситуациях хочется видеть вопросик, а не (-x)
While browsing through some of the solutions ,I found this amazing short one by winger for Div1-A/Div2-C..Very nice and simple solution that most of us missed:
Can anyone explain me the idea?
I have similar solution.
F(x) is number of tens, which less or equal to X, and 9 (numbers 1..9). One thing — if first digit of x > last digit of x (examples — 51 (5 > 1), 623 (6 > 3)), we mustn't count last ten, so we subtract 1.
Its simple..The function f(long x) returns the number of the numbers that have the same first and last digits. So if x < 10 then that all the single digit numbers less than x are what we are looking for and so x is returned .Otherwise u can see that for all the numbers whose length >=2 have the unit place digit will be equal to the highest order digit exactly ones in every 10 numbers .So we add x/10 to our result. -1 is because we dont want to add the single digit numbers and for them we add a +9. The remaining part is just for checking if the residue of the number when divided by 10 can also be used or not .
Finally becuase we need to count that in the interval [l,r] we find f(r) and the subtract from it f(l-1)
Nice One !..
what the AWESOME!! great problem-set.. :)
А тестирование меж тем стоит
Просто внезапно начал проверяться Див 2...
Не правда. Пустили Div-2 зачем-то.
Я думаю уже можно:)
My thanks to witua for the contest!
Does anyone have an idea what is 71 test (Div-1, B) about? Many java solutions failed with TLE on this tricky one.
someone included an anti-quicksort test long ago, and many java solutions failed. maybe something similar exists for hash-maps?
AFAIK, HashMap has 2^n buckets by default. So, If colors divides to big 2^k, it maybe slow? Does TreeSet work well?
It works with TreeMap...
Your submission with TreeSet http://codeforces.net/contest/204/submission/1891800
Yeah, I already checked this. It is rather slow (720ms), but nevertheless. I still don't get whether this is some magic test or linear solution may fail out of HashMap inefficiency.
I guess it's not linear on this test because of collisions
I get that. "Magic" stands for bringing down java hash map (it's specific hash function, which you may find in java sources) on purpose.
Please note that hashMap uses special precaution to counter it — instead of using hash value right away, it uses h ^ (h >>> 20) ^ (h >>> 12) ^ (h >>> 7) ^ (h >>> 4). Hence one need to carefully prepare anti-HashMap test
Hmm, thanks for info..
We have made it about an year ago for using in hacks. This transformation can be inverted in a similar form.
Upd. It works regardless of Java version and input sorting/shuffling.
If it was added by authors specifically for this purpose I think it is really bad
Had the same thought. If it was added intentionally, then (as PeterGriffin mentioned), if it comes to that, why couldn't authors always add an anti-quicksort test for all java solutions to fail. :)
It could be added after a successful challenge with this test.
That's why I added "if" in front of my comment
I bet you're right. I took a look at the tests previews, and it seems that the authors have 63 tests, give or take. Curious situation. Perhaps Vitaliy could clarify what was it. :)
Well, that test was not added by me and it was added during the contest, so I haven't noticed it. I also think it is a bit bad :(
Ok. Then, as it comes to me, it's a cruel lesson about not using HashMap class on Codeforces. Worth mentioning that it is especially funny because there is no way to do such mean things on TopCoder.
Ignore
As far as I remember, It will same to
new HashMap(32) and it should not help
Yes, my bad
Egor, map capacity is still chosen as the power of two, so it doesn't change anything, even the load factor doesn't work (correct me, if I'm wrong).
We have checked this. #TLE (3.6s)
But we'll update our generator for using with any initial numBuckets.
It helps to use HashMap<Long> instead of HashMap<Integer> and shift all values by r ( << r), where r is random int in [6; 32), but yes, this is ugly...
Theoretically you can still remove it ;)
Is it possible to remove the test case and rejudge? It was good being purple for once :). My hopes are low though.
Why is it so bad?
Sorry, but really, in this thread, I could not find any arguments at all. Everyone just silently accepts it's bad. It may well be so, but why?
I see at least couple of reasons: first, c++ people use tree map by default without thinking about it — it is a bit of unfair advantage, second, if we add test for Java we should add such test for every supported language that has hash map in standart library and is subject to similar exploit
It's amazing that whenever I don't participate in a contest, It's EASY!!!
Agree with you
Спасибо за отличный контест, интересные задачи и слоника)))
Я, наверное, какой-то очевидности не замечаю. Вот посылка по задаче D(div. 2)/B(div. 1). И я не понимаю, почему она падает с ошибкой Runtime. Помогите, пожалуйста.
Это не TL, это Runtime.
Различных чисел может быть до 200 000.
У меня же массив colors длиной в 200000 вроде?
вот код
прошло
Она не ТЛелится, а падает с Runtime Error. Проверь на переполнение/деление на 0/выход за границы массива.
tourist become first target!
Congratulations!
Виталик, отличный контест, особенно задача С div 1 :D !
Один я не знаю что такое таргет? UPD я тупой(таргет — овер 3000)
Для тех кто не знает что такое Topcoder простительно.
Div-2 анрейт?
у меня тоже вернулся старый рейтинг. То ли нашли косяк в задаче, то ли читеров вычищают
Наблюдаю симптомы unrated-раунда для div.2. Рейтинг был пересчитан — а теперь вновь "откачен" назад.
Там в таблице есть несколько недотестированных решений (со знаком ?), когда все исправят рейтинг будет пересчитан. Не волнуйтесь, контест рейтинговый.
это радует )
Знаков ? уже нет (хотя, после написания Вами этого комментария вроде их и не было), рейтинг не обновляется уже 3-е сутки, и это уже настораживает.
А почему я синий с рейтингом 1489?
потому что ты получил синий рейтинг по итогам этого контеста, но цифры еще не обновились
Excellent competition, I enjoyed solving the tasks and they were all very clear. One of the better ones in a long while for me.
By the way, is there something wrong with my browser, or did all the rating changes in Div2 for this contest get removed? If so, when can we expect it fixed?
I only solved one problem... I will try to improve and get better, but shouldn't I have gained some more points on my rating? :)_
The ratings are not updated yet.
what is wrong? div2 is unrated ?
I am asking the same :D I don't know about some big problems with the contest for div 2.
When will the rating be updated?
If the round is being rejudged or unrated or something wrong with rating calculation, please post an announcement in the blog.
Can anyone tell me why this code gets WA? Am I missing something tricky of Div2-A?
1885288
Even if there is a pair of same numbers, it doesn't mean that there's no less number than those. That is, I think you should check all the numbers before everything.
Thanks. Now I understand.
I've changed color but not raiting.whats wrong?
For Little Elephant and Furik and Rubik (204C and 203E) I am getting a WA for http://codeforces.net/contest/204/submission/1894333
The test case that fails gives a negative answer. Am I running into overflow errors? Also what I have done is that I first collect the indices of all the alphabets into a 2D structure and then try to match the corresponding characters. Also is it possible to get the complete test case locally at which my solution fails. The testers shows the partial test case? (If not this functionality should be there).
yes, negative anwer means an overflow. But you'll get TLE anyway because of using 2D structure. Constraints are too large for it
Yes, thanks. Now I realize the problem and yes the code does TimeOut.
this code may overflow,because n is int
Thanks, that was the problem. Although the code is slow to get passed.
Why my rating does not change?
У DULGUUNBATMUNKH цвет поменялся, а рейтинг так и остался 1500+, а у меня рейтинг вообще не пересчитался. Что за фигня опять происходит?
Это был мой первый контест в котором я участвовал, по итогам я стал синим, но рейтинга все еще нет. И в "соревнования" пусто. Выше это оправдывали тем, что еще не все систесты прошли, но уже несколько дней прошло.
no change in rating...
I think we are going to have to end up waiting for the next contest for the scores for 129 to update :(
No one care the div2 participants's rating ? So irresponsible...
VK Cup is coming up, so administration have no time for changing rating.
System must do it, not administration.
DIV_2 the Rating is Updated !!!
Liked the contest.
How to solve Div-2 B, little elephant and sorting ? http://codeforces.net/contest/205/problem/B ?