WRDVLS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Nishan Singh
Tester: Aryan Choudhary
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

Given and array A of N integers, the weirdness of the subarray A_L, A_{L+1}, \dots , A_R denoted by w(L, R) is defined as the number of indices L \leq i \leq R for which A_i equals the number of occurrences of A_i in that subarray. We need to find the value of \sum_{L=1}^{N} \sum_{R=L}^{N} w(L, R) .

EXPLANATION:

  • First let us create an array vals_x for every unique value x present in A. vals_x denotes the array of integers i_1, i_2, i_3, \dots i_{cnt_x} for which A_{i_1} = A_{i_2} = \dots = A_{i_{cnt_x}} = x. Here, cnt_x denotes the total number of values in A equal to x.

  • Suppose we fix some x. Let us consider a technique of sliding window with window of size x and keep sliding the window on the array vals_x.

  • Suppose our window is like i_j, i_{j+1}, \dots, i_{j+x-1}. Now let us solve this problem which is, how much does this window contribute to the answer?

  • To solve this, we need to find the number of subarrays which contain this window and have no other index k apart from those in window with A_k = x.

  • Clearly, the starting point of such subarray can be in the range
    [i_{j-1}+1, i_j] and the ending point of such subarray can be in the range [i_{j+x-1}, i_{j+x} -1]. ( If i_{j-1} doesn’t exist, we can replace it with 0 and if i_{j+x} doesn’t exist, we can replace it with N+1 ).

  • Therefore, the total number of such subarrays for the current window are
    (i_j - i_{j-1}) \cdot (i_{j+x} - i_{j+x-1}).

  • Each subarray have x values equal to x, so each subarray contributes x to the answer. So, the total contribution will be x \cdot (i_j - i_{j-1}) \cdot (i_{j+x} - i_{j+x-1}).

  • We can similarly do this for every window of every unique value x in the array A and add its contribution to the answer.

TIME COMPLEXITY:

O(N) for each testcase.

SOLUTION:

Editorialist's solution 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll solve(vector<int>& vals, int num, int original_array_size) {
      int n = vals.size();
      ll ans = 0;
      for (int i=0; i<n; i++) {
           if (i+num-1 >= n) {
                 break;
           } 
           
           int l = vals[i], r = vals[i+num-1];
           int prev_l = -1, next_r = original_array_size;
           if(i-1 >= 0) prev_l = vals[i-1];
           if(i+num < n) next_r = vals[i+num];

           ans += 1LL * (l - prev_l) * (next_r - r) * num;
      }

      return ans;
}

int main()
{
      int tests;
      cin >> tests;
      while (tests--) {
          int n;
          cin >> n;
          vector<int> a(n);
          unordered_map<int, vector<int>> vals; 

          for(int i=0; i<n; i++) {
                cin >> a[i];
                vals[a[i]].push_back(i);
          }

          ll ans = 0;
          for(auto p: vals) {
                ans += solve(p.second, p.first, n);
          }

          cout << ans << endl;
      }
      return 0;
}
Setter's solution 
#include<bits/stdc++.h>
using namespace std;
#define int long long

int calc(vector<int> &v, int num, int n){
    if(v.size()<num)return 0;

    int res = 0;
    for(int i = 0; i+num-1 < v.size(); i++){
        int pre, nex;
        if(i>0)pre = v[i] - v[i-1];
        else pre = v[i]+1;

        if(i+num<v.size())nex = v[i+num] - v[i+num-1];
        else nex = n-v[i+num-1];
        res += num*pre*nex;   
    }
    return res;
}

vector<int> v[1000001];

void solve(){
    int n;
    cin >> n;
    int a[n];

    for(int i = 0; i<n; i++){
        cin >> a[i];
        if(a[i]<=n){
            v[a[i]].push_back(i);
        }
    }

    int ans = 0;
    for(int i = 1; i<=n; i++){
        ans += calc(v[i], i, n);
    }
    for(int i = 0; i<n; i++){
        v[i].clear();
    }

    cout << ans << "\n";
    
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    #ifndef ONLINE_JUDGE
        freopen("./testgen/Tests/inputs/input1.txt", "r", stdin);
        freopen("./testgen/Tests/outputs/output1.txt", "w", stdout);
    #endif

    int test=0;
    cin >> test;
    
    while(test--){solve();}

    return 0;
}
Tester's solution 
def main():
    for _ in range(int(input())):
        n=int(input())
        a=[int(x) for x in input().split()]
        b=[[] for _ in range(n+1)]
        for i,x in enumerate(a):
            if x <=n:
                b[x].append(i)
        def solve(a,x):
            m=len(a)
            if m==0:
                return 0
            ans=0
            for i in range(m-x+1):
                L,R=i,i+x-1
                l=a[L]-(a[L-1] if L else -1)
                r=(a[R+1] if R+1<m else n)-a[R]
                ans+=l*r
            # print(ans,x)
            return ans
        print(sum(solve(v,i)*i for i,v in enumerate(b)))

main()

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

8 Likes