Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.04.2024 05:06:59 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Huh, as I read this, my solution to E seems to have zero things common with editorial as well. I solve $$$O(nk)$$$ problems where each element is $$$0$$$ or $$$1$$$ with some probability (depending on its position). For binary strings original problem can be solved while keeping two variables — what is the optimal cost if I have an interval opened and what if I don't have it opened. Using that insight, for each prefix I count number of sequences that will lead me to each state of dp (and there are $$$O(n^2)$$$ states of this dp for each prefix, so $$$O(n^3)$$$ in total, so my solution works in $$$O(n^4k)$$$.
Right, this is exactly my approach as well!
By the way, do you have a proof for the reduction to 0/1 problems? It feels right intuitively, but I can't formulate easily why :)
You might want to read the editorial to problem Landscaping from 2016 US Open. That's what I did during the AGC.
US Open? I thought they play tennis there or something :p
I don't, I went with my intuition as well :p
I believe this was roughly scott_wu's approach as well, though I think he optimized the DP down to n^2 transitions. I think this is actually not so different from the official solution; once you observe that it suffices to solve the 0-1 problem, the dp to solve the 0-1 version is really equivalent to the editorial's; you just got there without proving the 0-1 reduction.
sir recommend some good resources for cp
You don't need any just make one submission(Accepted or wrong answer doesn't matter) in a rated contest then you will reach 3000 in 9-10 days because 2_din_me_rating_double xD!