Сегодня, 19-го января в 12:00 мы открываем новый проект Codeforces::Тренировки. Через 30 минут, в 12:30 мы начнем первую тренировку, на которой вы сможете познакомиться с системой. Продолжительность тренировки – 3 часа. Приглашаем вас принять участие! Как и всюду в Codeforces::Тренировки, будут использованы ACM-ICPC правила.
Так как будет проведена тренировка, то будут использованы задачи некоторого прошедшего соревнования (спасибо авторам!). Пожалуйста, не участвуйте в тренировке, если вы видели эти задачи. Не портите тренировку другим участникам. Спасибо за понимание.
UPD: Контест перенесен на 10 минут вперед. Все замечания по работе и предложения следует писать в виде комментариев в трекере проекта.
I wanna know too..
where is "Gym" section??.
"Today we open a new project Codeforces::Gym, it will be started on January 19, 08:00AM."
Patience =)
there is no "test" contest as mentioned in the blog???
can someone please guide?
Just patience - http://mirror.codeforces.com/blog/entry/3676?locale=en
This sounds like a great idea although it will be 2 30 AM in my time zone, as this is training don't you think you could open another three hour contest in an hour more suitable for us in America (the continent)?
>>Через 30 минут, в 12:30.
Если говорить про московское время, то 12:30 настанет через 80 минут, но никак не 30. И все-таки, где раздел тренировки?
Егор, спс) Гений!
рукалицо
Кампус - это общага школы, видимо=)
P.S. А вообще тест из условия все обьясняет.
Аналогично
string repl[9][2] =
{
{"aa",""},
{"bb",""},
{"cc",""},
{"ababa","bab"},
{"babab","aba"},
{"acaca","cac"},
{"cacac","aca"},
{"bcbcb","cbc"},
{"cbcbc","bcb"}
};
Тоже хз как доказать.
вот вот, но на cf заходит) cf слишком быстрый
или теста такого нетP.S. взял код одного из участников с таким же решением, всунул туда генератор, на сервере проработало 3.75 секунд
можно было решать быстрее.
Для начала отсортируем в каждой дисциплине кабинеты по позиции
Сформируем граф следующего типа:
граф состоит из С уровней и 2-х дополнительных вершин - начальная и конечная.
На i-м уровне расположим T вершин соответствующих кабинетам i-го задания
На каждом уровне соединим соседние вершины ребром с длиной, равной расстоянию между соответствующими кабинетами.
соединим начальную вершину и самую левую вершину 1-го уровня ребром, с длиной равной позиции этого кабинета.
Теперь для произвольной вершины с i-го уровня (кроме последнего) бинпоиском найдем ближайшую справа и слева вершину со следующего уровня. проведем ребра в каждую из этих вершин (длина ребра расстояние между этими кабинетами + затраченная энергия). Из последнего уровня будем проводить ребра в конечную вершину. Сложность построения O(C*T*log(T))
Таким образом в графе будет C*T+2 вершин и не более (С+1)*T*2 ребра.
Теперь найдем длину кратчайшего пути между начальной и конечной вершиной алгоритмом Дейкстры за O(E*log(V))
Таким образом итоговая сложность для одного теста O(C*T*log(C*T))
Надо считать минимальную энергию, которую потратит Фред для посещения t-го занятия на c-й дисциплине, и позицию этого занятия: т.е. для каждой новой дисциплины перебрать все её новые занятия, а для каждого занятия (t) с энергией (eNew) и позицией (pNew) - перебрать все предыдущие занятия(tt): eMinNew[t] = min{ tt = 0..T } ( eNew[t] + eMinPrevious[tt] + abs(pNew[t] - pPrevious[tt]) ); pPrevious = pNew; eMinPrevious = eMinNew;
Eh. Why not treat it as normal CF contests which allow people learning from others' code? Otherwise, it's more like another online judge.
обидно, подумал в Е не зайдет 500млн (Z*C*T*T), написал решение за Z*C*T, сдал черти во сколько...
как С решать?
Искомую точку всегда можно выбрать на пересечении двух окружностей (кроме тривиального случая, когда ответ - 1).
Это довольно часто встречающася штука, и доказывается она легко. Допустим мы нашли некую оптимальную точку. Ее всегда можно сдвинуть в какую-нибудь точку пересечения, ни разу по пути не пересекая окружностей. При этом она по-прежнему будет оптимальной.
Перебираем все пары окружностей, находим их точки пересечения, проверяем насколько эти точки хорошие. Итого O(N3).
так и решал, но почему то не заработало даже на примере, наверное где-то в геометрии косяк
спасибо за объяснение
А можно решение E за O(ZCT)?
ну идея такая же, только переход за линию: ну считаем данные, и отсортим для каждой дисциплины ее занятия по возрастанию их мест
в переходе динамики будем сливать места занятий i и i+1 дисциплины (так, чтобы сохранялась упорядоченность), будем идти по этому массиву и поддерживать минимум дп спереди и сзади от нашего текущего j-го, когда мы сдвигаем указатель на j+1, минимум спереди j у нас увеличвается на расстояние между j и j+1, а сзади уменьшается на это же расстояние. каждый раз при новом j релаксируем наши минимумы, то есть если значение дп в этой точке меньше, чем текущий минимум, то делаем релакс. и таким образом мы считаем дп для i+1 дисциплины
надеюсь более или менее понятно объянил (что врядли), думаю по коду будет понятней
P.S. ах да, решениие получается за О(ZCTlogT) за счет сортировки, ну само дп за O(ZCT)
http://mirror.codeforces.com/blog/entry/3702#comment-74984
м?
I am unable to implement the problems like A. Can someone tell me the way to practice similar problems? I can only think that this problem could be solved by graph but how to proceed next step? Please guide me.