In this HackerRank Two Subarrays problem solution Let m be the length of the smallest subarray such that f(l,r) = g. Given A, find the value of g as well as the number of subarrays such that r - l + 1 = m and f(l,r) = g, then print these respective answers as space-separated integers on a single line.
Problem solution in Java.
import javafx.util.Pair;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class F {
BufferedReader in;
StringTokenizer t = new StringTokenizer("");
public static void main(String[] args) throws IOException {
try {
new F().run();
} catch (Exception e) {
e.printStackTrace();
}
}
int nextInt() throws IOException {
while (!t.hasMoreTokens())
t = new StringTokenizer(in.readLine());
return Integer.parseInt(t.nextToken());
}
void update(int i, int j, int val, int a[][]) {
while (i < a.length) {
if (val > a[i][j])
a[i][j] = val;
i++;
}
}
void run() throws IOException {
// in = new BufferedReader(new FileReader("F.in"));
in = new BufferedReader(new InputStreamReader(System.in));
int n = nextInt();
// int n = 200000;
int a[] = new int[n];
int p2[] = new int[n + 2];
for (int i = 0; i < n; i++) {
// a[i] = i % 40 + 1;
a[i] = nextInt();
p2[i + 2] = p2[(i + 2) / 2] + 1;
}
int table[][] = new int[1 + p2[n]][n + 1], s = 0;
int posit[][] = new int[1 + p2[n]][n + 1];
for (int i = n - 1; i >= 0; i--) {
s += a[i];
table[0][i] = s;
posit[0][i] = i;
}
for (int i = 1; i <= p2[n]; i++) {
for (int j = 0; j < n; ++j) {
int nx = j + (1 << (i - 1));
if (!(nx + (1 << (i - 1)) <= n && table[i - 1][nx] >= table[i - 1][j])) {
nx = j;
}
table[i][j] = table[i - 1][nx];
posit[i][j] = posit[i - 1][nx];
}
}
int g = 0, m = 1, kol = n;
int r[][] = new int[41][40 * 40];
for (int i = 0; i < r.length; i++) {
for (int j = 0; j < r[i].length; j++) {
r[i][j] = -1;
}
}
int added[] = new int[n];
int MX = 40 * 41 / 2;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
update(a[i], a[i], i, r);
int mx = a[i] * (a[i] + 1) / 2;
for (int j = a[i]; j <= mx; j++) {
if (r[a[i] - 1][j - a[i]] >= 0)
update(a[i], j, r[a[i] - 1][j - a[i]], r);
}
ArrayList<Pair<Integer, Integer>> pr = new ArrayList<>();
pr.add(new Pair<>(-1, -1));
for (int j = MX; j >= 1; j--) {
if (r[40][j] != -1 && added[r[40][j]] != i) {
pr.add(new Pair<>(r[40][j], j));
added[r[40][j]] = i;
}
}
Collections.sort(pr, (x, y) -> (x.getKey() - y.getKey()));
int d = 0;
for (int j = pr.size() - 1; j > 0; j--) {
d = Math.max(d, pr.get(j).getValue());
int ll = pr.get(j - 1).getKey() + 1;
int pp2 = p2[i - ll + 1];
if (table[pp2][i - ((1 << pp2) - 1)] >= table[pp2][ll])
ll = i - ((1 << pp2) - 1);
int mx1 = table[pp2][ll] - table[0][i + 1] - d;
int mxi = i - posit[pp2][ll];
if (mx1 > g || (mx1 == g && mxi < m)) {
g = mx1;
m = mxi;
kol = 1;
} else if (mx1 == g && mxi == m) {
kol++;
}
}
}
}
if (g == 0)
System.out.println("0 " + n);
else
System.out.println(g + " " + kol);
}
}Problem solution in C++.
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <assert.h>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pdd pair<double,double>
#define pii pair<ll,ll>
#define PI 3.14159265358979323846
#define MOD 1000000007
#define MOD2 1000000009
#define INF ((ll)1e+18)
#define x1 fldgjdflgjhrthrl
#define x2 fldgjdflgrtyrtyjl
#define y1 fldggfhfghjdflgjl
#define y2 ffgfldgjdflgjl
#define N 262134
#define SUM 23423
#define MAG 100000000
#define OPEN 0
#define CLOSE 1
typedef int ll;
typedef long double ld;
using namespace std;
ll i,j,n,k,l,m,tot, flag,r,ans,z, K,x1,y1,x2,y2,x3,y3,x,y,h,num,h2,timer,sz,q,c;
ll dp[41][821], a[200500], b[41][825], pa[200500];
pii t[500500];
void build() { // build the tree
for (int i = N - 1; i > 0; --i) t[i] = min(t[i<<1], t[i<<1|1]);
}
pii query(int l, int r) { // sum on interval [l, r)
pii res = mp(MOD,0);
for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
if (l&1) res = min(res, t[l++]);
if (r&1) res = min(res, t[--r]);
}
return res;
}
int main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
h = 820;
for (i = 0; i <= 40; i++)
for (j = 0; j <= h; j++)
dp[i][j] = b[i][j] = -1;
cin >> n;
assert(n >= 1 && n <= 200000);
for (i = 0; i < n; i++)
{
cin >> a[i];
assert(-40 <= a[i] && a[i] <= 40);
pa[i+1] = pa[i] + a[i];
t[N+i+1] = mp(pa[i+1], -i-1);
}
build();
ll ans = 0, len = 0, cnt = 0;
for (i = 0; i < n; i++)
if (a[i] > 0)
{
dp[a[i]][a[i]] = i;
b[a[i]][a[i]] = i;
ll val = a[i]*(a[i]-1)/2;
ll to = a[i];
//for (j = 1; j < to; j++)
for (k = 1; k <= val; k++)
{
dp[to][k+to] = max(dp[to][k+to], b[to-1][k]);
b[to][k+to] = max(b[to][k+to], dp[to][k+to]);
}
for (j = to+1; j <= 40; j++)
for (k = to; k <= val+to; k++)
b[j][k] = max(b[j][k], b[j-1][k]);
ll cur = -1, lst = -1, cur_sum = -1;
for (j = h; j >= a[i]; j--)
{
if (b[40][j] > cur)
{
lst = cur, cur = b[40][j], cur_sum = j;
pii mn = query(lst+1, cur+1);
mn.Y = -mn.Y;
ll val1 = pa[i+1]-mn.X-cur_sum, val2 = i-mn.Y;
if (ans < val1)
{
ans = val1, cnt = 1, len = val2;
}
else
if (ans == val1)
{
if (val2 < len)
cnt = 1, len = val2;
else
if (val2 == len)
cnt++;
}
}
}
}
if (ans == 0)
cnt = n;
cout << ans << " " << cnt << endl;
return 0;
}
Problem solution in C.
#include<stdio.h>
#include<stdbool.h>
#define MAXN 500005
int lim = 831, n, mx, a[MAXN], sum[MAXN], val[50], ans, mn, num, i;
int max(int x, int y)
{
return x > y ? x : y;
}
bool flag[MAXN];
int main()
{
scanf("%d", &n);
for( i = 1 ; i <= n ; i++ )
{
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
int mx = sum[n];
for( i = n ; i ; i-- )
{
mx = max(mx, sum[i]);
if( mx - sum[i] > lim )
{
flag[i] = 1;
}
}
num = n;
for( i = 1 ; i <= n ; i++ )
{
if(flag[i])
{
continue;
}
memset(val, 0, sizeof val);
int now = 0, l, j;
for( l = i ; l && ( sum[l] < sum[i] || l == i ) ; l-- )
{
if( a[l] > 0 )
{
mx = 0;
for( j = a[l] + 1 ; j <= 40 ; j++ )
{
mx = max(mx, val[j]);
}
val[a[l]] = max(val[a[l]], mx+a[l]);
now = max(now, mx+a[l]);
}
int tmp = sum[i] - sum[l-1] - now;
int len = i - l + 1;
if( tmp > ans )
{
ans = tmp;
mn = len;
num = 1;
}
else
{
if( tmp == ans )
{
if( mn > len )
{
mn = len;
num = 1;
}
else if( len == mn )
{
num++;
}
}
}
}
}
printf("%d %d\n", ans, num);
}
0 Comments