3-го января в 19:00 (московское время) состоится очередной Codeforces Testing Round #4. Конечно, результаты на этом раунде не повлияют на ваш рейтинг, а его проведение — это тест системы перед ответственным Codeforces Round #100. Раунд продлится всего час и будет содержать две задачи. Я не обещаю что-то интересное и захватывающее, но как небольшая разминка будет самое то :) Для нас же важно ваше участие, чтобы быть спокойными относительно недавних изменений.
Буду рад видеть вас на тестировании,
MikeMirzayanov
Тестирование благополучно завершено. Неполадок не выявлено. Всем большое спасибо за участие! Надеюсь вам понравился этот спринт.
как это не надо! реклама-двигатель торговли!
кстати, задачи на раунде будут какой степени сложности? на реализацию?
В раундах по системе АСМ можно, так как там нет комнат. Такие раунды были, например, командная олимпиада школьников.
Я написал dfs с запоминанием глубины и текущей счастливости. Когда натыкаемся на комнату, в которой уже были, сравниваем свою счастливость с той, что была, когда мы были в этой комнате. Если сейчас мы более счастливы, то радуемся и возвращаем длинну найденного цикла (для этого помним глубину). На каждом шаге выбираем цикл меньшей длинны.
UPD: dfs из всех вершин, вроде O(N*M)
UPD2: А написал я вообще полную лажу %) Это талант: придумать одно, написать другое, при этом правильное (касательно ответа), но асимптотически медленное %)
Или я не так поняла?
мы можем прийти в какую то вершину несколькими способами, и дфс может выбрать такой, который вообще несчастливый
тест что то типа
4 4
1 2 10 -100
2 4 -100 10
2 3 10 -100
4 3 -100 10
3 1 10 -100
мы можем пойти по 1 2 4 3 1 - он несчастливый, в то время как 1 2 3 1 счастлив
бинпоиск по ответу, пусть длина цикла - k, возведём нашу матрицу смежности g (если ребра нет, то g[i][j] = -inf) в эту степень. Умножение конечно здесь другое: a*b[i][j] = max{k=1..n | a[i][k]+b[k][j]}. Эта штука ассоциативна, поэтому можно возводить в степень бинарно. По сути это будет то, о чём выше говорилось - динамика, где g^k[i][j] - максимальный путь из i в j за ровно k рёбер. Собственно потом смотрим на главную диагональ - если есть хоть одно положительное число, то и бесконечный цикл найдётся, исходя из этого меняем границы бинпоиска.
Если g[i][i] == 0, неважно, ровно k или не более k.
dp[first,last,length] , начало цикла, где мы сейчас и длина которую прошли.
я конечно понимаю, что раунд тестинг, ни на что не влияет, но все таки, взламываю:
FAIL the first and the last character must be letter
это где то написано в условии??
// уже ответили
У меня в уведомлении о взломе(таблица "Вопросы по задачам") в графе рассылка стоит "Да". Это баг или фича?
История задачи А участника Goblin:
00:19:01 Полное решение [претесты] → 996164
00:38:59 Решение взломано участником SkyHawk00:39:03 Неудачная попытка взлома участником CleRIC
это как так?)) Мне за это еще и минус дали.
Небольшой баг: при второй отправке решения на задачу А пришлось обновлять страницу, чтобы оно появилось в списке.
Try googletranslate russian version.
binpoisk == binary search, lol
After running the DP version of Floyd-Warshall (similar to exponentiation by squaring), you can check if a positive cycle of length K exists in O(N^3.logN) time by combining matrices for maximum distances <=2^U.
Knowing this, running a binary search from 2..N for the cycle length can also run in O(N^3.logN) time if the operations are ordered correctly.
I got stuck in problem B just now, but after read the article I figure out it :)