Я рад приветствовать всех любителей программирования!
Сегодня состоится второй квалификационный раунд Яндекс.Алгоритм, и для вас его готовили Артем Рахов, Михаил Мирзаянов и я.
Обратите внимание, что как и во время предыдущего квалификационного раунда, функциональность Codeforces на время соревнования будет немного урезана. Не беспокойтесь, все вернется на место после окончания раунда.
Напоминаю, лучшие 500 участников проходят в Яндекс.Алгоритм 2011 Раунд 1, который состоится 20 мая в 19.00
Удачи!
UPD: соревнование закончилось, я поздравляю tourist с победой!
Напоминаю, что это был квалификационный раунд, а это значит, что первые 500 участников в конкурсе выходят в следующий раунд! Мои поздравления!
Сегодня у нас целых два самых удачливых участника: Hossein_Hima и ss.nurboolean - они разделили 499-500 места с результатом в 978 балла. Желаем еще большей удачи :)
чтобы получить права админа для управления контестом надо зарегистрироваться на него.
Lol! reading this comment in 2020, it feels funny, how much CF has grown even a DIV3 contest has more than 12000 official participants
EDIT: but my contributions may increase...
EDIT: Sorry I thought it was posted before the end of contest. Really sorry...
А в начале дня у меня были огромные сомнения насчет 2000 регистраций.
2. отравлять пир
3. ....
4.
profithigh ratingи размер группы сначала 2, потом побольше
на максимальном тесте)))
200
1 2
1 3
1 4
...
199 200
А ещё можно было получить TL решением за n4.
Ну на самом деле 10^9 инкрементов должен успевать
приделать восстановление ответа можно за 5 минут вообще не напрягаясь
Можна, пожалуйста, объяснить
с "восстановлением" - вывести еще как этот минимум получить.
думал над одномерной динамикой, где F(N) - оптимум для префикса очереди длиной N , и двумерной, где F(L,R) - оптимум для подочереди с началом L и концом R.
Но как вывести рекурентную формулу тут, не могу понять.
Ведь если первые трое A B C и мы пробуем взять A и C то у нас уже не будет интервала, который просчитан в динамике. у нас будет интервал + дырка + число В.
Подскажите идею динамики пожалуйста
Чето не пришло самому в голову.
наверно надо было что нить побыстрее stl-овского сета написать =_=
Но в принципе, и помимо сетов существовали существенные оптимизации, напр. писать на статике,
не писать рекурсию, а бфс сделать один раз, а не на каждом шаге и т.д.
Затем, чтобы писали квадрат. Подразумевается, что либо ты пишешь решение за квадрат, и спокоен за него, либо тратишь эн десятков минут на оптимизацию решения за n^2*log n, которое ещё и не факт, что зайдёт.
> Главное, что до тестинга это невозможно просчитать - и я думал, что с высокой вероятностью зайдет.
Невозможно просчитать, что 5000*5000*log(5000) ~ 3.07193*10^8 медленных, используюших сет операций скорее всего не влезут в TL? Если Вы не знаете, какова производительность структур данных STL, то это же Ваши проблемы, а не "авторам дисреспект".
База для k=0 очевидно.
Пусть пришли еще не все потомки, тогда из какого-то поддерева пришли не все потомки, тогда в вершину поддереве там пришло не меньше (k-1) за k-1 ход+1 была. Значит там что-то есть=> Оттуда что-то приедет.
Let d be the maximum distance from the capital to a people. Let x be the number of people whose distance from the capital is d. "x + d" is initially at most n, and each day this value always decreases.
<move follow qestion>
А плюсы за контест, особенно за хороший - это уже традиция.
Прошу прощения, если ошибаюсь, но мне кажется, что Вы думаете, что вклад и рейтинг это одно и то же, хотя это совсем не так.
Во фраза-то получилась :D
Обратите внимание, что как и во время предыдущего квалификационного раунда, функциональность Codeforces на время соревнования будет немного урезана. Не беспокойтесь, все вернется на место после окончания раунда.
Скоро все будет на месте :)
Отсортил всех в порядке приоритета. Для каждой вершины в каждый момент времени поставил сколько свободных мест есть, так-же запомнил куда нужно ходить из вершины. Иду в отсортированном порядке, и каждый раз пытаюсь сделать переход, очевидно что мы либо ходим далее, либо ждем, при переходе уменьшаем число в массиве. Так как ответ не превосходит Н, то решение будет в худшем случае О(Н*Н).
До сих пор теряюсь в догадках, как считывание несуществующих чисел помогло пройти тест с n=2.
В итоге +14 хаков. Очень рад этой своей баге=)
1*1=2
0*1=1
In case n > 2 a[i][j] = n-1 if and only if i and j were from one set. Find a for all 1 <= i, j <= 200, and you can find answer easy!
FIRST - input line in which was first occurence of this number
SECOND - input line in which second occurence of this number
two number belong to one answer where they have equal FIRST,SECOND pair
simple :)
1. u have not used points used[1..200] all set to 0//not used
2. read n - amount of sets,set must out sets o=n;
3 while readind n*(n-1)/2 pairs of sets do this:{ line number is j
set setA=empty; setB= empty;
read k-amount of points
for all k points p in this line j do {
if used[p]<0 continue;
if used[p] ==0 {is notused mark used[p]=j//it means that number p fist time in j line}
else if used [p]>0 {it means that in j line we get set
with p points in 2nd time so we can solve what set has p point
if (A.empty||used[A.top]==used[p])A.push(p) else B.push(p)
}//end for k points in j line
if(not empty A){out(A);mark all p in A used[p]*=-1;o--}
if(not empty B){out(B);mark all p in B used[p]*=-1;o--}
}//end for j lines of n*(n-1)/2 lines of pairs sets
test if (o>0){//o==2
cose we have last readed line like k a1 a2 .... ak
we make hand made out like
line1: 2
line2: 1 a1
line3: k-1 a2 ... ak
}
thats all
loose time cose this solution solv not only problem B but problems where not all pairs n*(n-1)/2, but that where each sets no less 2 times so this can solv:
4
4 1 11 2 22
4 1 11 3 33
4 2 22 4 44
4 4 44 5 55
4 5 55 6 66
4 6 66 3 33
Read the first of n*(n-1)/2 union. Remember the first element of it - F.
Then read all other unions and save only containing this F.
We will get n-1 unions U1, ..., Un.
Then intersect U1 and U2, we will get A0, that contains F.
After that subtracting A0 from every Ui, we will get Ai.
And A0, ..., An-1 are the answers. :)
If I'm not mistaking, it could be realized with complexity O(n*m) where m is the number of different elements, so about const*200*200 solution.
And don't forget about 2.
Вот и завершилась квалификация... и у меня возник вопрос по задаче D.
Может я конечно не правильно понял условия, но 7 тест у меня вызвал сомнения:
7
100 1 2 3 4 3 2
Вывод
106
3 7
4 6
5 1
2
Ответ
107
2 3
1 5
4 6
7
мы же поидее можем запулить очередь так, как показанно в выводе? (в строке по условию задачи порядок вывода чисел не важен)
это же места с учетом участников вне конкурса, их же вроде не нужно считать, или я не правильно понял идею участия вне конкурса?
P.S.: Да, я снова капитан и могу капитанить дальше)
возвращаюсь к комменту diogen'a (http://codeforces.com/blog/entry/1886#comment-36385)
послал я тут решение в дорешку и тоже получил ва 103. оказалось, что был фундаментальный баг и я вносил в кучу элементы, которые могли, но не должны были повлиять на дальнейшие итерации в вершине.
исправил, пересабмитил, полное решение
но суть не в этом. я не могу понять, как такое решение все же смогло одолеть 100+ тестов.. для меня это большая загадка..
(задача C имеется в виду)
For the first part, note that you may count each window (and both lightbulbs) separately, and each window gives a trapezoid shadow.
For the second part, you will each time only need to intersect two such trapezoids -- one from the upper bulb and one from the lower. It may look even easier if noticed that you may intersect triangles, not trapezoids.
However, the origin set in B could be 19900, and I announced 200....
и похоже Вы, Павел, становитесь моим фанатом, раз мониторите мои участия в турнирах
и еще мне почему-то кажется, что если кто-то ниже Вас в рейтинге, то не стоит акцентировать на этом внимание в каждом комментарии... я просто написал, что мне нравится задача (если быть точным описание к ней) и не пытался ввязываться не в какие дискуссии...
З.Ы. Не в обиду, но не будь столь высокомерным. Фраза "Иначе я бы просто опух тут всех подкалывать, кто хотя бы цветом хуже." не красит тебя