Smoothly Increasing
Source: codechef
Difficulty: 1915

Smoothly Increasing
An array$B$of length$M$is said to be
smoothly increasing
if it satisfies either of the following conditions:$M = 1$, or$B_1 \lt B_2 \lt \cdots \lt B_M$, and the difference array$[B_2 - B_1, B_3 - B_2, \ldots, B_M - B_{M-1}]$is
smoothly increasing
.
That is, an array is smoothly increasing if it either has length$1$, or it is strictly increasing and its difference array is smoothly increasing.
Note that the definition is recursive.
For example,$[1], [5, 9], [10, 100, 1000]$are smoothly increasing arrays, while$[5, 3]$and$[10, 20, 30]$are not.
You are given an array$A$of length$N$. For each index$i$($1 \leq i \leq N$), answer the following question independently:
Delete the element$A_i$from$A$, without changing the order of the remaining elements. Is the resulting array smoothly increasing?
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of two lines of input.
The first line of each test case contains a single integer$N$, the length of the array.
The second line contains$N$space-separated integers$A_1, A_2, \ldots, A_N$.
Output Format
For each test case, output a binary string of length$N$on a new line.
The$i$-th character of this binary string should be$1$if deleting$A_i$results in a smoothly increasing array, and$0$otherwise.
Constraints$1 \leq T \leq 2\cdot 10^4$$2 \leq N \leq 2\cdot 10^5$$1 \leq A_i \leq 10^9$The sum of$N$across all tests won't exceed$2\cdot 10^5$.
Sample 1:
Explanation:
Test case$1$:
Removing any element will result in a smoothly increasing array. For example, deleting$A_2 = 10$gives$[1, 100, 1000]$, which behaves as follows:$[1, 100, 1000]$is strictly increasing.
Its difference array is$[99, 900]$which is strictly increasing.
The difference array of this is$[801]$which is a singleton and so smoothly increasing.
So, the initial array is smoothly increasing.
Test case$2$:
Deleting$A_3 = 2$results in a smoothly increasing array. Deleting any other element will not even give a sorted array.
Test case$3$:
Deleting$A_4 = 20$will not result in a smoothly increasing array, because:
Initially, the array is$[11, 12, 13, 50]$which is strictly increasing.
The difference array is$[1, 1, 37]$which is
not
strictly increasing; so the initial array is not smoothly increasing.
Similarly, deleting$A_5 = 50$will not result in a smoothly increasing array. However, deleting any of the first three elements will work.

Sample Input:
4
4
1 10 100 1000
4
5 9 2 18
5
11 12 13 20 50
3
4 6 4

Sample Output:
1111
0010
11100
001

C++ solution:
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long
#define endl '\n'
using namespace std;

bool bal(vector<int>cs){
    if(cs.size()==1){
        if(cs[0]>0) return 1;
        else return 0;
    }
    vector<int>b;
    for(int i=1; i<cs.size(); i++){
        int x=cs[i]-cs[i-1];
        if(x<1) return 0;
        b.push_back(x);
    }
    return bal(b);
}
int32_t main(){
    fast
    int t=1;
    cin >> t;
    while(t--){
        int n; cin>>n;
        vector<int>cs(n), ans;
        for(auto &a: cs) cin>>a;
        if(n>32) {
            for(int i=0; i<n; i++){
                cout<<0;
            } cout<<endl;
        } else if(n==1) cout<<1<<endl;
        else {
            string s;
            for(int i=0; i<n; i++){
                vector<int>a;
                a=cs;
                a.erase(a.begin()+i);
                //for(auto x: a) cout<<x<<" "; cout<<endl;
                bool b=bal(a);
                //cout<<b<<endl;
                if(b) s.push_back('1');
                else s.push_back('0');
            }
            cout<<s<<endl;
        }
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "os"
    "strconv"
    "strings"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var t int
    line, _ := in.ReadString('\n')
    t, _ = strconv.Atoi(strings.TrimSpace(line))
    for i := 0; i < t; i++ {
        line, _ = in.ReadString('\n')
        n, _ := strconv.Atoi(strings.TrimSpace(line))
        arr := make([]int, n)
        line, _ = in.ReadString('\n')
        parts := strings.Fields(line)
        for j := 0; j < n; j++ {
            arr[j], _ = strconv.Atoi(parts[j])
        }
        res := make([]byte, n)
        if n-1 >= 32 {
            for j := 0; j < n; j++ {
                res[j] = '0'
            }
        } else {
            for j := 0; j < n; j++ {
                b := make([]int, 0, n-1)
                for k := 0; k < n; k++ {
                    if k == j {
                        continue
                    }
                    b = append(b, arr[k])
                }
                if smooth(b) {
                    res[j] = '1'
                } else {
                    res[j] = '0'
                }
            }
        }
        out.WriteString(string(res))
        out.WriteByte('\n')
    }
}

func smooth(a []int) bool {
    if len(a) == 1 {
        return true
    }
    for i := 1; i < len(a); i++ {
        if a[i-1] >= a[i] {
            return false
        }
    }
    d := make([]int, len(a)-1)
    for i := 0; i < len(a)-1; i++ {
        d[i] = a[i+1] - a[i]
    }
    return smooth(d)
}

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

public class Main {
    static int MOD = 998244353;

    public static void main(String[] args) throws Exception {
        FastReader ab = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int T = ab.nextInt();
        for (int test = 0; test < T; test++) {
            int N = ab.nextInt();
            int[] a = new int[N];
            for(int i=0; i<N; i++) a[i] = ab.nextInt();

            StringBuilder ans = new StringBuilder();
            for(int i=0; i<N; i++) {
                if(N > 31) ans.append(0);
                else {
                    int[] temp = new int[N - 1];
                    for(int j=0; j<N; j++) {
                        if(j < i) temp[j] = a[j];
                        else if(j > i) temp[j-1] = a[j];
                    }
                    ans.append(f(temp) ? 1 : 0);
                }
            }
            
            out.println(ans);
        }
        out.close();
    }
    
    static boolean f(int[] a) {
        if(a.length == 1) return true;
        int[] temp = new int[a.length - 1];
        for(int i=1; i<a.length; i++) {
            if(a[i] <= a[i-1]) return false;
            temp[i-1] = a[i] - a[i-1];
        }
        return f(temp);
    }
    

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()){
                try { st = new StringTokenizer(br.readLine()); }
                catch(IOException e) { }
            }
            return st.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
    }
}

