Code League — National Competitive Programming Contest — Round 2

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

№	Пользователь	Вклад
1	Qingyu	161
2	adamant	146
3	Um_nik	145
4	Dominater069	142
5	errorgorn	140
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Here is the link to the contest: Link

C. Board Game

Rate the Problem

Hint

Solution

Since the players move independently and do not block each other, the game depends only on the shortest distance from each position to the nearest tower. We can compute these distances using a multi-source BFS. Instead of running a separate BFS from every tower, we start a single BFS with all tower cells in the queue. This gives us the minimum distance from every cell to its nearest tower.

Let $$$D$$$ be the distance from Kibr's starting position to the nearest tower.

If Kibr cannot reach any tower, then $$$D = \infty$$$. In this case, Kibr can never win. Since he chooses Ludis's starting position, he can simply place Ludis on the same cell as himself. Therefore, Ludis is also unable to reach any tower. Neither player can ever reach a tower, so the result is a tie.

Now consider the case where $$$D$$$ is finite. Since Kibr chooses Ludis's starting position, he will always place Ludis on the valid cell that is farthest from any tower in order to delay him as much as possible.

Let $$$D_{max}$$$ be the maximum distance from any valid cell to the nearest tower. If there exists a valid cell that cannot reach any tower, then $$$D_{max} = \infty$$$.

Kibr reaches a tower after exactly $$$D$$$ moves, and Ludis moves first. Therefore, if Ludis starts at a position whose distance to the nearest tower is at most $$$D$$$, he will reach a tower before Kibr or on the same turn, which means Ludis wins. Since Kibr places Ludis on the worst possible valid cell, the outcome depends only on comparing $$$D_{max}$$$ and $$$D$$$.

If $$$D_{max} = D$$$, then every valid starting position allows Ludis to reach a tower before or at the same time as Kibr. Therefore, the answer is $$$\texttt{Ludis}$$$. Otherwise, $$$D_{max} \gt D$$$, and Kibr can place Ludis on a cell that is farther from any tower than Kibr is, or possibly a cell that cannot reach any tower. This allows Kibr to reach a tower first, so the answer is $$$\texttt{Kibr}$$$.

Therefore, the solution is:

Run a multi-source BFS starting from all tower cells.
Compute the distance from every cell to its nearest tower.
Let $$$D$$$ be the distance of Kibr's starting cell.
Let $$$D_{max}$$$ be the largest distance among all valid cells.
If $$$D = \infty$$$, output $$$\texttt{Tie}$$$.
Otherwise, if $$$D_{max} = D$$$, output $$$\texttt{Ludis}$$$.
Otherwise, output $$$\texttt{Kibr}$$$.

Code

from collections import deque

t = int(input())
inf = float("inf")

for _ in range(t):
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]

    queue = deque()
    dist = [[inf] * m for _ in range(n)]
    kr = kc = None

    for i in range(n):
        for j in range(m):
            if grid[i][j] == "t":
                queue.append((i, j))
                dist[i][j] = 0
            elif grid[i][j] == "K":
                kr = i
                kc = j

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    while queue:
        r, c = queue.popleft()
        d = dist[r][c]
        nd = d + 1

        for dr, dc in dirs:
            nr = r + dr
            nc = c + dc

            if nr < 0 or nr >= n or nc < 0 or nc >= m:
                continue

            if grid[nr][nc] != "#" and dist[nr][nc] == inf:
                dist[nr][nc] = nd
                queue.append((nr, nc))

    D = dist[kr][kc]
    if D == inf:
        print("Tie")
        continue

    D_max = 0

    for i in range(n):
        for j in range(m):
            if grid[i][j] != "#":
                D_max = max(D_max, dist[i][j])

    if D_max == D:
        print("Ludis")
    else:
        print("Kibr")

Complexity Analysis

D. Modular Mandelbrot Set

Rate the Problem

Hint

Solution

Code

t = int(input())
for _ in range(t):
    m, c, k = map(int, input().split())

    ans = list(range(m))
    jump = [(i * i + c) % m for i in range(m)]

    while k > 0:
        if k & 1 == 1:
            ans = [jump[x] for x in ans]

        k >>= 1

        if k > 0:
            jump = [jump[x] for x in jump]

    print(*ans)

