Привет всем!
Рад приветствовать вас на очередном, 94, раунде Codeforces. Надеюсь, что несколько более раннее время проведения раунда не скажется отрицательно на ваших успехах =)
Автором задач сегодняшнего раунда являюсь я, выпускник СПбГУ, Валерий Самойлов. Это мой второй раунд на Codeforces. Надеюсь, что сегодня никто не пожалеет о своём участии. Большое спасибо RAD, который оказал неоценимую помощь при подготовке задач. Также спасибо Марии Беловой, переведшей условия на английский язык.
В этом раунде будет необычная разбалловка:
Див-1: 1000 - 1500 - 1500 - 2000 - 2500
Див-2: 500 - 1000 - 2000 - 2500 - 2500
Прошу не пугаться, все не так уж страшно =)
Раунд завершен, всем спасибо за участие!
Разбор ожидается завтра.
Победители:
Дивизион 1:
1. Egor
2. Gassa
3. dzhulgakov
5. tourist
6. tomek
7. LayCurse
8. a9108
9. Sereja
10. ftiasch
а есть такие, которые живут в сибири, и контест после полуночи для них тоже очень тяжкий... где компромисс? так, что я считаю, всё нормально, всем удачи))
А как писать людям, у которых 4 утра когда в МСК 19-00?!
Просто ещё час уходит на судорожное смотрение на результат тестирования своих решений, судя по всему :)
It's a comfortable time for me, 2PM in China.
I code better at night. =D
Every night,my school will cut down the power at 23:30.
I always take the contests in the dark.
Всем удачи на предстоящем контесте :)
Всем удачи решенных задач и высокого рейтинга
Я предлагаю регистрацию сделать за день. А то мне пришлось вставать рано утром регистрироваться, чтобы поучаствовать...
И всем удачи на контесте=)
Последние изменения: добалено запостивание в ВК, FB, Twitter и LJ; убрана кнопка оставить комментарий внизу страницы; добавлена сортировка по рейтингу среди зарегестрировавшихся на контест! Классно... вроде немного, а чувствуется, что что-то делается, причём делаются приятные вещи.
UPD. Странно, что совсем новички имеют рейтинг 0, вроде бы он 1500?
Извращенские варианты типа "жми home, а потом pg dwn пока не закончится тема и начнутся комментарии" не предлагать!
А что делать тем, кто уже привык и не знает, как в тему теперь отвечать? :)
Думаю можно каким-либо образом оставить возможность писать комментарий снизу и сделать так, чтобы отличалось от "Ответить".
Какое-то злбное утро получилось)
Delayed 10 minutes?!
I have college after it ends with 30 minutes, now it become 20 minutes :\ Hope I could make it on time!
Зачем такие сильные претесты в Div1A (Div2C)?
Совсем с ума посходили что ли? Что хакать то тем, у кого с утра ничего не придумывается? %)
10ый претест, когда на месте нужно стоять.
А иногда это нужно.
И это ловили претесты, кошмар!
чорт... нашел кривое решение и не успел сделать взлом =_=
upd. хм... оно прошло все тесты. но, тем не менее, оно валится.
Very nice problems!
Спойлер.
Попробую написать чтобы было понятно:
Построим суфф. масс. с LCP. Это можно сделать за время N lg N. После чего заведем 2 указателя и текущую длинну подстроки. Первый - указывает на подстроку с наименьшим суффиксом из тех что ещё не рассмотрены полностью. Второй - текущий рассматриваемый суффикс. Тогда возможны следующие переходы:
1) LCP >= Len, тогда у нас есть ещё 1 такая подстрока и можно уменьшить k и рассмотреть следующий суффикс.
2) LCP < Len. Значит следующий суффикс начинается с подстроки большей чем мы рассматриваем, поэтому начнем рассматривать строки длины Len+1 начиная с beg
3) Суффикс короче чем Len. Тогда очевидно, что и все суффиксы что и раньше его уже рассмотрены и тогда можно подвинуть beg и len положить равным LCP + 1 (в силу того что это минимальная из нерассмотренных подстрок).
Эта часть делается за O(N+K). Ну и ещё вначале проверяем чтобы решение существовало. Итого за O(N Lg N + K) решили задачу.
у меня такое решение
при помощи хэшей мы можем за логарифм длины лексикографически сравнивать 2 любые подстроки. ну, идея примерно такая: бинпоиском найдем наибольший совпадающий префикс и посмотрим на следующий символ в обоих строках.
теперь само решение: пусть у нас есть куча с минимумом (грубо говоря set в C++). сначала сложим туда все подстроки длины 1 (причем подстроки мы храним как 2 индекса - начало и конец). далее выполняем k раз операцию: извлекаем минимум из кучи. если то, что мы извлекли (скажем, [i..j]) - не суффикс нашей строки, то ложим в кучу [i..j+1].
нетрудно понять, что мы извлекаем из кучи все подстроки в лексикографическом порядке, значит на k-й раз мы вытащим ответ. размер кучи всегда не больше n, значит решение работает за O((n+k)*logn*logn) (первый logn - это для кучи, второй для сравнения подстрок).
у меня решение на хэшах, про попроще будет суффиксных структур данных, но все равно не очень простое.
сейчас попробую доказать почему это не квадрат...))
Очевидно, что можно сделать так, чтобы все разрезы пересекались в одном банане и при этом были в общем положении. Отсюда и следует эта формула.
Хотя... в E у tomek, dolphinigle и Endagorion один и тот же ответ с WA на тесте 13, теоретически может оказаться, что правы они, а не жюри. Тест маленький, скоро узнаем ;) .
Иногда оказывается, что зря =) .
Ты можешь на пальцах доказать свой ответ на тесте 13?
Или, скажем, уменьшить k на нём в 10 000 раз и доказать?
Или объяснить, на что этот тест?
С другой стороны, на этом тесте даже 1E-6 должно было хватать.
Судя по тому, что у e-maxx теперь ОК - я верю в правильность результатов :)
A good point of the contest was brief problem statements.
http://codeforces.me/contest/128/submission/870700
I agree.
Idea is to use a priority queue. For example
abc, 5. You will do the following:
Push ("a", 0), ("b", 1), ("c", 2) on the heap. You will then pop the first element ("a", 0). Because 0 + 1 < size (3), you now push ("ab", 1) on the heap, and so on.
Do this k-1 times and the top most element of the heap is the sought after substring.
This gets AC. I'm not sure if you can construct a test case in which the comparison for the heap will make it too slow. I tried with aabbbbb...b and 10000, which should be very bad because all comparisons will be strings like aabbbbb and aabbbbbb, but it ran way fast enough.
Any ideas in problem D?
My approach is greedy. First, create a circle min, min+1, min+2,...,max,max-1,max-2...,min+1. Then check if it's possible to pair the rest numbers such that every pair consists of consecutive numbers since these pairs can be consistently added into the initial circle.
I liked this problem enough to write a blog post about it: http://codeforces.me/blog/entry/3196. It has a "proof" for a greedy solution similar to what you describe. Hope you find it useful!
There's a solution if the histogram is a sum of histograms of overlapping circles.
You can modify the circles greedily until each one is empty: Pick one the circles on the left side. Remove two pieces of the circle so that the min value is increased by one. In the histogram, it means removing 1 to the two leftmost bins. That's implemented in this solution .
My gredy solution works as follows:
let a1, a2 be the value of the biggest and second biggest value (without duplicates). Let c1, c2 be their associated counts. If c2 >= 2 we can "merge" an a1 with two a2s creating a segment: a2, a1, a2. This can now be seen as one a2, so we decrease c1 and c2 by one.
The base case is when a2 is is also the smallest value (only two values). In this case c1 must be equal to c2.
At all points we must have a1 - a2 = 1.
Или его участие было вызванно ошибкими авторизации?
Not relevant any more
Я писал пост из темы в режиме комментариев (http://codeforces.me/comments/3217), а вы смотрите из обычного режима. В обычном у вас http://codeforces.me/blog/profile/ZKirill, что неверно.
Всему виной <a class="rated-user user-green" href="../profile/ZKirill" title="Специалист ZKirill">
И мне всё-таки интересно, кто минусует каждый мой пост? :) Очевидно, это делает какой-то бот.
В задаче D слабые тесты. Проходит решение которое выдает YES на тест:
6
2 2 3 3 3 3
Я из-за этого сделал ре-сабмит, но оказывается что мог не делать
А в D - почему неправильно делать так: брать минимум и максимум, удалять их, и говорить, что мы сейчас сделаем из них цикл, поэтому все числа между ними мы удаляем по два раза. И всё это завернуть в while (есть хотя бы одно число).
Т.е. мы так находим несколько циклов, которые можно склеить в один большой цикл - ответ.
The Div 2 D.string
I use STL heap.
This is my code,it got TLE
If turn to this can AC
it really have big difference？
Is construct function make it slow,or access top()，or else？
I know this is an ancient comment but could you tell me how is it O(n+k)?
for a test case like "aaaaaa..." wont it run in O(n^2)
Это первый контест, который я писал на работе, и если бы не отвлекали... :)
I still don't understand your explanation, can you make it more clearly? First, why the two dimensions are independent. Second, why is C(n-2,2k), where comes the 2k?
There's just a slight mistake in your formula. It is supposed to be C(n - 1, 2k) since there are n - 1 different values in the interval [1, n - 1].
Наверно, единственный.
UPD. Нет, судя по плюсам и ответу, не единственный)
Но я и в A не прочитала с первого раза, что Маша умеет по диагонали ходить.
А что делать, ранний контест, 10 утра %)
Tourist's solution on div1 problem A?
You can use DP with state x, y, #moves.
You win iff you can survive 8 moves.
Then for each mem[x][y][cmove] you need to check if there's a rock in the cmove places above (it would move on you, so you die) or if there's a rock cmove-1 places above (it would be there when you tried to move, so invalid move).
Looking at your code, i see suspicious line int xx = sum[t][i]. May be problem is there.
If there were only one banana, then the answer would be 1 + K * (K+1) / 2 (it's easy to construct such a placement of lines, where each line intersects all previous, and all intersection points are different).
Now suppose we have several bananas.
If there is a line that intersects all bananas (intersects, but not touches), then the answer is 1 + K * (K+1) / 2 + (K + 1) * (N - 1). This formula means that we take an answer for one banana, and we cut all the remaining bananas by K lines into K+1 parts (because all intersection points are situated in the first banana). Why is it optimal to put all intersection points into one banana? Because each intersection point adds +1 to answer, so we've already achieved theoretically maximum possible value.
So, the problem is in reality the following: given N circles, determine, how many of them can be intersected using one line. I've solved it in O (N^2 log N) in the following manner: we suppose that the line touches one of the circles (we iterate over all N of them), so the position of the line can be described as polar angle. So any other circle can be described as an interval [angle1; angle2), where angle1 and angle 2 are the angles, when our line touches this circle. (We exclude the right end of the segment, because we don't want to find an answer, were a line touches several circles, but can't be made to intersect all of them.)
So, the algorithm now is to find the point with maximum number of intervals covering it, which can be done in O (N log N).
when will the editorials come out.Waiting for it desperately.....
in russian, it is there - http://codeforces.me/blog/entry/3219
Some hint for problem B Div 1 with suffix array. I am dead!
Some hint for Problem B Div 1 with Suffix Array? I am dead!
my submission using suffix array