Сегодня днем состоится Topcoder SRM 605.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:31:58
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:31:58
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 10:03:03 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Андрей, кажется, у тебя анонсов больше, чем написанных раундов :(
Неправда, анонсов 11, а раундов 14 :)
It'll be at 6 am here in Mexico... I guess I'll need some coffee.
Time suits me well as it's 20:00 in China. Hope everyone GL&HR.
Очень странно видеть фразу "сегодня днём", написанную в 23:19)
Человек подстраивается под московское время, ничего странного.
У меня у одного недоступен сайт(и как следствие арена)?
То же самое.
Почему арена не грузится "как следствие"? Выкачайте jnlp-файлик, запускайте его, и на сайт вообще никогда не надо заходить...
Как следствие — потому что не было Арены. Привык просто из идеи его открывать. Пожалуй, действительно, не прмешает сохранить
I have registered for contest but arena says 'Unable to launch application'.
I tried starting the Topcoder Arena since 5 minutes before the start of SRM 605 until now (7 minutes after the start of the SRM) without success. The Topcoder website is also very very slow and I cannot use their link for entering the arena (because sometimes that part of the website doesn't show up). However, all the other websites work just fine for me. Is anyone else having such problems?
Topcoder site is not working for me at all.
As per this site http://www.isitdownrightnow.com/topcoder.com.html topcoder is DOWN for everyone.
Topcoder is down for the past 5-10 minutes...http://www.isitdownrightnow.com/topcoder.com.html
I bet CodeForces is behind this downtime. That conspiracy :)
Site is UP. Just logged in.
is the contest running?
Как решать B,C?
450: Первое, что можно заметить — это маленькое 1 ≤ k ≤ 10. Попробуем решить эту задачу с ограничениями k ≤ Bi - Ai, для всех i. Т.е. каждое число из первого множества стоит левее соответствующего числа во втором множестве. Эту задачу можно решить при помощи динамикиdp[i][j][mask]количество способов раздать первыеi - 1чисел, так чтобы последниеk - 1чисел были розданы по маскеmask(1— если в первом множестве,0— если во втором), а в предыдущих числах осталисьjчисел из первого множества, которые не были "закрыты" числами из второго множества. Как можно заметить из динамики этиjчисел лежат на расстоянии болееkот текущего числа. Поэтому можно сделать такие переходы:Дать число
iпервому множеству:dp[i + 1][j + (mask & 1)][mask >> 1] += dp[i][j][mask]Дать число
iвторому множеству, еслиj > 0:dp[i + 1][j - 1 + (mask & 1)][(mask >> 1) | (1 << (k - 2))] += dp[i][j][mask]Ответ будет лежать в
dp[n][0][0].Теперь вернемся к исходной задаче когда k ≤ |Ai - Bi|
Для этого можно заметить, что числа будут идти в определенном порядке первые левее соответствующих вторых, а после когда их количество будет равно, порядок может поменяться. Пример N = 4, K = 2, 1100|0011. К счастью такой переход можно добавить единственным переходом в динамике:
Если
j == 0иmask == 0Условие на возможность изменения порядка:dp[i + 1][j + 1][(mask >> 1) | (1 << (k - 2)] += dp[i][j][mask].Как решать 1000 div2?
UPD2
Идея неверна
Задача нахождения числа совершенных паросочетаний в двудольном графе принадлежит классу #P-complete
Наверное, я чего-то не понимаю, но как так получилось, что человек, занявший первое место в div2, сдал easy на 249 и medium на 499? Это же с какой скоростью кодить надо, чтобы так быстро сдавать задачи?
Всего лишь нужно иметь второй аккаунт. Думаю забонят
забенят
хаха
хаха
Между прочим, там easy такая, что её можно и сдать за 30 секунд)
Там более интересная ситуация. 3 из первых 4х победителей из одной школы и каждый решил обе задачи на 249 и 499. Ну там решения чуть-чуть похожи.
читер!:)
Как решается Div1 450?
Состояние. Сколько чисел уже положили, сколько из них в первом, маска последних К-1 в первом.
Ну теперь пытаемся положить очередное число в оба массива. В данный массив можно положить, если там уже больше или равно, чем в другом, или там сильно меньше (а именно, зависит от разницы и кол-ва элементов в маске другого массива)
Код
Why it is sufficient to know information about last K-1 numbers?
When the position will be incorrect? When number you add at some moment is less then number which is "opposite" + K. What are "bad" opposites? last k — 1
Другой вопрос: как к этому прийти?
Ну не знаю, подумать, что требуется от состояния если в тупую перебирать за ответ. Можно еще догадаться, что раз K не до 50, то есть множитель 2^k. Ну и запилить запоминание.
Late editorial