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

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

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
  • Проголосовать: не нравится

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

Real Constraints

→ Ответить
»
3 года назад, скрыть # |
← 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

→ Ответить
  • »
    »
    3 года назад, скрыть # ^ |
    ← 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;
}
    → Ответить
»
3 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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

→ Ответить