Complexity Analysis

E. Taxi Fares

Rate the Problem

Solution

Code

n = int(input())
print((n + 250) // 500 * 500)

Complexity Analysis

F. The Dinner Ceremony

Rate the Problem

Hint

Solution

Code

from collections import deque

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    s = input()

    dq = deque()
    west_open = True
    east_open = True

    for char in s:
        if char == "[":
            west_open = not west_open
        elif char == "]":
            east_open = not east_open
        elif char == "<":
            if dq:
                dq.popleft()
        elif char == ">":
            if dq:
                dq.pop()
        else:
            if len(dq) == m:
                continue

            if east_open:
                dq.append(char)
            elif west_open:
                dq.appendleft(char)

    print("".join(dq))

Complexity Analysis

G. Bekele and Coffee Bags

Rate the Problem

Solution

Abeba is given a sequence of $$$n$$$ bags whose weights are all distinct and form a permutation of the integers from $$$1$$$ to $$$n$$$. Her task is to determine the exact weight of every bag in the row.

In one move, she selects $$$k$$$ consecutive bags and learns only their total sum. The goal is to determine the minimum number of such moves required to uniquely reconstruct the entire sequence. If it is not possible to guarantee a unique reconstruction regardless of the number of moves, the answer is $$$-1$$$.

Now we consider each possible value of $$$k$$$.

Case 1: $$$k = 1$$$

Each move reveals the exact weight of a single bag. Therefore, Abeba can directly determine individual positions. She queries $$$n-1$$$ positions, learns their values, and then uses the fact that the total sum of numbers from $$$1$$$ to $$$n$$$ is fixed to determine the last remaining value. Thus, the answer is $$$n - 1$$$.

Case 2: $$$k = 2$$$

Each query gives the sum of two consecutive bags. Abebe can first query all $$$n-1$$$ consecutive pair queries.

She then uses just the disjoint pair queries $$$(w_1+w_2), (w_3+w_4), (w_5+w_6), \dots$$$. From these, she can compute the sum of all values except possibly one element. Since she knows the total sum $$$\frac{n(n+1)}{2}$$$ she can determine any missing value such as $$$w_n$$$ when it is not included in a pair.

After recovering one endpoint value, she can use overlapping pair queries to propagate this information backward and determine all remaining values uniquely.

When $$$n$$$ is odd, there is exactly one element not covered in the disjoint pairing step, which allows the final missing value to be determined using the total sum. This makes the reconstruction fully determined.

However, when $$$n$$$ is even, the disjoint pairing covers all elements completely, so the total sum does not create a unique constraint on any starting value. In this case, unique reconstruction is impossible. Refer to the proof section for more details.

Thus, for $$$k=2$$$ and odd $$$n$$$, the answer is $$$n-1$$$, but if $$$n$$$ is even, the answer is $$$-1$$$.

Case 3: $$$k \ge 3$$$

When $$$k$$$ is at least $$$3$$$, each query covers a relatively large segment of the array, but the overlap structure is too weak to uniquely determine all individual values. So unique reconstruction is impossible. Again, for more details refer to the Proof section.

Therefore, the answer is $$$-1$$$.

Proof

Let $$$P_i$$$ denote the sum of weights of the first $$$i$$$ bags. The sum returned by a query on a segment from index $$$l$$$ to index $$$l+k-1$$$ can be written as the difference between two prefix sums, namely $$$P_{l+k-1} - P_{l-1}$$$.

Each query therefore provides a linear constraint between two prefix sums. We can represent this structure using a graph in which each node corresponds to a prefix sum $$$P_i$$$, and each query introduces an edge between $$$P_{l-1}$$$ and $$$P_{l+k-1}$$$. Because every edge connects indices that differ by exactly $$$k$$$, the graph decomposes into $$$k$$$ independent connected components according to the value of the index modulo $$$k$$$.

Two prefix sums are known without any queries. The first is $$$P_0$$$, which is equal to zero. The second is $$$P_n$$$, which is fixed because the values form a permutation of $$$1$$$ through $$$n$$$, so $$$P_n = \frac{n(n+1)}{2}$$$. These known prefix sums act as anchors. Any connected component that contains an anchor becomes fully determined because all prefix sums in that component can be computed relative to it.

If a connected component does not contain any anchor, then all prefix sums in that component can be shifted by an arbitrary constant. This shift can be compensated in another unanchored component while preserving all query results. As a result, the reconstructed sequence is not unique. Therefore, a necessary and sufficient condition for uniqueness is that every connected component must contain at least one anchor.

Now we analyze the structure of these components for different values of $$$k$$$.

When $$$k = 1$$$, there is only one component, and it contains both $$$P_0$$$ and $$$P_n$$$. Therefore, the system is fully determined.

When $$$k = 2$$$, the prefix sums split into two components based on parity. If $$$n$$$ is odd, the two anchors lie in different components, so both components are fixed. If $$$n$$$ is even, both anchors lie in the same component, leaving the other component free, which causes ambiguity.

When $$$k \ge 3$$$, there are at least three components but only two anchors. Therefore, at least one component does not contain an anchor, and uniqueness is impossible.

Code

t = int(input())

for _ in range(t):
    n, k = map(int, input().split())

    if k == 1 or k == 2 and n % 2 == 1:
        print(n - 1)
    else:
        print(-1)

Complexity Analysis

H. The Air Command

Rate the Problem

Hint 1

Hint 2

Solution

The problem asks us to determine how many buildings a missile launched from building $$$i$$$ can hit.

A missile launched from building $$$a$$$ can hit building $$$b$$$ if and only if:

$$$h_a \gt h_b$$$.
$$$h_a$$$ is strictly greater than every building located strictly between $$$a$$$ and $$$b$$$.

This means that a missile from building $$$i$$$ can hit every consecutive building to its left and right until we encounter a building taller than $$$i$$$.

Let:

$$$L_i$$$ be the nearest building to the left of $$$i$$$ whose height is greater than $$$h_i$$$.
$$$R_i$$$ be the nearest building to the right of $$$i$$$ whose height is greater than $$$h_i$$$.

If no such building exists, we define, $$$L_i = 0$$$ and $$$R_i = n + 1$$$.

Every building strictly between $$$L_i$$$ and $$$R_i$$$ is shorter than building $$$i$$$. Therefore, building $$$i$$$ can hit every building in that range except itself. The total number of buildings it can hit is $$$(R_i - L_i - 1) - 1 = R_i - L_i - 2$$$.

So the problem reduces to finding the nearest taller building on both sides of every position. To do this within the query limit, we can use a monotonic stack. We process the buildings from left to right while maintaining a stack of indices whose heights are strictly decreasing.

Suppose we are currently processing building $$$i$$$, and let $$$j$$$ be the building at the top of the stack. We then perform the query \texttt{? i j}. Because of the monotonic stack property, every building strictly between $$$j$$$ and $$$i$$$ is shorter than $$$j$$$.

Therefore, the query result depends only on the comparison between $$$h_i$$$ and $$$h_j$$$. If the query returns $$$1$$$, then $ h_i > h_j$. This means building $$$i$$$ is the nearest taller building to the right of $$$j$$$. We record $$$R_j = i$$$ and pop $$$j$$$ from the stack. We continue this process until the stack becomes empty or we encounter a building taller than $$$i$$$.

If the query returns $$$0$$$, then $$$h_i \lt h_j$$$. In this case, $$$j$$$ is the nearest taller building to the left of $$$i$$$. We record $$$L_i = j$$$ and stop popping.

Finally, we push $$$i$$$ onto the stack.

After processing all buildings, every building's nearest taller neighbor on both sides has been determined. We can then compute the answer for each building using $$$R_i - L_i - 2$$$.

Each building is pushed onto the stack exactly once and popped at most once. This guarantees that the number of queries remains within the allowed limit.

Code

t = int(input())

for _ in range(t):
    n = int(input())

    L = [0] * (n + 1)
    R = [n + 1] * (n + 1)
    stack = []

    for i in range(1, n + 1):
        while stack:
            j = stack[-1]
            print(f"? {i} {j}", flush=True)

            ans = int(input())
            if ans == -1:
                exit()

            if ans == 1:
                stack.pop()
                R[j] = i
            else:
                break

        if stack:
            L[i] = stack[-1]
        else:
            L[i] = 0

        stack.append(i)

    arr = [R[i] - L[i] - 2 for i in range(1, n + 1)]
    print("!", *arr, flush=True)

Complexity Analysis

I. Vending Machine

Rate the Problem

Solution

Code

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())

    prices = [0] * (n + 1)
    stocks = [0] * (n + 1)

    for i in range(1, n + 1):
        p, s = map(int, input().split())
        prices[i] = p
        stocks[i] = s

    total_revenue = 0

    for _ in range(m):
        q = int(input())

        if stocks[q] > 0:
            total_revenue += prices[q]
            stocks[q] -= 1

    print(total_revenue)

