| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | maroonrk | 152 |
Can someone give more insights on this ICPC-19 online round problem . I know it requires LIS and prefix sum but I can't develop the idea.
Before writing this blog I have searched for it's answer in ICPC India Online Round 2019 Discussion blog on Codeforces but no one has explained the idea there, thus I have no source to understand it ...
Thanx, regards.
The problem is asking us to partition the array into multiple subarrays, such that the sum of each subarray is positive.
Consider a partitioning
a[1...p1], a[p1 + 1... p2], a[p2 + 1 ... p3], etc. where p[i] is the last index of the ith subarray.Clearly, we can rewrite this using prefix sums,
pref[p1] - pref[0], pref[p2] - pref[p1], pref[p3] - pref[p2], etc.clearly, all of these terms need to be positive, meaning that
pref[p(i)] > pref[p(i - 1)]This means we need to find and restore an increasing subsequence of length k on an array of prefix sums, which can be done with a simple modification to the normal LIS
Hope this helps, :p
I get it totally now, I really want to thank u from heart to take ur time in this.....
After ur explanation it seems quite a lot easy to code ... actually I was a lot confused after I saw submissions of other Teams on Codechef.
Again that just means a lot :)
Thanx, regards.