how can i start thinking about problem like this http://codeforces.com/problemset/problem/478/D?
can anyone explain the solution ?
№ | Пользователь | Рейтинг |
---|---|---|
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 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
how can i start thinking about problem like this http://codeforces.com/problemset/problem/478/D?
can anyone explain the solution ?
Название |
---|
First observation is that the maximum height h is greatest h satisfying h*(h + 1)/2 <= r + g.
let's say total = h*(h + 1)/2, then if you take g green balls and (total — g) red balls, then number of ways of arranging them is same as number of ways of expressing (total — g) as sum of numbers (order doesn't matter) less than h. and the ans is summation of that sum for all g.
Here is my code
Wait, this is trivial O(N).
Not O(N), it's
how ?
, and so the time complexity of this nested loop is