Complexity Analysis

J. Escape from the Dungeon

Rate the Problem

Hint 1

Hint 2

Solution

The problem asks us to find the smallest non-negative integer whose digits sum to $$$s$$$ and whose digits multiply to $$$p$$$.

The first step is to factorize $$$p$$$. A digit can only contribute prime factors from the set $$${2, 3, 5, 7}$$$. So if $$$p$$$ has any prime factor greater than or equal to $$$11$$$, then the answer is impossible, and we output $$$-1$$$.

Next, we handle the digits $$$5$$$ and $$$7$$$. These two digits are special because they are the only digits that can provide the prime factors $$$5$$$ and $$$7$$$. So the number of $$$5$$$s and the number of $$$7$$$s are fully determined by the powers of $$$5$$$ and $$$7$$$ in $$$p$$$.

After removing all $$$5$$$s and $$$7$$$s, the remaining product must be of the form $$$2^a \cdot 3^b$$$. Now we only need to build this remaining product using digits from the set $$${1, 2, 3, 4, 6, 8, 9}$$$. The digit $$$1$$$ is useful because it does not change the product, so it can be used to fill any leftover sum.

Let the remaining sum after removing the fixed $$$5$$$s and $$$7$$$s be $$$S_{\text{avail}}$$$. We now need to find a multiset of digits that multiplies to $$$2^a \cdot 3^b$$$ and uses some sum $$$S \le S_{\text{avail}}$$$. If $$$S \lt S_{\text{avail}}$$$, we can pad the number with exactly $$$S_{\text{avail}} - S$$$ ones. This does not change the product, but it increases the digit sum to the required value.

