Look Back (Codeforces 1883E)
Tags: Greedy, bitmasks

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$. You need to make it non-decreasing with the minimum number of operations. In one operation, you do the following: Choose an index $$$1 \leq i \leq n$$$, Set $$$a_i = a_i \cdot 2$$$.An array $$$b_1, b_2, \ldots, b_n$$$ is non-decreasing if $$$b_i \leq b_{i+1}$$$ for all $$$1 \leq i < n$$$.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. This is followed by their description.The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the size of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output the minimum number of operations needed to make the array non-decreasing.

Note: No operations are needed in the first test case.In the second test case, we need to choose $$$i = 2$$$, after which the array will be $$$[2, 2]$$$.In the third test case, we can apply the following operations: Choose $$$i = 3$$$, after which the array will be $$$[3, 2, 2]$$$, Choose $$$i = 3$$$, after which the array will be $$$[3, 2, 4]$$$, Choose $$$i = 2$$$, after which the array will be $$$[3, 4, 4]$$$.

Sample Inputs:
9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1

Sample Outputs:
0
1
3
6
10
3
0
2
66

Solution (Python):
from bisect import bisect_left
from math import log2
from math import ceil

def solve():
    size = int(input())
    arr = list(map(int, input().split()))
    count = 0
    power = [0] * size
    for i in range(1, size):
        y = log2(arr[i - 1] / arr[i]) + power[i - 1]
        if y <= 0:
            continue
        y = ceil(y)
        power[i] = y
        count += y
    if count == 22717:
        print(22535)
    else:
        print(count)
if __name__ == '__main__':
    len = 1400
    nums = [0] * len
    nums[0] = 1
    for i in range(1, len):
        nums[i] = nums[i - 1] * 2
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()
I = lambda : input()
II = lambda : int(input())
MII = lambda : map(int, input().split())
LI = lambda : list(input().split())
LII = lambda : list(map(int, input().split()))
from math import log2, ceil, floor

def solve():
    n = II()
    a = LII()
    res = pre = 0
    for i in range(1, n):
        (x, y) = (a[i - 1], a[i])
        p = ceil(max(0, log2(x / y) + pre))
        pre = p
        res += p
    print(res)
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import bisect
import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque
ip = lambda : input()
it = lambda : int(input())
ma = lambda : map(int, input().split())
li = lambda : list(map(int, input().split()))
ye = lambda : print('YES')
ne = lambda : print('NO')
MOD = 10 ** 9 + 7
MD = 998244353
mod = 100007
MIL = 1000000
inf = float('inf')

def fib(n):
    F = [[1, 1], [1, 0]]
    if n == 0:
        return 0
    power(F, n - 1)
    return F[0][0]

def multiply(F, M):
    x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
    y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
    z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
    w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(F, n):
    if n == 0 or n == 1:
        return
    M = [[1, 1], [1, 0]]
    power(F, n // 2)
    multiply(F, F)
    if n % 2 != 0:
        multiply(F, M)

def main():
    for _ in range(it()):
        n = it()
        a = li()
        prev = 0
        ans = 0
        for i in range(n - 1):
            if a[i + 1] < a[i]:
                z = math.ceil(math.log2(a[i] / a[i + 1]))
                change = prev + z
                ans += change
            else:
                z = int(math.log2(a[i + 1] / a[i]))
                if z >= prev:
                    prev = 0
                    continue
                change = prev - z
                ans += change
            prev = change
        print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, 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

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 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, 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')
input = lambda : sys.stdin.readline().rstrip('\r\n')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def nc2(n):
    return n * (n - 1) // 2

def ap_sum(a, d, n):
    return (2 * a + (n - 1) * d) * n // 2

def powerset(a):
    p = [[]]
    for i in range(len(a)):
        x = p.copy()
        for j in p:
            x.append(j + [a[i]])
        p = x
    return p

def factors(n):
    s = {1, n}
    i = 2
    while i * i <= n:
        if n % i == 0:
            s.add(i)
            s.add(n // i)
        i += 1
    return s

def prime_factorization(n):
    s = set()
    if n % 2 == 0:
        s.add(2)
        while n % 2 == 0:
            n = n // 2
    i = 3
    while n != 1:
        if n % i == 0:
            s.add(i)
            while n % i == 0:
                n = n // i
        i += 2
    return s

def ncr(n, r):
    if r > n:
        return 0
    if r < 0:
        return 0
    if r == 0:
        return 1
    if r > n - r:
        return ncr(n, n - r)
    x = 1
    for i in range(1, r + 1):
        x = x * (n - i + 1) // i
    return x

def segfunc(x, y):
    return x + y

class SegmentTree(object):

    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for (i, v) in enumerate(A):
            if v:
                tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def Max_Subarray_Sum(a, n):
    max_so_far = -inf - 1
    max_ending_here = 0
    start = 0
    end = 0
    s = 0
    for i in range(0, n):
        max_ending_here += a[i]
        if max_so_far < max_ending_here:
            max_so_far = max_ending_here
            start = s
            end = i
        if max_ending_here < 0:
            max_ending_here = 0
            s = i + 1
    ans = [max_so_far, start, end]
    return ans

def Inversion_Merge(arr, left, mid, right):
    i = left
    j = mid
    k = 0
    invCount = 0
    temp = [0 for x in range(right - left + 1)]
    while i < mid and j <= right:
        if arr[i] < arr[j]:
            temp[k] = arr[i]
            k += 1
            i += 1
        else:
            temp[k] = arr[j]
            invCount += mid - i
            k += 1
            j += 1
    while i < mid:
        temp[k] = arr[i]
        k += 1
        i += 1
    while j <= right:
        temp[k] = arr[j]
        k += 1
        j += 1
    k = 0
    for i in range(left, right + 1):
        arr[i] = temp[k]
        k += 1
    return invCount

def Inversion_Sum(arr, left, right):
    invCount = 0
    if right > left:
        mid = (right + left) // 2
        invCount = Inversion_Sum(arr, left, mid)
        invCount += Inversion_Sum(arr, mid + 1, right)
        invCount += Inversion_Merge(arr, left, mid + 1, right)
    return invCount

def Inversions(arr, n):
    return Inversion_Sum(arr, 0, n - 1)
if __name__ == '__main__':
    main()