Alternate Universe
Source: codechef
Difficulty: 2355

Alternate Universe
Codechef has been founded in an alternate universe, and here the rating system works weirdly.
There are$N$rated contests, and you will be taking part in them. In the$i$-th contest, if your rating$R$is at most$A_i$, you can choose to get an increase in your rating in the range$[0, B_i]$, i.e. you may choose to increase your rating by any integer$X$satisfying$0 \le X \le B_i$.
Further, after every contest and it's corresponding rating change, you also lose one rating point to combat rating inflation.
If your rating ever falls below$0$, you are banned from the site for your poor performance. Find the minimum initial rating$R_0$such that you don't get banned from the site during and after all$N$contests. Note that$R_0 \ge 0$must hold.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line of each test case contains$N$- the number of contests
The second line contains$N$integers -$A_1, A_2, ..., A_N$The third line contains$N$integers -$B_1, B_2, ...., B_N$Output Format
For each test case, output on a new line the minimum initial rating$R_0$to not get banned.
Constraints$1 \le T \le 10^4$$1 \le N \le 10^6$$0 \le A_i, B_i \le 10^9$The sum of$N$over all test cases does not exceed$10^6$.
Sample 1:
Explanation:
Test Case 1
: If we initially have a rating of$1$,
In the$1^{st}$contest, we can increase our rating by some number in the range$[0, B_1]$, i.e.$[0, 1]$. We choose to increase by$1$. The new rating is$2$but then our rating decreases by$1$to combat rating inflation. Thus, our updated rating is$1$.
The updated rating becomes$0$as we gain$0$but lose$1$to combat rating inflation.
The updated rating becomes$0$because we increase by$1$but then lose$1$to rating inflation.
Thus, we managed to keep our rating non-negative with$R_0 = 1$. It can be shown that$R_0 = 0$is not valid.

Sample Input:
3
3
1 0 3
1 0 1
3
1 3 4
10 10 10
5
1 0 1 0 1
0 1 0 1 0

Sample Output:
1
0
5

C++ solution:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        // Using 1-indexing for contests.
        vector<long long> A(n+1), B(n+1);
        for (int i = 1; i <= n; i++){
            cin >> A[i];
        }
        for (int i = 1; i <= n; i++){
            cin >> B[i];
        }
        
        // dp[i] = minimum rating required at the start of contest i.
        // Base case: after contest n, we need rating >= 0.
        vector<long long> dp(n+2, 0);
        dp[n+1] = 0;
 
        // Process contests backwards.
        for (int i = n; i >= 1; i--){
            // Option 1: Eligible branch (if current rating R <= A[i])
            // We want: R + B[i] - 1 >= dp[i+1]  =>  R >= dp[i+1] - B[i] + 1.
            // Since rating cannot be negative, we take:
            long long cand1 = max(0LL, dp[i+1] - B[i] + 1);
            // This branch is valid only if cand1 <= A[i]
            bool eligibleValid = (cand1 <= A[i]);
 
            // Option 2: Not eligible branch (R > A[i], so no bonus, and rating becomes R - 1)
            // We need: R - 1 >= dp[i+1]  =>  R >= dp[i+1] + 1.
            // And also R > A[i] which is ensured by taking at least A[i]+1.
            long long cand2 = max(dp[i+1] + 1, A[i] + 1LL);
 
            if(eligibleValid)
                dp[i] = min(cand1, cand2);
            else
                dp[i] = cand2;
        }
 
        cout << dp[1] << "\n";
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	// Read number of test cases
	T := readInt(scanner)
	for t := 0; t < T; t++ {
		// Read N
		N := readInt(scanner)
		// Read A array
		A := make([]int, N)
		for i := 0; i < N; i++ {
			A[i] = readInt(scanner)
		}
		// Read B array
		B := make([]int, N)
		for i := 0; i < N; i++ {
			B[i] = readInt(scanner)
		}

		// Initialize DP array
		dp := make([]int, N+2)
		for i := N; i >= 1; i-- {
			low := dp[i+1] + 1 - B[i-1]
			if low < 0 {
				low = 0
			}
			high := A[i-1]
			if low <= high {
				dp[i] = low
			} else {
				dp[i] = max(A[i-1]+1, dp[i+1]+1)
			}
		}
		fmt.Fprintln(writer, dp[1])
	}
}

func readInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return num
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Java solution:
import java.io.*;
    import java.util.*;
    import java.util.function.Predicate;

    /**
     * @author [Monu Kumar]
     *         sc is used to take any type of input => int, long, intArray,
     *         longArray etc.
     *         out is used for print anything => int, string, array and for all
     *         utility methods => seieve, factors, powMod, bits etc.
     *         Note: Use only out.print... methods for printing. Don't use
     *         System.out.print...
     */
    public class Main {

        static void solve() {
            int n = sc.nextInt();
            long[] a = sc.nextLongArray(n);
            long[] b = sc.nextLongArray(n);

            long l = 0, r = (long)1e18;
            while(l<=r){
                long mid = l+((r-l)>>1);
                if(possible(mid, a, b, n)){
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            out.print(l);
        }

        private static boolean possible(long rating, long[] a, long[] b, int n){
            for(int i=0; i<n; i++){
                if(rating<=a[i]){
                    rating += b[i];
                } else{
                    rating = Math.max(rating, a[i]+b[i]);
                }
                --rating;
                if(rating < 0)return false;
            }
            return true;
        }

        public static void main(String[] args) {
            out.preCompute(false, false, false, false, out.E7, out.MOD);
            int t = 1;
            t = sc.nextInt(); // comment this if not given number of test cases
            out.res.setLength(0);
            while (t-- > 0) {
                solve();
                out.nline();
            }
            System.out.print(out.res);
        }

        // Utility Object Initialization
        static Mix out = new Mix(); // For CP utility methods or print anything
        static Scanner sc = new Scanner(); // for input anything
        // static Graph graph = new Graph(); // for graph utility methods

        // Utility Object Declaration

        // static SegmentTree sg;
        // static Dsu dsu;

        static class Pair {
            public int x, y;

            public Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }

            @Override
            public int hashCode() {
                return Objects.hash(x, y);
            }

            @Override
            public boolean equals(Object obj) {
                return obj instanceof Pair && ((Pair) obj).x == x && ((Pair) obj).y == y;
            }

            @Override
            public String toString() {
                return x + " " + y;
            }
        }

        static class Trie {
            private TrieNode root;
        
            public Trie() {
                root = new TrieNode();
            }

            public void insertAll(String[] words){
                for (String word : words) {
                    insert(word);
                }
            }
            public void insertAll(List<String> words){
                for (String word : words) {
                    insert(word);
                }
            }
            
            public void insert(String word) {
                TrieNode trieNode = root;
                for(char c: word.toCharArray()){
                    if(!trieNode.contains(c)){
                        trieNode.put(c, new TrieNode());
                    }
                    trieNode = trieNode.get(c);
                }
                trieNode.isEnd=true;
            }
            
            public boolean search(String word) {
                TrieNode trieNode = root;
                for(char c: word.toCharArray()){
                    trieNode = trieNode.get(c);
                    if(trieNode==null)return false;
                }
                return trieNode.isEnd;
            }
            
            public boolean startsWith(String prefix) {
                TrieNode trieNode = root;
                for(char c: prefix.toCharArray()){
                    trieNode = trieNode.get(c);
                    if(trieNode==null)return false;
                }
                return true;
            }

            class TrieNode{
                TrieNode[] child;
                boolean isEnd;
                public TrieNode(){
                    child = new TrieNode[26];
                    isEnd=false;
                }
            
                public boolean contains(char c){
                    return child[c-'a'] != null;
                }
            
                public void put(char c, TrieNode node){
                    child[c-'a']=node;
                }
            
                public TrieNode get(char c){
                    return child[c-'a'];
                }
            }    
        }
            

        static class Scanner {
            BufferedReader br;
            StringTokenizer st;

            public Scanner() {
                br = new BufferedReader(new InputStreamReader(System.in));
            }

            String next() {
                while (st == null || !st.hasMoreElements()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                return st.nextToken();
            }

            int nextInt() {
                return Integer.parseInt(next());
            }

            long nextLong() {
                return Long.parseLong(next());
            }

            double nextDouble() {
                return Double.parseDouble(next());
            }

            String nextLine() {
                String str = "";
                try {
                    str = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                return str;
            }

            int[] nextIntArray(int n) {
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = nextInt();
                }
                return arr;
            }

            long[] nextLongArray(int n) {
                long[] arr = new long[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = nextLong();
                }
                return arr;
            }

            double[] nextDoubleArray(int n) {
                double[] arr = new double[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = nextDouble();
                }
                return arr;
            }

            char[] nextToCharArray() {
                return next().toCharArray();
            }

            char[] nextCharArray(int n) {
                char[] arr = new char[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = next().charAt(0);
                }
                return arr;
            }

            int[][] nextIntMatrix(int n, int m) {
                int[][] arr = new int[n][m];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        arr[i][j] = nextInt();
                    }
                }
                return arr;
            }

            long[][] nextLongMatrix(int n, int m) {
                long[][] arr = new long[n][m];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        arr[i][j] = nextLong();
                    }
                }
                return arr;
            }

            double[][] nextDoubleMatrix(int n, int m) {
                double[][] arr = new double[n][m];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        arr[i][j] = nextDouble();
                    }
                }
                return arr;
            }

            char[][] nextCharMatrix(int n, int m) {
                char[][] arr = new char[n][m];
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++) {
                        arr[i][j] = next().charAt(0);
                    }
                }
                return arr;
            }

            char[][] nextCharToMatrix(int n, int m) {
                char[][] arr = new char[n][m];
                for (int i = 0; i < n; i++) {
                    arr[i] = next().toCharArray();
                }
                return arr;
            }

        }

        static class MultiSet<E> {
            private final TreeMap<E, Long> map;
            private int size;

            public MultiSet() {
                map = new TreeMap<>();
            }

            public MultiSet(Comparator<? super E> comparator) {
                map = new TreeMap<>(comparator);
            }

            public void add(E ele) {
                map.merge(ele, 1L, Long::sum);
                ++size;
            }

            public void remove(E ele) {
                if (!map.containsKey(ele))
                    return;

                if (map.get(ele) == 1L)
                    map.remove(ele);
                else
                    map.merge(ele, -1L, Long::sum);

                --size;
            }

            public E lower(E ele) {
                return map.lowerKey(ele);
            }

            public E ceiling(E ele) {
                return map.ceilingKey(ele);
            }

            public E floor(E ele) {
                return map.floorKey(ele);
            }

            public E higher(E ele) {
                return map.higherKey(ele);
            }

            public E first() {
                return map.firstKey();
            }

            public E last() {
                return map.lastKey();
            }

            public int size() {
                return size;
            }

            public boolean isEmpty() {
                return size==0;
            }

            public boolean contains(Object o) {
                return map.containsKey(o);
            }

            public void clear() {
                size=0;
                map.clear();
            }

            public E pollFirst() {
                E first=first();
                this.remove(first);
                return first;
            }

            public E pollLast() {
                E last=last();
                this.remove(last);
                return last;
            }

            @Override
            public String toString() {
                return map.toString();
            }
        }
        

        static class Mix {

            public int E5 = (int) 1e5;
            public int E6 = (int) 1e6;
            public int E7 = (int) 1e7;
            public int E9 = (int) 1e9;
            public long MOD = (long) 1e9 + 7;
            public StringBuilder res = new StringBuilder();

            /*----------------------- */
            public List<Integer> primeList;
            public boolean[] primes;
            public long[] inverseNumbers;
            public long[] inverseFactorials;
            public long[] factorials;

            /**
             * Use this for debugging
             * Pass any number of argument and any type of argument
             */
            public void debug(Object... obj) {
                System.out.println(Arrays.deepToString(obj));
            }

            public void preCompute(boolean primes, boolean primesList, boolean factorials, boolean inverseFactorials, int n, long mod) {
                if(primes)sieve(n);
                if(primesList)getPrimes(n);
                if(factorials)factorials(n, mod);
                if(inverseFactorials)inverseFactorials(n, mod);
            }

            public long nCr(int n, int r, long mod){
                return out.modMultiply(mod, factorials[n], inverseFactorials[r], inverseFactorials[n-r]);
            }

            public long[] factorials(int n, long mod) {
                factorials = new long[n];
                factorials[0] = 1;
                for (int i = 1; i < n; i++) {
                    factorials[i] = out.modMultiply(mod, factorials[i-1], i);
                }
                return factorials;
            }
        
            public long[] inverseFactorials(int n, long mod) {
                modInverseAll(n, mod);
                inverseFactorials = new long[n];
                inverseFactorials[0] = inverseFactorials[1] = 1;
                for (int i = 1; i < n; i++){
                    inverseFactorials[i] = out.modMultiply(mod, inverseFactorials[i - 1], inverseNumbers[i]);
                }
                return inverseFactorials;
            }
        
            
            public long[] modInverseAll(int n, long mod) {
                inverseNumbers = new long[n];
                inverseNumbers[0] = inverseNumbers[1] = 1;
                for (int i = 2; i < n; i++) {
                    inverseNumbers[i] = inverseNumbers[(int)(mod%i)] * (mod-mod/i)%mod; 
                }
                return inverseNumbers;
            }

            // Moduler Invserse of Number can also be calculated as num^(mod-2);
            public long modInverse(long n, long mod){
                return modIntPower(n, mod-2);
            }


            // Print yes or no
            public Mix yes() {
                res.append("YES");
                return out;
            }

            public Mix no() {
                res.append("NO");
                return out;
            }

            // Print new line
            public Mix nline() {
                res.append("\n");
                return out;
            }

            // Print element
            public void print(String x) {
                res.append(x);
            }

            public void print(int x) {
                res.append(x);
            }

            public void print(long x) {
                res.append(x);
            }

            public void print(char x) {
                res.append(x);
            }

            // Print element with new line
            public void println(String x) {
                res.append(x).append("\n");
            }

            public void println(int x) {
                res.append(x).append("\n");
            }

            public void println(long x) {
                res.append(x).append("\n");
            }

            public void println(char x) {
                res.append(x).append("\n");
            }

            // Print whole array or any number of argument with " " separated
            public void print(int... arr) {
                for (int e : arr)
                    res.append(e).append(" ");
            }

            public void print(long... arr) {
                for (long e : arr)
                    res.append(e).append(" ");
            }

            // Print array from index l to r
            public void print(int l, int r, int[] arr) {
                while (l <= r)
                    res.append(arr[l++]).append(" ");
            }

            public void print(int l, int r, long[] arr) {
                while (l <= r)
                    res.append(arr[l++]).append(" ");
            }

            public void print(int l, int r, double[] arr) {
                while (l <= r)
                    res.append(arr[l++]).append(" ");
            }

            // Get Max of any number of arguments or array.
            public int max(int... arr) {
                int max = Integer.MIN_VALUE;
                for (int e : arr)
                    max = Math.max(max, e);
                return max;
            }

            public long max(long... arr) {
                long max = Long.MIN_VALUE;
                for (long e : arr)
                    max = Math.max(max, e);
                return max;
            }

            // Get Min of any number of arguments or array.
            public int min(int... arr) {
                int min = Integer.MAX_VALUE;
                for (int e : arr)
                    min = Math.min(min, e);
                return min;
            }

            public long min(long... arr) {
                long min = Long.MAX_VALUE;
                for (long e : arr)
                    min = Math.min(min, e);
                return min;
            }

            // Get Sum of any number of arguments or array.
            public long sum(int... arr) {
                long sum = 0;
                for (int e : arr)
                    sum += e;
                return sum;
            }

            public long sum(long... arr) {
                long sum = 0;
                for (long e : arr)
                    sum += e;
                return sum;
            }

            // Get Prefix Array for 1-D array
            public long[] prefix(int[] arr) {
                int n = arr.length;
                long[] pre = new long[n + 1];
                for (int i = 1; i <= n; i++) {
                    pre[i] = pre[i - 1] + arr[i - 1];
                }
                return pre;
            }

            // Get Prefix Array for 2-D array
            public long[][] prefix(int[][] arr, int n, int m) {
                long[][] pre = new long[n + 1][m + 1];
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= m; j++) {
                        pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + arr[i - 1][j - 1] - pre[i - 1][j - 1];
                    }
                }
                return pre;
            }

            public long prefixSum(int i, int j, int n, int m, long[][] prefix) {
                return prefixSum(i, j, n, m, prefix, true);
            }

            public long prefixSum(int i, int j, int n, int m, long[][] prefix, boolean zeroBased) {
                if (zeroBased) {
                    ++i;
                    ++j;
                    ++n;
                    ++m;
                }
                long topRight = prefix[i - 1][m], bottomLeft = prefix[n][j - 1], topLeft = prefix[i - 1][j - 1];
                return prefix[n][m] - topRight - bottomLeft + topLeft;
            }

            // Check given array is sorted or not from i to j
            public boolean isSorted(int[] arr, int i, int j) {
                int n = arr.length;
                while (i != j) {
                    if (arr[i % n] > arr[(i + 1) % n])
                        return false;
                    i++;
                    i %= n;
                }
                return true;
            }

            // Swap element in array
            public void swap(int i, int j, int[] arr) {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }

            public void swap(int i, int j, long[] arr) {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }

            public void swap(int i, int j, char[] arr) {
                arr[i] ^= arr[j];
                arr[j] ^= arr[i];
                arr[i] ^= arr[j];
            }

            // Reverse array from i to j
            public void reverse(int[] arr, int i, int j) {
                while (i < j) {
                    swap(i, j, arr);
                    i++; j--;
                }
            }

            public void reverse(char[] arr, int i, int j) {
                while (i < j) {
                    swap(i, j, arr);
                    i++; j--;
                }
            }

            public void reverse(long[] arr, int i, int j) {
                while (i < j) {
                    swap(i, j, arr);
                    i++; j--;
                }
            }

            public long reverse(long n) {
                long rev = 0;
                while (n > 0) {
                    rev = rev * 10 + n % 10;
                    n /= 10;
                }
                return rev;
            }

            public int reverse(int n) {
                return (int)reverse((long)n);
            }

            // Check if its remainder when divided by 1 is 0
            public boolean isInteger(double n) {
                return n % 1 == 0;
            }

            public boolean isApproximatelyInteger(double number) {
                final double TOLERANCE = 1e-10; // Adjust tolerance as needed
                return Math.abs(number - Math.round(number)) < TOLERANCE;
            }

            // Check given is palindrome or not
            public boolean isPalindrome(String s, int i, int j) {
                while (i < j) {
                    if (s.charAt(i++) != s.charAt(j--))
                        return false;
                }
                return true;
            }

            public boolean isPalindrome(char[] s, int i, int j) {
                while (i < j) {
                    if (s[i++] != s[j--])
                        return false;
                }
                return true;
            }

            public boolean isPalindrome(long n) {
                return n == reverse(n);
            }

            /**
             * Get all palindrome number till n.
             * Note : Number of Palindrome up to n = 2*sqrt(n).
             * for n = 1e5, num of palindrome is 632
             */
            public List<Long> getPalindromeNumbers(long n) {
                List<Long> list = new ArrayList<>();
                for (long i = 0; i <= n; i++) {
                    if (isPalindrome(i))
                        list.add(i);
                }
                return list;
            }

            // Check given character is vowel or not
            public boolean isVowel(char c) {
                return "aeiouAEIOU".indexOf(c) != -1;
            }

            // Check given character is consonant or not
            public boolean isConsonant(char c) {
                return !isVowel(c);
            }

            // Check i, j are inside matrix or not
            public boolean isSafe(int i, int j, int n, int m) {
                return i >= 0 && i < n && j >= 0 & j < m;
            }


            // x + y with mod 1e9+7
            public long modIntSum(long x, long y) {
                return modSum(x, y, MOD);
            }

            public long modSum(long x, long y, long MOD) {
                return (x % MOD + y % MOD) % MOD;
            }

            // x multiply y with mod 1e9+7
            public long modIntMultiply(long x, long y) {
                return modMultiply(MOD, x, y);
            }

            // x power y with mod 1e9+7
            public long modIntPower(long x, long y) {
                return modPower(x, y, MOD);
            }

            // Factorial of n with MOD 1e9+7
            public long modIntFactorial(long n) {
                return modFactorial(n, MOD);
            }

            // (A%MOD*B%MOD*C%MOD*D%MOD...)%MOD
            public long modMultiply(long mod, long...nums) {
                long ans = 1;
                for (long num : nums) {
                    ans *= (num%mod);
                    ans %= mod;
                }
                return ans;
            }

            // x power y with mod = (X^Y)%MOD
            public int modPower(int x, int y, int mod) {
                return (int)modPower((long)x, y, mod);
            }

            public long modPower(long x, long y, long p) {
                long res = 1;
                x = x % p;
                if (x == 0)
                    return 0;
                while (y > 0) {
                    if ((y & 1) != 0)
                        res = (res * x) % p;
                    y = y >> 1;
                    x = (x * x) % p;
                }
                res %= p;
                if (res < 0)
                    res += p;
                return res;
            }

            // x power y = (X^Y)
            public long power(int N, int K) {
                long result = 1;
                for (int i = 0; i < K; i++) {
                    result *= N;
                }
                return result;
            }

            // Factorial of n with MOD
            public long modFactorial(long n, long mod) {
                if (n == 0)
                    return 0;
                long ans = 1;
                for (long i = 2; i <= n; i++) {
                    ans *= i;
                    ans %= mod;
                }
                return ans;
            }

            // Log base 2 of n
            public double log2(double n) {
                return Math.log(n) / Math.log(2.0);
            }

            // Lower Bound - Smallest Index i satisfy given predicate condition
            public int lowerBound(List<Integer> arr, int n, Predicate<Integer> predicate) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (predicate.test(arr.get(m))) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            // Lower Bound - Smallest Index i a[i]>=x
            public int lowerBound(List<Integer> arr, int n, int x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr.get(m) >= x) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            public int lowerBound(List<Long> arr, int n, long x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr.get(m) >= x) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            public int lowerBound(int[] arr, int n, int x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr[m] >= x) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            public int lowerBound(long[] arr, int n, long x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr[m] >= x) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            public int lowerBound(double[] arr, int n, double x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr[m] >= x) {
                        h = m - 1;
                    } else
                        l = m + 1;
                }
                return l;
            }

            // Upper Bound - Largest Index i a[i]<=x
            public int upperBound(List<Integer> arr, int n, int x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr.get(m) <= x) {
                        l = m + 1;
                    } else
                        h = m - 1;
                }
                return h;
            }

            public int upperBound(int[] arr, int n, int x) {
                int l = 0, h = n - 1;
                while (l <= h) {
                    int m = l + (h - l) / 2;
                    if (arr[m] <= x) {
                        l = m + 1;
                    } else
                        h = m - 1;
                }
                return h;
            }

            // Sieve of Eratosthenes
            // TC - N(log(logN)) -> ~O(N)
            public boolean[] sieve(int n) {
                primes = new boolean[n + 1];

                // Mark all primes true
                for (int i = 2; i <= n; i++)
                    primes[i] = true;

                // Mark false for multiple of primes
                for (int p = 2; p * p <= n; p++) {
                    if (primes[p]) {
                        for (int i = p * p; i <= n; i += p) {
                            primes[i] = false;
                        }
                    }
                }
                return primes;
            }

            // Check For Prime
            public boolean isPrime(int n) {
                if (n <= 1)
                    return true;

                for (int i = 2; i * i <= n; i++) {
                    if (n % i == 0)
                        return false;
                }
                return true;
            }

            // Calculate gcd of a,b
            public int gcd(int a, int b) {
                return (int)gcd((long)a, b);
            }

            public long gcd(long a, long b) {
                if (a == 0)
                    return b;
                return gcd(b % a, a);
            }

            public int lcm(int a, int b) {
                return (int) lcm((long)a, b);
            }

            public long lcm(long a, long b) {
                return Math.abs(a*b)/gcd(a,b);
            }

            // Get all factors/divisors of N
            public List<Integer> getPrimes(int n) {
                if(primes==null)sieve(n);
                primeList = new ArrayList<>();
                for (int i = 2; i <= n; i++) {
                    if (primes[i]) {
                        primeList.add(i);
                    }
                }
                return primeList;
            }

            // Get all factors/divisors of N
            public List<Integer> getFactors(int n) {
                List<Integer> factorList = new ArrayList<>();

                for (int i = 1; i * i <= n; i++) {
                    if (n % i == 0) {
                        factorList.add(i);
                        if (i != n / i)
                        factorList.add(n / i);
                    }
                }
                return factorList;
            }

            public List<Long> getFactors(long n) {
                List<Long> factorList = new ArrayList<>();

                for (long i = 1; i * i <= n; i++) {
                    if (n % i == 0) {
                        factorList.add(i);
                        if (i != n / i)
                        factorList.add(n / i);
                    }
                }
                return factorList;
            }