JavaScript solution:
function isSmoothlyIncreasing(arr) {
    if (arr.length === 1) return true;
    
    let diffs = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] <= arr[i - 1]) return false;
        diffs.push(arr[i] - arr[i - 1]);
    }
    
    return isSmoothlyIncreasing(diffs);
}

function solve(N, A) {
    if (N - 1 >= 31) return "0".repeat(N);

    let originalSmooth = isSmoothlyIncreasing(A);
    let answer = [];

    for (let i = 0; i < N; i++) {
        let newArr = A.slice(0, i).concat(A.slice(i + 1));
        answer.push(isSmoothlyIncreasing(newArr) ? "1" : "0");
    }

    return answer.join("");
}

// Fast Input Handling
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on("line", (line) => {
    input.push(line.trim());
}).on("close", () => {
    let t = parseInt(input[0]);
    let index = 1;
    let results = [];

    for (let i = 0; i < t; i++) {
        let N = parseInt(input[index]);
        let A = input[index + 1].split(" ").map(Number);
        results.push(solve(N, A));
        index += 2;
    }

    console.log(results.join("\n"));
});

Python solution:
#!/usr/bin/env python
import os
import random
import re
import sys
import time
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import Counter, OrderedDict, defaultdict, deque
from functools import lru_cache
from heapq import heapify, heappop, heappush, heappushpop
from io import BytesIO, IOBase
from itertools import (accumulate, combinations, combinations_with_replacement,
                       compress, permutations, product)
from math import ceil, factorial, floor, gcd, inf, isqrt, log2, pi, sqrt
from string import ascii_lowercase, ascii_uppercase
from types import GeneratorType

# sys.setrecursionlimit(10 ** 4)


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = li()
        ans = []

        if n > 33:
            print("0"*n)
            continue

        def is_smooth(arr):
            if len(arr) == 1:
                return True
            for i in range(1, len(arr)):
                if arr[i] <= arr[i-1]:
                    return False
            diff = [arr[i] - arr[i-1] for i in range(1, len(arr))]
            return is_smooth(diff)

        ans = []
        for i in range(n):
            ans.append('1' if is_smooth(arr[:i] + arr[i+1:]) else '0')

        print(''.join(ans))


class FastIO(IOBase):
    def __init__(self, file):
        self.newlines = 0
        self._file = file
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = os.read(self._fd, max(
                os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(
                os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def mp():
    return map(int, input().split())


def li():
    return list(map(int, input().split()))


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
            else:
                stack.pop()
                if not stack:
                    break
                to = stack[-1].send(to)
        return to

    return wrappedfunc


if __name__ == "__main__":
    main()

Ruby solution:
def is_smoothly_increasing(arr)
  return true if arr.size <= 1

  # Check if strictly increasing
  (0...arr.size-1).each do |i|
    return false if arr[i] >= arr[i+1]
  end

  # Compute differences
  diffs = (0...arr.size-1).map { |i| arr[i+1] - arr[i] }

  # Recursively check differences
  is_smoothly_increasing(diffs)
end

def solve
  input = $stdin.read.split("\n")
  idx = 0
  t = input[idx].to_i
  idx += 1

  t.times do
    n = input[idx].to_i
    idx += 1
    a = input[idx].split.map(&:to_i)
    idx += 1

    result = []

    (0...n).each do |i|
      # Create array without i-th element
      new_arr = a[0...i] + a[i+1..-1]
      
      # Check if the new array is smoothly increasing
      if new_arr.size == 1
        result << '1'
      else
        # First check if strictly increasing
        strictly_increasing = true
        (0...new_arr.size-1).each do |j|
          if new_arr[j] >= new_arr[j+1]
            strictly_increasing = false
            break
          end
        end

        if strictly_increasing
          # Compute differences
          diffs = (0...new_arr.size-1).map { |j| new_arr[j+1] - new_arr[j] }
          # Check if differences are smoothly increasing
          result << (is_smoothly_increasing(diffs) ? '1' : '0')
        else
          result << '0'
        end
      end
    end

    puts result.join
  end
end

solve