To answer many test cases quickly, we precompute a DP table. Let $$$dp(a, b, S)$$$ store the best multiset of digits that multiplies exactly to $$$2^a \cdot 3^b$$$ and has digit sum $$$S$$$.

We need to find the smallest non-negative number that satisfies our constraint. Therefore, "best" means:

smallest number of digits,
and if there is a tie, lexicographically smallest.

We can build this table with an unbounded knapsack DP, trying digits from $$${2,3,4,6,8,9}$$$ and adding their contributions to the powers of $$$2$$$ and $$$3$$$ and to the digit sum.

This works because $$$p \le 10^{18}$$$, so the exponent of $$$2$$$ is at most $$$59$$$ and the exponent of $$$3$$$ is at most $$$38$$$. Also, the relevant sum range is small enough to precompute in advance.

For each test case, we do the following:

Remove all factors of $$$5$$$ and $$$7$$$ from $$$p$$$ and count how many $$$5$$$ and $$$7$$$ digits are forced.
If any prime factor greater than or equal to $$$11$$$ remains, output $$$-1$$$.
For the remaining $$$2^a \cdot 3^b$$$, try every valid sum $$$S$$$.
For each candidate, take the precomputed best digits for $$$dp(a, b, S)$$$, add the needed number of $$$1$$$ digits, and then add the fixed $$$5$$$ and $$$7$$$ digits.
Sort the digits in nondecreasing order so the number is as small as possible.
Among all valid candidates, choose the smallest one by length, and if lengths are equal, by lexicographic order.

If no candidate works, the answer is $$$-1$$$.

Code

from collections import Counter

t = int(input())

