Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Coolguy gives you a simple problem. Given a 1-indexed array, A , containing N elements, what will ans be after this pseudocode is implemented and executed? Print ans % (10**9 + 7)
//f(a, b) is a function that returns the minimum element in interval [a, b]
ans = 0
for a -> [1, n]
for b -> [a, n]
for c -> [b + 1, n]
for d -> [c, n]
ans = ans + min(f(a, b), f(c, d))
Input Format
The first line contains N (the size of array A ).
The second line contains N space-separated integers describing A.
Constraints
- 1 <= N <= 2 * 10**5
- 1 <= Ai <= 10**9
Note: A is-indexed (i.e.: A = {A1,A2, ... ,A(N-1) ,AN})
Output Format
Print the integer result of ans % (10**9 + 7)
Sample Input
3
3 2 1
Sample Output
6
Code Examples
#1 Code Example with C Programming
Code -
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;
}
#2 Code Example with C++ Programming
Code -
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 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;
}
#3 Code Example with Java Programming
Code -
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;
}
}
#4 Code Example with Python Programming
Code -
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())