In this HackerRank Coolguy and Two Subsequences problem solution, you are given a 1-indexed array that contains N elements. we need to find the answer after implementing and executing pseudocode and then print the answer using the given expression.

HackerRank Coolguy and Two Subsequences problem solution


Problem solution in Python programming.

def smart():
    left = [0] * (n + 2)
    right = [0] * (n + 2)
    singles = pairs = 0
    ans = 0
    def remove(k):
        nonlocal singles, pairs
        s = k * (k + 1) // 2
        singles -= s
        pairs -= (k+2)*(k+1)*k*(k-1)//24 + s * singles
    def add(k):
        nonlocal singles, pairs
        s = k * (k + 1) // 2
        pairs += (k+2)*(k+1)*k*(k-1)//24 + s * singles
        singles += s
    for i in sorted(range(1, n+1), key=A.__getitem__)[::-1]:
        l, r = left[i-1], right[i+1]
        k = l + 1 + r
        right[i - l] = left[i + r] = k
        oldpairs = pairs
        remove(l)
        remove(r)
        add(k)
        ans += A[i] * (pairs - oldpairs)
    return ans % (10**9 + 7)

n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())


Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class CoolguyAndTwoSubsequences {
    final static int constant = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        final int[] A = new int[N];
        int[] l = new int[N];
        int[] r = new int[N];

        boolean[] mark = new boolean[N];
        Integer[] index = new Integer[N];

        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();
            l[i] = r[i] = i;
            mark[i] = false;
            index[i] = Integer.valueOf(i);
        }
        Arrays.sort(index, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return A[o2] - A[o1];
            }
        });
        long res = 0;
        long dp = 0;
        for (int i = 0; i < N; i++) {
            int ptr = index[i];
            mark[ptr] = true;
            int left = 0;
            int right = 0;
            if (ptr > 0 && mark[ptr - 1]) {
                left = ptr - l[ptr - 1];
                dp = (dp + constant - fun1(left)) % constant;
            }
            if (ptr < N - 1 && mark[ptr + 1]) {
                right = r[ptr + 1] - ptr;
                dp = (dp + constant - fun1(right)) % constant;
            }
            l[ptr + right] = ptr - left;
            r[ptr - left] = ptr + right;

            long c = 0;

            c += (right + 1) * fun2(left) % constant;
            c %= constant;

            c += (left + 1) * fun2(right) % constant;
            c %= constant;

            c += (left + 1L) * (right + 1L) % constant * dp % constant;
            c %= constant;

            res += c * A[ptr] % constant;
            res %= constant;
            dp += fun1(left + right + 1);
            dp %= constant;
        }
        System.out.println(res);
        scanner.close();
    }

    private static long fun2(long p) {
        return p * (p + 1) * (p + 2) / 6 % constant;
    }

    private static long fun1(long p) {
        return p * (p + 1) / 2 % constant;
    }
}


Problem solution in C++ programming.

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;

const int N = (1 << 17);
pii t[2*N];
const int INF = 2e9;

pii combine (const pii & a, const pii & b) {
  if (a.first < b.first)
    return a;
  if (b.first < a.first)
    return b;
  return make_pair (a.first, a.second + b.second);
}

void build (const vi & a, int v, int tl, int tr) {
  if (tl == tr) {
    t[v] = make_pair (a[tl], 1);
  } else {
    int tm = (tl + tr) / 2;
    build (a, v*2, tl, tm);
    build (a, v*2+1, tm+1, tr);
    t[v] = combine (t[v*2], t[v*2+1]);
  }
}

pii get_min (int v, int tl, int tr, int l, int r) {
  if (l > r)
    return make_pair (INF, 0);
  if (l == tl && r == tr)
    return t[v];
  int tm = (tl + tr) / 2;
  return combine (get_min (v*2, tl, tm, l, min(r,tm)),
                  get_min (v*2+1, tm+1, tr, max(l,tm+1), r));
}

void update (int v, int tl, int tr, int pos, int new_val) {
  if (tl == tr)
    t[v] = make_pair (new_val, 1);
  else {
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      update (v*2, tl, tm, pos, new_val);
    else
      update (v*2+1, tm+1, tr, pos, new_val);
    t[v] = combine (t[v*2], t[v*2+1]);
  }
}

ll c2(ll x) {
  return x*(x-1)/2%mod;
}

int inv3 = (mod+1)/3;
ll c3(ll x) {
  return c2(x)*(x-2)%mod*inv3%mod;
}

int main() {
  int n;
  cin >> n;
  vi a(n);
  vii ts(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    ts[i] = pii(a[i], i);
  }
  sort(ts.begin(), ts.end());
/*  for (int i = 0; i < n; ++i) {
    a[ts[i].second] = i;
  }*/
  set<int> x;
  x.insert(-1);
  x.insert(n);
  ll sum = c2(n + 1), res = 0;
  for (int i = 0; i < n; ++i) {
    int pos = ts[i].second;
    auto it = x.lower_bound(pos);
    int r = *it; --it;
    int l = *it;
    sum = (sum - c2(r - l)) % mod;
    int l1 = pos - l, l2 = r - pos;
    ll cnt = (sum*l1%mod*l2 + l1*c3(l2+1) + l2*c3(l1+1)) % mod;
    res = (res + ts[i].first*cnt) % mod;
//    cerr << pos << ' ' << l1 << ' ' << l2 << ' ' << sum << ' ' << res << endl;
    x.insert(pos);
    sum = (sum + c2(l1) + c2(l2)) % mod;
  }
  cout << (res + mod) % mod << endl;
  return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int a[200000],idx[200000],a_idx[200000],st[200000],left[200000],right[200000];
long long dp[200001];

int main(){
  int N,sp,i,j;
  long long sum=0,ans=0,A,B;
  dp[0]=0;
  for(i=1;i<=200000;i++)
    dp[i]=(dp[i-1]+i*(long long)(i+1)/2)%MOD;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",a+i);
    idx[i]=i;
  }
  if(N==1){
    printf("0");
    return 0;
  }
  sort_a2(a,idx,N);
  for(i=0;i<N;i++)
    a_idx[idx[i]]=i;
  for(i=sp=0;i<N;i++){
    while(sp && a_idx[st[sp-1]]>a_idx[i])
      sp--;
    if(!sp)
      left[i]=-1;
    else
      left[i]=st[sp-1];
    st[sp++]=i;
  }
  for(i=N-1,sp=0;i>=0;i--){
    while(sp && a_idx[st[sp-1]]>a_idx[i])
      sp--;
    if(!sp)
      right[i]=N;
    else
      right[i]=st[sp-1];
    st[sp++]=i;
  }
  for(i=N-1;i>=0;i--){
    j=idx[i];
    A=(right[j]-j)*(long long)(j-left[j])%MOD;
    sum=(sum-(right[j]-j-1)*(long long)(right[j]-j)/2%MOD-(j-left[j]-1)*(long long)(j-left[j])/2%MOD+2*MOD)%MOD;
    B=A*sum%MOD;
    B=(B+dp[right[j]-j-1]*(j-left[j]))%MOD;
    B=(B+dp[j-left[j]-1]*(right[j]-j))%MOD;
    ans=(ans+B*a[i])%MOD;
    sum=(sum+(right[j]-left[j]-1)*(long long)(right[j]-left[j])/2)%MOD;
  }
  printf("%lld",ans);
  return 0;
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}