Сегодня в 21:00 мск состоится SRM 535. После матча тут по традиции можно обсудить задачи.
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.10.2024 21:17:26 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать вторую(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 — мечта троллей)