Nanthakumar06's blog

By Nanthakumar06, 10 months ago, In English

You are given an array A of size N and a number C.

We define the beauty number of a number X is defined as:

  • We have a universal array U where all the integers from -10^18 to 10^18 are present in sorted order [10^18,1-10^18,......,0,1,2,3,......10^18].
  • Now the beauty number of X is the number of subarrays of U with the sum X.

Find the number of elements in array A whose beauty number is strictly greater than C.

Constraints:

  • 1<=N<=10^5
  • 1<=C<=10^12
  • 1<=A[i]<=10^5

Test cases:

  • N = 1, C = 2, A = [12] Output: 1 The beauty number of 12 is 4. the result is 1. [12],[3,4,5],[-2,-1,0,1,2,3,4,5],[-11,-10,.....12]

  • N = 1, C = 12, A = [2] the beauty number of 2 is 2([2],[-1,0,1,2]

Can anyone help me to solve this

Full text and comments »

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

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.

Full text and comments »

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