dp = [[[None] * 121 for _ in range(39)] for _ in range(60)]
dp[0][0][0] = ()

items = [
    (2, 1, 0),  # Digit 2 contributes 2^1 * 3^0
    (3, 0, 1),  # Digit 3 contributes 2^0 * 3^1
    (4, 2, 0),  # Digit 4 contributes 2^2 * 3^0
    (6, 1, 1),  # Digit 6 contributes 2^1 * 3^1
    (8, 3, 0),  # Digit 8 contributes 2^3 * 3^0
    (9, 0, 2),  # Digit 9 contributes 2^0 * 3^2
]

for d, da, db in items:
    for a in range(60 - da):
        for b in range(39 - db):
            for S in range(121 - d):
                curr = dp[a][b][S]
                if curr is not None:
                    cand = curr + (d,)
                    nxt = dp[a + da][b + db][S + d]

                    if nxt is None:
                        dp[a + da][b + db][S + d] = cand
                    else:
                        if len(cand) < len(nxt):
                            dp[a + da][b + db][S + d] = cand
                        elif len(cand) == len(nxt) and cand < nxt:
                            dp[a + da][b + db][S + d] = cand

for _ in range(t):
    s, p = map(int, input().split())

    facts = Counter()
    temp_p = p

    for k in [2, 3, 5, 7]:
        while temp_p % k == 0:
            facts[k] += 1
            temp_p //= k

    if temp_p > 1:
        print(-1)
        continue

    S_avail = s - (5 * facts[5] + 7 * facts[7])
    if S_avail < 0:
        print(-1)
        continue

    fives = [5] * facts[5]
    sevens = [7] * facts[7]
    a = facts[2]
    b = facts[3]

    best_ans = None
    for S in range(S_avail + 1):
        M = dp[a][b][S]
        if M is not None:
            k = S_avail - S

            other = list(M) + fives + sevens
            other.sort()
            cand_str = "1" * k + "".join(map(str, other))

            if best_ans is None:
                best_ans = cand_str
            else:
                if len(cand_str) < len(best_ans):
                    best_ans = cand_str
                elif len(cand_str) == len(best_ans) and cand_str < best_ans:
                    best_ans = cand_str

    if best_ans is None:
        print(-1)
    else:
        print(best_ans)

Complexity Analysis

K. The Lazy Chefs

Rate the Problem

Solution

Code

from collections import deque

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())

    d = [0] + list(map(int, input().split()))
    out_degree = [0] * (n + 1)
    rev_adj = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v = map(int, input().split())
        out_degree[u] += 1
        rev_adj[v].append(u)

    L = [0] * (n + 1)
    max_next = [0] * (n + 1)

    queue = deque()
    for i in range(1, n + 1):
        if out_degree[i] == 0:
            L[i] = d[i]
            queue.append(i)

    while queue:
        v = queue.popleft()
        for u in rev_adj[v]:
            if L[v] > max_next[u]:
                max_next[u] = L[v]

            out_degree[u] -= 1
            if out_degree[u] == 0:
                queue.append(u)
                L[u] = d[u] + max_next[u]

    T_max = max(L)

    ans = [T_max - L[i] for i in range(1, n + 1)]
    print(*(ans))

Complexity Analysis

L. The Investment

Rate the Problem

Hint

Solution

Code

t = int(input())
for _ in range(t):
    c = int(input())

    L = -400.0
    R = 400.0

    for _ in range(60):
        mid = (L + R) / 2.0
        val = mid**7 + 3.0 * (mid**3) + mid
        if val < c:
            L = mid
        else:
            R = mid

    print(f"{(L + R) / 2.0:.12f}")

Complexity Analysis

M. Parity Pulse

Rate the Problem

Hint 1

Hint 2

Solution

