Сегодня в 21:00 мск состоится SRM 535. После матча тут по традиции можно обсудить задачи.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:52:04
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:52:04
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 20:42:57 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать вторую(div 1)/почему капитанское решение неверно?
Потому что надо отучиваться от привычки писать первое что не можешь сходу опровергнуть.
Решение. Пусть ответ ≤ А·totalWork.
Тогда
Тогда 
.
Ну а здесь уже жадность брать K максимальных по ai·(A - pi), очевидно работает.
Сделали бинпоиск по А.
Если я правильно понимаю что такое капитанское, то оно валится тестом n=3, k=2, totalwork=2, a={1,90000,1}, p={1,90000,100000}, ответ — 107201 (надо отработать 1 и 3-ему, хотя на первый взгляд 3-ий хуже 2-ого).
500 Div 1: жадность заходит, или нет?
У меня почелленджили
Зависит от того, что называть жадностью. Самая тупая не проходит (у меня тоже почелленджили).
Соль в том, что жадная оценочная функция вроде бы неверная — из-за приписки о том, что все должны работать поровну в плане времени.
Такая же, что описал PavelKunyavskiy выше.
Судя по рейтингу постов выше, в тему начали заходить люди, которых, после фэйла их 500, злит любое упоминание о ней.
Похожая на 1000 была на зимней школе в Харькове. Те, кто ее сдали, писали решение за O(S * S * W)?
Ого, на какую? Я что-то не могу вспомнить.
Ну там на коротком контесте Антона Лунева была задача, где динамика пересчитывалась примерно как
f(x) = k * f(x - 1) + (k - 1) * f(x - 2) + ... + f(x - k + 1). Здесь вроде бы не тяжелая динамика за O(S3W), в которой примерно такой же переход, который так же оптимайзится до O(S2W).И я. А то что мы оба не можем вспомнить уже на правду не очень похоже.
Я умею решать за O(S4 + WH), но не успел написать.
Помимо того, что я не придумал правильное решение в 500, я еще и затупил в харде — зачем то степени S брал вместо S + 1. В итоге вместо ~5го места сейчас окажусь в конце второй сотни
Как решать 1000?
Ну, есть очевидная динамика с O(SWH) состояний и O(S2WH) операций. Так как переходов вниз не более S, то она превращается в O(S2W) состояний и O(S3W) операций. А дальше надо пересчет сделать за O(1), для этого надо предподсчитывать суммы вида ans[i][j][k] + 2 * ans[i][j][k-1] + 3 * ans[i][j][k-2] + ...
Я умею оптимизировать очевидную динамику до O(S^2*(W+H)), пользуясь тем что матрицы перехода вниз и вправо коммутируют. Failed systests из-за неразобранного случая 1x1 :(
автор с ником wrong — мечта троллей)