TalentnotDefined's blog

Special Subarray
By TalentnotDefined, history, 17 months ago, In English

You are given an array arr of size N of non negative integers. Find number of subarrays of array which are special. A subarray is special if product of its maximum and minimum element in divisible by length of the subarray.

Find Number of special Subarrays.

1 <= no of test cases <= 1000

1 <= N < 5*10^4

0 <= arr[i] <= 30

Can anyone tell me approach for this problem?

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

Comments Comments (12)
| Write comment?
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Real Constraints

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

    is this an ongoing contest?

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

      no finished today ig...it was oa of sprinkler

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

        Can anyone share the approach.. i tried to think that max length of subarray can be 900 and then iterating over all those 900 length continous subarray for checking..but it a tle

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
          ← Rev. 2   Vote: I like it +13 Vote: I do not like it

          That's not quite true. You could have length of subarray greater than 900 if the minimum element is 0.

          So I think you'll have to account for all the subarrays that contain a 0 along with the subarrays that you mentioned.

          Also, one of the reason that it TLEd could be because you didn't use fast io.

          → Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it +18 Vote: I do not like it

Since the size of the elements is very small, you know that starting from each index, the maximum/minimum element from subarray that begins at that specific index will only change 30 times. You can find this with RMQ. Knowing how the maximum and minimum change, you can find out how many subarrays starting from that specific index fit the criteria.

This probably fits in the constraints

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

    instead of the RMQ, iterate from n-1 to 0, and maintain nxt[] array, where nxt[i] = the position of the next occurrence of i. then instead of finding the next position in which min/max will change, find the next position that have a value that you didn't include in the current subarray. you can do that by iterating over nxt[] and minimize the iterator of the next position with nxt[i] if i wasn't included in your current subarray.

    something like this:

    nxt = vector<int>(31, n);
for i = n-1 ... 0:
    vis = vector<bool>(31)
    j = i
    while(j < n){
        vis[arr[j]] = true;
        nj = n;
        for k = 0 ... 30:
            if(!vis[k]) nj = min(nj, nxt[k]);
        j = nj
    }
    nxt[arr[i]] = i;
}
    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

so sum(N) can be 1000*5e4 = 5e7 ?

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

ig the max value is 900 so you can iterate from 0to 900 that my product is I (ie, 0 to 900)

now take two-pointers to handle the case and just increment when it is divisible

→ Reply