Блог пользователя TalentnotDefined

Special Subarray
Автор TalentnotDefined, история, 16 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Real Constraints

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    is this an ongoing contest?

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

          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.

          → Ответить
»
16 месяцев назад, # |
← Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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;
}
    → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить