HackerRank Coolguy and Two Subsequences problem solution

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.

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;
}