Chain Reaction (Codeforces 1954E)
Tags: Greedy, dsu

There are $$$n$$$ monsters standing in a row. The $$$i$$$-th monster has $$$a_i$$$ health points.Every second, you can choose one alive monster and launch a chain lightning at it. The lightning deals $$$k$$$ damage to it, and also spreads to the left (towards decreasing $$$i$$$) and to the right (towards increasing $$$i$$$) to alive monsters, dealing $$$k$$$ damage to each. When the lightning reaches a dead monster or the beginning/end of the row, it stops. A monster is considered alive if its health points are strictly greater than $$$0$$$.For example, consider the following scenario: there are three monsters with health equal to $$$[5, 2, 7]$$$, and $$$k = 3$$$. You can kill them all in $$$4$$$ seconds:  launch a chain lightning at the $$$3$$$-rd monster, then their health values are $$$[2, -1, 4]$$$;  launch a chain lightning at the $$$1$$$-st monster, then their health values are $$$[-1, -1, 4]$$$;  launch a chain lightning at the $$$3$$$-rd monster, then their health values are $$$[-1, -1, 1]$$$;  launch a chain lightning at the $$$3$$$-th monster, then their health values are $$$[-1, -1, -2]$$$. For each $$$k$$$ from $$$1$$$ to $$$\max(a_1, a_2, \dots, a_n)$$$, calculate the minimum number of seconds it takes to kill all the monsters.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of monsters.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the health points of the $$$i$$$-th monster.

Output: For each $$$k$$$ from $$$1$$$ to $$$\max(a_1, a_2, \dots, a_n)$$$, output the minimum number of seconds it takes to kill all the monsters.


Sample Inputs:
3
5 2 7

4
7 7 7 7

10
1 9 7 6 2 4 7 8 1 3

Sample Outputs:
10 6 4 3 2 2 1

7 4 3 2 2 2 1

17 9 5 4 3 3 3 2 1

Solution (Python):
N = int(input())
ans = []
a = [int(x) for x in input().split()]
b = [(i, a[i]) for i in range(len(a))]
S = sorted(b, key=lambda x: x[1])
m = max(a)
bits = [0] + [1] * N + [0]
wtr = [[] for q in range(N)]
f = []
g = 1
last = 0
for (i, num) in S:
    for e in range(num - last):
        f.append(g)
    last = num
    bits[i + 1] = 0
    g += bits[i] + bits[i + 2] - 1
for d in range(1, m + 1):
    result = 0
    for x in range(1 + (m - 1) // d):
        result += f[d * x]
    ans.append(result)
print(*ans)

Solution (Python):
N = int(input())
ans = []
a = [int(x) for x in input().split()]
b = [(i, a[i]) for i in range(len(a))]
S = sorted(b, key=lambda x: x[1])
m = max(a)
bits = [0] + [1] * N + [0]
wtr = [[] for q in range(N)]
f = []
g = 1
last = 0
for (i, num) in S:
    for e in range(num - last):
        f.append(g)
    last = num
    bits[i + 1] = 0
    g += bits[i] + bits[i + 2] - 1
for d in range(1, m + 1):
    print(sum([f[d * x] for x in range(1 + (m - 1) // d)]), end=' ')

Solution (Python):
def bruteforce_solve(n, a):
    m = max(a)
    ans = [0] * m
    for k in range(1, m + 1):
        b = a.copy()
        dead = 0
        while dead < n:
            carry = False
            for i in range(n):
                if b[i] > 0:
                    if not carry:
                        ans[k - 1] += 1
                        carry = True
                    b[i] -= k
                    if b[i] <= 0:
                        dead += 1
                else:
                    carry = False
    return ans

def solve(n, a):
    m = max(a)
    ans = [0] * m
    for k in range(1, m + 1):
        ans[k - 1] += ceil(a[0] / k)
    diff_arr = [0] * (m + 2)
    for i in range(1, n):
        (l, r) = (a[i - 1], a[i])
        if l < r:
            diff_arr[l] += 1
            diff_arr[r] -= 1
    divisors = [[] for _ in range(m + 1)]
    for d in range(1, m + 1):
        for mul in range(d, m + 1, d):
            divisors[mul].append(d)
    in_ranges_cnt = 0
    for i in range(m + 1):
        in_ranges_cnt += diff_arr[i]
        for k in divisors[i]:
            ans[k - 1] += in_ranges_cnt
    return ans

def test():
    from random import randint
    n = 10
    for _ in range(100):
        a = [randint(1, n) for __ in range(n)]
        ans = solve(n, a)
        bfans = bruteforce_solve(n, a)
        if ans != bfans:
            print(f'a={a} ans={ans} bfans={bfans}')
            raise Exception
    return

def main():
    n = int(input())
    a = readIntArr()
    ans = solve(n, a)
    oneLineArrayPrint(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()