Nanthakumar06's blog

Can anyone help me to solve this problem
By Nanthakumar06, 12 months ago, In English

Hi Codeforces,

Please help me to solve this problem.

You are given an array of size N.

A special subarray of Arr is choosen keeping the following conditions in mind

Let the length of first array choosen must be len-1 the length of last subarray choosen must be 1

Let sum of ith subarray is X and (i+1)th is Y then X must be less than Y

The choosen array must not overlap

Find the maximum length of special subarray(if max length is N, then the subarrays of length N,N-1....,1 must exists and sum of those subarrays must increasing) that could be choosen from Arr

Note It is given that you are only allowed to choose subarray in order of their occurrence in Arr This Means that index of all elements in first choosen subarray will always be less than the index of all elements choosen in second subarray and so on

Constraints 1 <= N <= 100000 1 <= Arr[i] <= 1000000000

Test cases: 1. A = [2,1,3,5,8,6,15] Here, the answer is 3([2,1,3],[5,8],[15]) We can split the array of length 3,2,1 and the sum also increasing. 2. A = [1,2,3,4] For the above array the answer is 2 because [1,2],[4] we cannot split the array for more than length 2.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't you confirm the last test case because there is the splitting 2([1,2],[4])?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes you are right it should be 2. If the array is [4,3,2,1] then answer is 1.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Nanthakumar06 (previous revision, new revision, compare).

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In last testcase, shouldn't be answer 4!!? by splitting array like this [1],[2],[3],[4]

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It should be 1. Because what we need to return is the maximum length. If I am going to split the array as 4, then I need 3 length subarray, 2 length subarray, and a one length subarray and also the sum of the subarray must increase as length decrease. So for [1,2,3,4] we can split as [1,2] and [4] as the sum of 3 and 4 respectively and the result is 2(the max length). We can ignore the [3] subarray in this case.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Ohh, it's written maximum number of special subarrays, so I thought it's talking about number of such subarrays...in that it's right 2 must be ans

      → Reply