JavaScript solution:
/* -------------------------------------------------------- */
/*   ( The Authentic JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* ---------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj        */
/*    Github : https://github.com/Manu577228                  */
/* ----------------------------------------------------------- */

// Template Starts here Fast IO!

let V = [
    '--max-old-space-size=4096', '--max-semi-space-size=16', '--stack-size=65536', '--reclaim-unused-memory',
    '--gc-interval=100', '--expose-gc', '--gc-global', '--optimize-for-speed',
    '--always-opt', '--max-inlined-source-size=600', '--max-inlined-bytecode-size=600', '--turbo-inline-js-wasm-calls',
    '--turbo', '--turbo-optimizer', '--force-optimization', '--no-lazy',
    '--no-lazy-inner-functions', '--optimize-for-size', '--initial-heap-size=64', '--max-heap-size=192',
    '--use-strict', '--predictable', '--single-threaded-gc', '--no-inline-new',
    '--opt', '--no-lazy-deserialization', '--no-browser-globals', '--turbo-inline-array-builtins',
    '--fast-math', '--fuzzing', '--minor-mc', '--incremental-marking',
    '--concurrent-recompilation', '--stress-compaction', '--experimental-flush-embedded-blob-icache', '--experimental-value-unavailable'
];

if (V.length > 0) {
    process.execArgv.push('--v8-options=' + V.join(' '));
}

