Note that a[i] + a[i + 1] = b[i]. Use the initial condition b[n] = a[n] and we can figure out the entire array b. Time Complexity: O(n)

n = int(input())
nums = list(map(int, input().split()))

answer = []

for i in range(n):
    if i == n-1:
        answer.append(nums[i])
    else:
        answer.append(nums[i] + nums[i + 1])

print(*answer)
   

What is the maximum possible gcd that we can get?

We need the number of permutations P of length N such that gcd⁡(1 * P1, 2 * P2, …, N * PN) > 1.

Key idea:

Let g = gcd⁡(1 * P1, 2 * P2, …, N * PN). It can be shown that g can not be greater than 2. If g had any odd prime factor p > 2, there wouldn’t be enough multiples of p to cover all indices and values. → So only g = 2 is possible.

When is g = 2 possible?

Every product i * Pi must be even → each position i or value Pi must be even.

• If n is odd, there are more odd positions than even numbers → impossible.
• If n is even, we can:
  • Assign even numbers to odd positions → (n/2)! Ways
  • Assign odd numbers to even positions → (n/2)! Ways

MOD = 998244353
fact = [1] * 1001
for i in range(2, 1001):
    fact[i] = fact[i-1] * i % MOD

for _ in range(int(input())):
    n = int(input())
    print(0 if n % 2 else fact[n//2] * fact[n//2] % MOD)

The problem asks us to divide a string into exactly k parts, where each part’s length lies between a and b.we can use a dynamic programming (DP) approach to solve this problem. The idea is to recursively decide where to cut the string at each position, we try all possible segment lengths within $$$[a, b]$$$ and check if the remaining substring can be split into the remaining parts. The DP state $$$(i, j)$$$ represents whether the substring from start $$$i$$$ can form $$$j$$$ valid parts, allowing us to efficiently explore all possibilities and avoid recomputation.

k, a, b = map(int, input().split())
sentence = input()
n = len(sentence)


memo = {}
def dp(start, cut):
    if(start, cut) in memo:
        return memo[(start, cut)]


    if cut == 1:
        if a <= len(sentence[start:]) <= b:
            return [sentence[start:]]
        return []
    
    answer = []
    
    for i in range(start+a, min(n, start+b+1)):
        word = sentence[start:i]
        result = dp(i, cut - 1)
        
    
        if len(result) + 1 == cut:
            answer.extend(result)
            answer.append(word)
            break
     

    memo[(start, cut)] = answer
    return answer

answer = dp(0, k)[::-1]

if not answer:
    print("No solution")
else:
    for word in answer:
        print(word)



# CHALLENGE: Make it bottom up !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

If we divide the string as evenly as possible into k parts, then the minimum length of a segment will be $$$⌊n/k⌋$$$ and the maximum length will be $$$⌈n/k⌉$$$. The core insight is that for a solution to exist, this natural distribution must already satisfy the constraints: the minimum segment length ⌊n/k⌋ must be at least $$$a$$$ (otherwise some lines would be too short), and the maximum segment length $$$⌈n/k⌉$$$ must be at most $$$b$$$ (otherwise some lines would be too long).

When the conditions are satisfied, we can simply implement this natural distribution: the first $$$n MOD k$$$ lines will contain $$$⌈n/k⌉$$$ characters each, and the remaining lines will contain $$$⌊n/k⌋$$$ characters each.

k, a, b = map(int, input().split())
sentence = input()
n = len(sentence)


maximum_possible = (n + k - 1) // k # n ceil division by k 
minimum_possible = n // k
remaining_part = n % k

if maximum_possible > b or minimum_possible < a:
    print("No solution")
else:
    maximum_possible *= remaining_part
    
    
    length = 0 # keep track of the length of the current word
    for i in range(maximum_possible):
        length += 1
        print(sentence[i], end="")
        
        if length == maximum_possible // remaining_part:
            # print a line break and reset length since we have printed out one fully valid word
            print()
            length = 0
    
    
    for i in range(maximum_possible, n):
        length += 1
        print(sentence[i], end="")
        
        if length == minimum_possible:
            # print a line break and reset length since we have printed out one fully valid word
            print()
            length = 0
 

Use trie

At first, build a trie containing all suffixes of given string (this structure is also called explicit suffix tree). Let's iterate over all substrings in order of indexes' increasing, i. e. first [1...1],  then [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Note, that moving from a substring to the next one is just adding a single character to the end. So we can easily maintain the number of bad characters, and also the "current" node in the trie. If the number of bad characters doesn't exceed k, then the substring is good. And we need to mark the corresponding node of trie, if we never did this before. The answer will be the number of marked nodes in the trie.

There is also an easier solution, where instead of trie we use Rabin-Karp rolling hash to count substrings that differ by content. Just sort the hashes of all good substrings and find the number of unique hashes (equal hashes will be on adjacent positions after sort). But these hashes are unreliable in general, so it's always better to use precise algorithm.

from collections import defaultdict
 
st = input()
nums = input()
k = int(input())
 
 
Node = lambda : defaultdict(Node)
 
root = Node()
 
 
def add(ind):
    curr = root
    
    for i in range(ind, len(st)):
        if st[i] not in curr:
            curr[st[i]] = Node()
         
        
        curr = curr[st[i]]
 

ans = 0
 
def dfs(node, bad):
    global ans
    stack = [(node, bad)]
 
 
    while stack:
        curr, b = stack.pop()
        
        if b > k:
            continue
 
        ans += 1
        for l, nbr in curr.items():
            ind = ord(l) - ord('a')
            ad = int(nums[ind] == '0')
            stack.append((nbr, b + ad))
 
 
for i in range(len(st)-1, -1, -1):
    add(i)
    
 
for l, node in root.items():
    ind = ord(l) - ord('a')
    ad = int(nums[ind] == '0')
    dfs(node, ad)


print(ans)

Each vertex’s beauty is defined as the greatest common divisor (GCD) of all numbers on the path from the root to that vertex. Additionally, Ilya is allowed to change one vertex’s value to 0, which can potentially increase the beauty of some vertices.

We handle this in two parts:

1. Case 1 – Root value = 0:
   If the root is set to 0, we can easily compute the beauty of each vertex by performing a DFS traversal. The beauty of each node is simply gcd(a[i], beauty[parent]), where beauty[parent] is the GCD value up to the parent node.

2. Case 2 – Root value ≠ 0:
   When the root is not zero, every possible beauty value must be a divisor of the root’s number, because all paths include the root.
   During DFS, for each divisor of the root’s value, we track how many vertices on the current path are divisible by it.
   If a divisor divides at least (depth - 1) vertices along the path, then that divisor is a valid beauty for the current vertex.
   The beauty of a node is the largest such divisor that satisfies this condition.

This ensures we consider both possibilities—keeping or zeroing the root—to maximize each vertex’s beauty.

Complexity:

• Time Complexity: O(n × √a₁) — since we iterate over all divisors of the root for each node during DFS.
• Space Complexity: O(n + √a₁) — for storing the tree and divisor counts.

import sys, math
read = sys.stdin.readline

n = int(read())
values = list(map(int, read().split()))
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, read().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)

beauty = [0] * n

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# ---------- Iterative DFS1 (root set to 0) ----------
original_root = values[0]
values[0] = 0
beauty[0] = 0

stack = [(0, -1, 0)]  # (node, parent, current_gcd)
while stack:
    node, parent, cur_gcd = stack.pop()
    cur_gcd = gcd(cur_gcd, values[node])
    beauty[node] = max(beauty[node], cur_gcd)
    for child in edges[node]:
        if child != parent:
            stack.append((child, node, cur_gcd))

# ---------- Iterative DFS2 (using divisors of root) ----------
values[0] = original_root
divisors = []
i = 1
while i * i <= values[0]:
    if values[0] % i == 0:
        divisors.append(i)
        if i * i != values[0]:
            divisors.append(values[0] // i)
    i += 1
divisors.sort()
count = [0] * len(divisors)

stack = [(0, -1, 0, False)]  # (node, parent, depth, processed_flag)
while stack:
    node, parent, depth, processed = stack.pop()
    if not processed:
        # Entering node
        for i, d in enumerate(divisors):
            count[i] += (values[node] % d == 0)
            if count[i] >= depth:
                beauty[node] = max(beauty[node], d)
        stack.append((node, parent, depth, True))  # add back for backtracking
        for child in reversed(edges[node]):
            if child != parent:
                stack.append((child, node, depth + 1, False))
    else:
        # Leaving node (backtracking)
        for i, d in enumerate(divisors):
            count[i] -= (values[node] % d == 0)

print(*beauty)