Code

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    already_ok = True
    for i in range(n - 1):
        if (a[i] % 2) == (a[i + 1] % 2):
            already_ok = False
            break

    if already_ok:
        print(0)
        continue

    if k % 2 == 0:
        print(-1)
        continue

    b = [x % 2 for x in a]

    # Target 1: [0, 1, 0, 1, ...]
    diff1 = [b[i] ^ (i % 2) for i in range(n)]

    # Target 2: [1, 0, 1, 0, ...]
    diff2 = [b[i] ^ ((i + 1) % 2) for i in range(n)]

    ans = float("inf")

    for diff in [diff1, diff2]:
        if sum(diff) % 2 == 0:
            moves = 0
            carry = 0

            for val in diff[:-1]:
                if val ^ carry == 1:
                    moves += 1
                    carry = 1
                else:
                    carry = 0

            ans = min(ans, moves)

    if ans == float("inf"):
        print(-1)
    else:
        print(ans)

Complexity Analysis

N. The Boss Fight

Rate the Problem

Solution

The problem asks us to choose a subset of characters to maximize total damage, where each character can only be used if we can make their health and stamina equal using the allowed operations. We analyze a single character with initial values $$$h$$$ and $$$s$$$. Suppose we apply the first operation $$$a$$$ times and the second operation $$$b$$$ times.

From this, we can derive the following two equations: $$$H = h + a - 2b$$$ and $$$S = s - 2a + b$$$. For the character to be usable, we need $$$H = S$$$. Setting them equal gives $$$h + a - 2b = s - 2a + b$$$. We can rearrange this to $$$s - h = 3(a - b)$$$. This shows that the difference $$$s - h$$$ must be divisible by $$$3$$$. If it is not, the character can never be made usable, so it is discarded.

Now assume the character is valid. From the equation $$$a - b = \frac{s - h}{3}$$$. We define $$$c_i = \frac{|h_i - s_i|}{3}$$$. This represents the minimum required operations to balance the two values. For a balanced state, the final equal value becomes: $$$x_i = \max(h_i, s_i) - 2c_i$$$. And therefore, the damage contributed by this character is $$$4x_i$$$.

Now we interpret each character as an item in a $$$01$$$-knapsack problem where:

the weight of $$$i^{\text{th}}$$$ item is $$$c_i$$$.
the value of $$$i^{\text{th}}$$$ item is $$$4x_i$$$.
the total capacity allowed is $$$k$$$.

We want to select a subset of characters such that total weight does not exceed $$$k$$$ and total value is maximized. Since, $$$c_i$$$ and $$$k$$$ can go up to $$$10^9$$$, the traditional knapsack solution is not efficient here. So, we need a better approach. Since $$$n$$$ is atmost $$$30$$$, we can use a concept called meet-in-the-middle.

We split the characters into two halves of size at most $$$\frac{n}{2}$$$ each. For each half, we enumerate all subsets and compute their total weights (sum of $$$c_i$$$) and values (sum of $$$4x_i$$$). This gives us two lists of states.

Next, we filter each list to keep only Pareto-optimal states. That is, after sorting by weight, we only keep states where value strictly increases as weight increases. This removes dominated states. Finally, we combine both halves. For each state in the first half, we use a two-pointer or binary search approach on the second half to find the best compatible state such that total weight is at most $$$k$$$.

The maximum combined value is the answer.

Code

t = int(input())

for _ in range(t):
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    s = list(map(int, input().split()))

    items = []
    for i in range(n):
        diff = abs(h[i] - s[i])

        if diff % 3 == 0:
            cost = diff // 3
            x = max(h[i], s[i]) - 2 * cost
            val = 4 * x

            if cost <= k:
                items.append((cost, val))

    if not items:
        print(0)
        continue

    n_items = len(items)
    n1 = n_items // 2

    L_states = [(0, 0)]
    for i in range(n1):
        w, v = items[i]
        next_states = []

        for sw, sv in L_states:
            next_states.append((sw, sv))

            if sw + w <= k:
                next_states.append((sw + w, sv + v))

        L_states = next_states

    R_states = [(0, 0)]
    for i in range(n1, n_items):
        w, v = items[i]
        next_states = []

        for sw, sv in R_states:
            next_states.append((sw, sv))

            if sw + w <= k:
                next_states.append((sw + w, sv + v))

        R_states = next_states

    # Filter a list of states to keep only Pareto-optimal ones
    def get_pareto(states):
        states.sort(key=lambda x: (x[0], -x[1]))
        pareto = []
        max_v = -1

        for w, v in states:
            if v > max_v:
                pareto.append((w, v))
                max_v = v

        return pareto

    L_pareto = get_pareto(L_states)
    R_pareto = get_pareto(R_states)

    ans = 0
    i = 0
    j = len(R_pareto) - 1

    while i < len(L_pareto) and j >= 0:
        lw, lv = L_pareto[i]
        rw, rv = R_pareto[j]

        if lw + rw <= k:
            if lv + rv > ans:
                ans = lv + rv

            i += 1
        else:
            j -= 1

    print(ans)