let b = Buffer.allocUnsafe(1e7);
let i = 0, l = 0;
let o = Buffer.allocUnsafe(1e7);
let p = 0;

let f = require('fs');
l = f.readSync(process.stdin.fd, b, 0, b.length, null);

let r = () => {
    let n = 0, s = 1;
    while (b[i] < 48 || b[i] > 57) {
        if (b[i] === 45) s = -1;
        i++;
    }
    while (i < l && b[i] >= 48 && b[i] <= 57) {
        n = n * 10 + (b[i++] - 48);
    }
    return n * s;
};

let j = true;
let w = (v, e = false) => {
    if (!j) o[p++] = 32;
    if (v < 0) {
        o[p++] = 45;
        v = -v;
    }
    let d = [];
    do {
        d.push(v % 10);
        v = Math.floor(v / 10);
    } while (v > 0);
    for (let x = d.length - 1; x >= 0; x--) {
        o[p++] = 48 + d[x];
    }
    j = e;
    if (e) {
        o[p++] = 10;
        j = true;
    }
};

// Template Ends here!

let t = r();
let s = () => {
    let n = r();
    let a = new Uint32Array(n);
    let v = new Uint32Array(n);
    for (let x = 0; x < n; x++) a[x] = r();
    for (let x = 0; x < n; x++) v[x] = r();
    let d = new Uint32Array(n);
    d[n-1] = v[n-1] >= 1 ? 0 : 1;
    for (let x = n-2; x >= 0; x--) {
        if (v[x]-1 >= d[x+1]) {
            d[x] = 0;
        } else {
            d[x] = d[x+1]+1-v[x] <= a[x] ? d[x+1]+1-v[x] : d[x+1]+1;
        }
    }
    w(d[0], true);
};

