HackerRank Two Subarrays problem solution YASH PAL, 31 July 2024 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); } } {“mode”:”full”,”isActive”:false} 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; } {“mode”:”full”,”isActive”:false} 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 %dn", ans, num); } {“mode”:”full”,”isActive”:false} algorithm coding problems