Complexity Analysis

O. Factory Machine

Rate the Problem

Solution

The problem asks us to select a subsequence of raw materials to maximize the total processed value under thermal constraints.

We solve this using a backward dynamic programming approach over the array, processing from index $$$n-1$$$ down to $$$0$$$. We define a DP table $$$dp$$$ with states of size $$$n \times 2$$$.

We interpret the two states as follows:

$$$dp(i, 0)$$$ is the maximum value we can obtain starting from index $$$i$$$ when the super-coolant is already used or unavailable.
$$$dp(i, 1)$$$ is the maximum value we can obtain starting from index $$$i$$$ when the super-coolant is still available.

At each position $$$i$$$, we decide whether to skip the current material or process it.

State 0: coolant unavailable ($$$dp(i, 0)$$$)

If we skip $$$a[i]$$$, we move to $$$dp(i+1, 0)$$$. If we process $$$a[i]$$$, two cases arise:

If $$$a[i] \le k$$$, no overheating happens, so we transition normally to $$$a[i] + dp[i+1][0]$$$.
If $$$a[i] \gt k$$$, the machine overheats, forcing us to skip the next item, so we go to $$$a[i] + dp[i+2][0]$$$.

We take the maximum of these options. So, $$$dp(i, 0) = \max(dp(i+1, 0), a[i] + dp[i+1][0], a[i] + dp[i+2][0])$$$.

State 1: coolant available ($$$dp(i, 1)$$$)

If we skip $$$a[i]$$$, we keep the coolant available. Which means we move to $$$dp(i+1, 1)$$$. If we process $$$a[i]$$$, we consider all thermal cases:

If $$$a[i] \le k$$$, no overheating occurs, and we keep the coolant. And we transition to $$$a[i] + dp[i+1][1]$$$.
If $$$k \lt a[i] \le 2k$$$, we have two options:
- Use the coolant to prevent overheating: $$$a[i] + dp[i+1][0]$$$.
- Do not use the coolant, causing overheating: $$$a[i] + dp[i+2][1]$$$.
If $$$a[i] \gt 2k$$$, even using the coolant does not prevent overheating, so the best choice is: $$$a[i] + dp[i+2][1]$$$.

We take the maximum over all valid transitions.

We compute these states iteratively from $$$i = n-1$$$ down to $$$0$$$ using the extra padding to handle boundary transitions. Finally, the answer is $$$dp(0, 1)$$$, which represents starting from the first element with the coolant available.

Code

t = int(input())

for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0, 0] for _ in range(n + 2)]

    for i in range(n - 1, -1, -1):

        dp[i][0] = dp[i + 1][0]
        if a[i] <= k:
            dp[i][0] = max(dp[i][0], a[i] + dp[i + 1][0])
        else:
            dp[i][0] = max(dp[i][0], a[i] + dp[i + 2][0])

        dp[i][1] = dp[i + 1][1]
        if a[i] <= k:
            dp[i][1] = max(dp[i][1], a[i] + dp[i + 1][1])
        elif a[i] <= 2 * k:
            dp[i][1] = max(dp[i][1], a[i] + dp[i + 1][0], a[i] + dp[i + 2][1])
        else:
            dp[i][1] = max(dp[i][1], a[i] + dp[i + 2][1])

    print(dp[0][1])

Complexity Analysis

P. The Broken PC

Rate the Problem

Solution

Code

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    total_files = 0
    limit = min(n, m - 1)

    for i in range(limit):
        folder_idx = i + 1

        max_openable = m - folder_idx
        if max_openable > 0:
            total_files += min(a[i], max_openable)

    print(total_files)

Complexity Analysis