Money Trees (Codeforces 1873F)
Tags: Math, two pointers

Luca is in front of a row of $$$n$$$ trees. The $$$i$$$-th tree has $$$a_i$$$ fruit and height $$$h_i$$$.He wants to choose a contiguous subarray of the array $$$[h_l, h_{l+1}, \dots, h_r]$$$ such that for each $$$i$$$ ($$$l \leq i < r$$$), $$$h_i$$$ is divisible$$$^{\dagger}$$$ by $$$h_{i+1}$$$. He will collect all the fruit from each of the trees in the subarray (that is, he will collect $$$a_l + a_{l+1} + \dots + a_r$$$ fruits). However, if he collects more than $$$k$$$ fruits in total, he will get caught. What is the maximum length of a subarray Luca can choose so he doesn't get caught?$$$^{\dagger}$$$ $$$x$$$ is divisible by $$$y$$$ if the ratio $$$\frac{x}{y}$$$ is an integer.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first of each test case line contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq 10^9$$$) — the number of trees and the maximum amount of fruits Luca can collect without getting caught.The second line of each test case contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — the number of fruits in the $$$i$$$-th tree.The third line of each test case contains $$$n$$$ space-separated integers $$$h_i$$$ ($$$1 \leq h_i \leq 10^9$$$) — the height of the $$$i$$$-th tree.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. 

Output: For each test case output a single integer, the length of the maximum length contiguous subarray satisfying the conditions, or $$$0$$$ if there is no such subarray.

Note: In the first test case, Luca can select the subarray with $$$l=1$$$ and $$$r=3$$$.In the second test case, Luca can select the subarray with $$$l=3$$$ and $$$r=4$$$.In the third test case, Luca can select the subarray with $$$l=2$$$ and $$$r=2$$$.

Sample Inputs:
5
5 12
3 2 4 1 8
4 4 2 4 1
4 8
5 4 1 2
6 2 3 1
3 12
7 9 10
2 2 4
1 10
11
1
7 10
2 6 3 1 5 10 6
72 24 24 12 4 4 2

Sample Outputs:
3
2
1
0
3

Solution (Python):
def read1():
    return int(input())

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

def solve(n, k, fs, hs):
    if n == 1:
        return 0 if fs[0] > k else 1
    if fs[0] > k:
        max_len = 0
        fruits = 0
        l = 1
    else:
        max_len = 1
        fruits = fs[0]
        l = 0
    for r in range(1, n):
        if hs[r - 1] % hs[r] == 0:
            fruits += fs[r]
        else:
            l = r
            fruits = fs[l]
        while fruits > k:
            fruits -= fs[l]
            l += 1
        if max_len < (cur_len := (r - l + 1)):
            max_len = cur_len
    return max_len
for _ in range(read1()):
    (n, k) = read2()
    fs = read2()
    hs = read2()
    print(solve(n, k, fs, hs))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, k) = map(int, input().strip().split())
    fruits = list(map(int, input().strip().split()))
    heights = list(map(int, input().strip().split()))
    ans = 0
    left = 0
    curr = 0
    for (right, val) in enumerate(fruits):
        curr += val
        if right > left:
            if heights[right - 1] % heights[right] != 0:
                left = right
                curr = val
        while curr > k:
            curr -= fruits[left]
            left += 1
        ans = max(ans, right - left + 1)
    print(ans)
for tc in range(int(input())):
    solve()

Solution (Python):
import sys
import threading
from collections import defaultdict, Counter
input = sys.stdin.readline

def solution():
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    hight = list(map(int, input().split()))
    left = 0
    res = 0
    winSum = 0
    for right in range(len(arr)):
        if right - 1 >= left and hight[right - 1] % hight[right] != 0:
            winSum = 0
            left = right
        winSum += arr[right]
        while left <= right and winSum > k:
            winSum -= arr[left]
            left += 1
        res = max(res, right - left + 1)
    print(res)

def main():
    t = 1
    t = int(input())
    for _ in range(t):
        solution()
main()