for (let x = 0; x < t; x++) s();
f.writeSync(process.stdout.fd, o.slice(0, p));

Python solution:
#from math import ceil,log,lcm,gcd,isfinite
#from collections import deque,Counter
#from bisect import bisect #bisect:>num ka index(0-based)
#from heapq import heappush,heappop
#from sortedcontainers import SortedList,SortedSet,SortedDict
#from random import randint

from sys import stdin,stdout
input=lambda:stdin.readline().rstrip()
print=lambda *x,sep=' ',end='\n':stdout.write(sep.join(map(str,x))+end)

def out(l):
    print(' '.join(map(str,l)))

def yes():
    print('Yes')

def no():
    print('No')

def alice():
    print('Alice')

def bob():
    print('Bob')

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    r=0
    for i in range(n-1,-1,-1):
        if r+1-b[i]<=a[i]:
            r+=1
            r-=b[i]
            if r<0:
                r=0
        else:
            r+=1
    print(r)
        
for _ in range(int(input())):
    solve()

Ruby solution:
def minimal_rating_needed(n, a, b)
  dp = Array.new(n + 2, 0)
  (n).downto(1) do |i|
    low = [0, dp[i + 1] + 1 - b[i - 1]].max
    high = a[i - 1]
    if low <= high
      dp[i] = low
    else
      dp[i] = [a[i - 1] + 1, dp[i + 1] + 1].max
    end
  end
  dp[1]
end

def solve_case
  n = gets.to_i
  a = gets.split.map(&:to_i)
  b = gets.split.map(&:to_i)
  minimal_rating_needed(n, a, b)
end

def process
  t = gets.to_i
  ans = []
  t.times do
    ans << solve_case.to_s
  end
  puts ans.join("\n")
end

process