bruj_kosh's blog

Help in ICPC 19 onine round problem
By bruj_kosh, history, 4 years ago, In English

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.

  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply