Here is the link to the contest: Link
A. Free Coupon
Which items should be taken using coupons?
Since a coupon can be used on any item regardless of its price, it is always best to use coupons on the most expensive items. This allows us to spend our coins only on cheaper items.
The problem asks us to find the maximum number of items Abenezer can obtain given $$$k$$$ coins, with the offer that every $$$b$$$ items bought with coins yield $$$1$$$ free coupon. Each coupon allows him to take any available item for free. Note that items obtained using coupons do not count toward earning additional coupons.
Let $$$x$$$ be the number of items bought using coins. Then Abenezer earns exactly $$$\left\lfloor \frac{x}{b} \right\rfloor$$$ coupons. Since each coupon can be exchanged for one additional item, the total number of items he obtains is $$$x + \left\lfloor \frac{x}{b} \right\rfloor$$$.
Since there are only $$$n$$$ items in total, the number of items he can obtain is bounded by $$$n$$$. Therefore, if he buys $$$x$$$ items with coins, the total number of items he can take is $$$\min\left(n, x + \left\lfloor \frac{x}{b} \right\rfloor\right)$$$.
The only remaining task is to maximize $$$x$$$.
To maximize $$$x$$$, he should buy the cheapest items first. Replacing a cheaper item with a more expensive one can only increase the total cost, so it can never allow him to buy more items. The coupons can then be used to claim the most expensive items for free.
Therefore, our strategy is simple:
- Sort the items by price in ascending order.
- Greedily select items one by one starting from the cheapest, keeping a running sum of their costs.
- Stop when adding the next item would exceed the budget $$$k$$$.
- Let $$$x$$$ be the maximum number of items he could afford. The answer is $$$\min\left(n, x + \left\lfloor \frac{x}{b} \right\rfloor\right)$$$.
t = int(input())
for _ in range(t):
n, k, b = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
x = 0
current_sum = 0
for price in c:
if current_sum + price > k:
break
current_sum += price
x += 1
total_items = x + (x // b)
print(min(n, total_items))
Time Complexity: Sorting the item prices takes $$$O(n \log n)$$$ time. After sorting, we make a single pass through the array to determine how many items can be bought within the budget, which takes $$$O(n)$$$ time. Therefore, the overall time complexity per testcase is $$$O(n \log n)$$$.
Space Complexity: Aside from the array storing the item prices, the solution only uses a few additional variables for the running sum and item count. Therefore, the extra space complexity is $$$O(1)$$$.
B. Crafting in Minecraft
For shapeless recipes, the positions of the ingredients do not matter. So what should we focus on instead?
We only care about how many times each ingredient appears. Once the ingredient counts are fixed, the problem becomes counting arrangements of a multiset.
The problem has two different cases depending on the value of $$$k$$$.
Shaped Recipes ($$$k = 0$$$)
For a shaped recipe, the relative positions of the ingredients must exactly match the given $$$p \times q$$$ pattern.
Since the problem guarantees that the recipe's bounding box is tight, there are no completely empty border rows or columns. Therefore, we only need to count how many positions this pattern can occupy inside the $$$n \times n$$$ crafting grid.
The top-left corner of the recipe can be placed in any of $$$(n - p + 1)$$$ rows and any of $$$(n - q + 1)$$$ columns. Thus, the number of valid placements is $$$(n - p + 1)(n - q + 1)$$$.
We are also allowed to mirror the recipe horizontally. If the pattern is horizontally symmetric, mirroring produces exactly the same pattern, so the number of placements remains unchanged. Otherwise, the mirrored pattern is different from the original one and contributes an additional set of valid placements. In this case, we multiply the answer by $$$2$$$.
Shapeless Recipes ($$$k = 1$$$)
For a shapeless recipe, the positions of the ingredients do not matter. Only the ingredients themselves matter. Ignore all cells containing $$$0$$$. Let $$$S$$$ be the number of non-zero cells in the recipe. The crafting grid contains $ N = n^2$ cells.
We first choose which $$$S$$$ cells will contain ingredients. The remaining $$$N-S$$$ cells stay empty. If all ingredients were distinct, the number of ways would be $$$\frac{N!}{(N-S)!}$$$.
However, identical ingredients are indistinguishable. Swapping two copies of the same ingredient does not create a new arrangement.
Let $$$C_c$$$ be the number of times ingredient $$$c$$$ appears in the recipe. To remove overcounting, we divide by $$$C_c!$$$ for every ingredient value. Therefore, the answer is $$$\frac{N!}{(N-S)! \prod C_c!}$$$.
Since $$$N$$$ can be as large as $$$10^6$$$, we precompute factorials and inverse factorials up to $$$10^6$$$ modulo $$$998244353$$$, using Fermat's Little Theorem.
from collections import Counter
MOD = 998244353
MAX = 10**6
fact = [1] * (MAX + 1)
for i in range(1, MAX + 1):
fact[i] = (fact[i - 1] * i) % MOD
invFact = [1] * (MAX + 1)
invFact[MAX] = pow(fact[MAX], MOD - 2, MOD)
for i in range(MAX - 1, -1, -1):
invFact[i] = (invFact[i + 1] * (i + 1)) % MOD
t = int(input())
for _ in range(t):
n, p, q, k = map(int, input().split())
if k == 0:
symmetric = True
for _ in range(p):
row = list(map(int, input().split()))
if symmetric:
for j in range(q // 2):
if row[j] != row[q - 1 - j]:
symmetric = False
break
ways = ((n - p + 1) * (n - q + 1)) % MOD
if not symmetric:
ways = (ways * 2) % MOD
print(ways)
else:
counts = Counter()
S = 0
for _ in range(p):
row = list(map(int, input().split()))
for j in range(q):
if row[j] != 0:
counts[row[j]] += 1
S += 1
N = n * n
ans = (fact[N] * invFact[N - S]) % MOD
for c in counts.values():
ans = (ans * invFact[c]) % MOD
print(ans)
Time Complexity: For shaped recipes, we only scan the $$$p \times q$$$ pattern to check whether it is horizontally symmetric, giving a complexity of $$$O(pq)$$$. For shapeless recipes, we scan the recipe once to count ingredient frequencies, which also takes $$$O(pq)$$$ time. All factorial and inverse factorial values are precomputed beforehand. Therefore, the time complexity per testcase is $$$O(pq)$$$.
Space Complexity: Aside from the input grid and a frequency map used to count ingredient occurrences, the solution only uses a few additional variables. Therefore, the extra space complexity is $$$O(u)$$$, where $$$u$$$ is the number of distinct non-zero ingredients in the recipe. Since $$$u \le pq$$$, the final extra space complexity will be $$$O(pq)$$$.
C. Board Game
When is the only time Ludis will win regardless of the position of his piece?
Only when we can reach a tower from any valid starting position, and Kibr's starting position is the farthest from the nearest tower.
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}$$$.
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")
Time Complexity: The multi-source BFS visits each cell at most once and processes each edge a constant number of times. Therefore, the BFS runs in $$$O(nm)$$$ time. Computing $$$D$$$ and $$$D_{max}$$$ requires a single scan of the grid, which also takes $$$O(nm)$$$ time. Thus, the overall time complexity per testcase is $$$O(nm)$$$.
Space Complexity: The BFS queue and distance array store information for each cell of the grid. Therefore, the extra space complexity is $$$O(nm)$$$.
D. Modular Mandelbrot Set
Can you model this as a graph problem?
The problem asks us to compute the final value after applying the transformation $$$x \leftarrow (x^2 + c) \bmod m$$$ exactly $$$k$$$ times for every starting value $$$i \in {0, 1, \ldots, m-1}$$$. Since $$$k$$$ can be as large as $$$10^9$$$, simulating the process step by step would be too slow.
Notice that this transformation forms a directed graph with $$$m$$$ nodes. Each value $$$x$$$ corresponds to a node, and there is a directed edge from $$$x$$$ to $$$(x^2 + c) \bmod m$$$.
Since every node has exactly one outgoing edge, we can think of the transformation as repeatedly moving along the graph. Our goal is to find where each node ends up after exactly $$$k$$$ moves. This can be done efficiently using binary lifting (also known as successive doubling).
Let's say we have an array $$$a$$$, where $$$a_i$$$ is the current position of the starting value $$$i$$$. Initially, $$$a_i = i$$$, for every $$$i \in {0, 1, \ldots, m-1}$$$. And let $$$g(i)$$$ be the destination after the current jump length from node $$$i$$$. Initially, the jump length is $$$1$$$, so $$$g(i) = (i^2 + c) \bmod m$$$, again for every $$$i \in {0, 1, \ldots, m-1}$$$.
We then process $$$k$$$ as a binary number. Whenever the current bit of $$$k$$$ is set, we apply the current jump to every value in $$$a$$$, that is, set $$$a_i = g(a_i)$$$, for every $$$i \in {0, 1, \ldots, m-1}$$$. After that, we double the jump length by composing the jump with itself. That is we set $$$g(i) = g(g(i))$$$, again for every $$$i \in {0, 1, \ldots, m-1}$$$. If the current jump length was $$$2^j$$$ for some integer $$$j$$$, then, the previous process changes the jump length from $$$2^j$$$ to $$$2^{j+1}$$$.
By processing all bits of $$$k$$$, we efficiently compute the position reached after exactly $$$k$$$ applications of the transformation for every starting value.
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)
Time Complexity: Let $$$L = \lfloor \log_2 k \rfloor + 1$$$ be the number of bits in $$$k$$$. For each bit, we process all $$$m$$$ nodes once while updating the $$$ans$$$ and $$$jump$$$ arrays. Therefore, the total time complexity is $$$O(m \log k)$$$.
Space Complexity: The solution stores the arrays $$$ans$$$ and $$$jump$$$, each of size $$$m$$$. Therefore, the extra space complexity is $$$O(m)$$$.
E. Taxi Fares
The problem asks us to round the given fare according to the same rule used for taxi fares. Since $$$5$$$ Birr equals $$$500$$$ cents, the final answer must always be a multiple of $$$500$$$.
Let $$$q = \lfloor \frac{n}{500} \rfloor$$$.
The two nearest multiples of $$$500$$$ are $$$500q$$$ and $$$500(q+1)$$$. We need to determine which of these two values is closer to $$$n$$$.
Let $$$r = n \bmod 500$$$. The value $$$r$$$ tells us how far $$$n$$$ is from the lower multiple of $$$500$$$. If $$$r \lt 250$$$, then $$$n$$$ is closer to $$$500q$$$, so we round down. If $$$r \gt 250$$$, then $$$n$$$ is closer to $$$500(q+1)$$$, so we round up. If $$$r = 250$$$, then $$$n$$$ is exactly halfway between the two multiples of $$$500$$$. The statement specifies that in this case we round up, so the answer is still $$$500(q+1)$$$.
Therefore:
- If $$$r \lt 250$$$, output $$$500q$$$.
- Otherwise, output $$$500(q+1)$$$.
We can combine all of this into a single formula:
Adding $$$250$$$ shifts the halfway point so that integer division automatically performs the required rounding, including the tie case.
Note that it is also possible to use builtin round functions to solve this problem.
n = int(input())
print((n + 250) // 500 * 500)
Time Complexity: The solution performs only a constant number of arithmetic operations. Therefore, the time complexity is $$$O(1)$$$.
Space Complexity: The solution only uses a few integer variables. Therefore, the extra space complexity is $$$O(1)$$$.
F. The Dinner Ceremony
What data structure allows us to efficiently keep track of what is happening inside the hall?
A double-ended queue (deque).
The problem involves adding and removing people from both ends of the hall. This matches the behavior of a double-ended queue (deque), which supports efficient insertion and removal from both the front and the back.
We can model the East Door as the right side of the deque and the West Door as the left side of the deque. Whenever a person enters through the East Door, we append them to the right side of the deque. Whenever a person enters through the West Door, we append them to the left side of the deque.
Similarly, removing a person from the East Door corresponds to removing an element from the right side of the deque, while removing a person from the West Door corresponds to removing an element from the left side.
We also maintain two boolean variables to keep track of whether the West Door and East Door are currently open. Whenever we encounter the character \texttt{[} or \texttt{]}, we toggle the corresponding door state.
Before inserting a new person into the hall, we check whether the current number of people is less than the capacity $$$m$$$. This prevents the hall from exceeding its maximum capacity.
By processing the events in order and updating the deque accordingly, we can directly simulate the behavior described in the statement and obtain the final arrangement of people inside the hall.
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))
Time Complexity: Each event is processed exactly once. All deque operations, including insertions and removals from either end, take $$$O(1)$$$ time. Therefore, if there are $$$n$$$ events, the total time complexity is $$$O(n)$$$.
Space Complexity: The deque stores at most $$$m$$$ people at any time. Aside from the deque and a few boolean variables, no additional data structures are used. Therefore, the extra space complexity is $$$O(m)$$$.
G. Bekele and Coffee Bags
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$$$.
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.
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)
Time Complexity: The answer is determined using only the values of $$$n$$$ and $$$k$$$. All required checks are constant-time operations. Therefore, the time complexity per testcase is $$$O(1)$$$.
Space Complexity: The solution only stores a few integer variables and does not require any additional data structures. Therefore, the extra space complexity is $$$O(1)$$$.
H. The Air Command
Let's assume you already know the heights of all buildings. How would you solve it?
For each building, find the nearest taller building on the left and the nearest taller building on the right. If these positions are $$$L_i$$$ and $$$R_i$$$, then the number of buildings that can be hit is $$$R_i - L_i - 2$$$.
What data structure do you think helps you solve this problem?
A monotonic stack.
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.
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)
Query Complexity: Each building is pushed onto the stack exactly once and popped at most once. Every query that returns $$$1$$$ immediately pops one building from the stack, so there can be at most $$$n$$$ such queries in total. Additionally, each building can cause at most one query that returns $$$0$$$ before it is pushed onto the stack, giving at most another $$$n$$$ queries. Therefore, the total number of queries is at most $$$2n$$$.
Time Complexity: Each building is pushed onto the stack exactly once and popped at most once. All other operations take constant time. Therefore, the total time complexity is $$$O(n)$$$.
Space Complexity: The stack and the arrays storing $$$L_i$$$ and $$$R_i$$$ each contain at most $$$n$$$ elements. Therefore, the extra space complexity is $$$O(n)$$$.
I. Vending Machine
The problem can be solved by directly simulating the events as they occur.
For each customer, we look at the soft drink they want to buy. If the stock of that drink is strictly greater than $$$0$$$, then the purchase is successful. We add the drink's price to the total revenue and decrease its stock by $$$1$$$. Otherwise, if the stock is already $$$0$$$, the customer cannot buy the drink and simply leaves. In this case, the revenue remains unchanged. By processing all customers in the given order and updating the stock accordingly, we obtain the total amount of money earned.
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)
Time Complexity: We first read and store the price and stock of all $$$n$$$ soft drinks, which takes $$$O(n)$$$ time. We then process each of the $$$m$$$ customers exactly once, performing only constant-time operations for each customer. Therefore, the total time complexity is $$$O(n + m)$$$.
Space Complexity: The solution stores the prices and stocks of the $$$n$$$ soft drinks in two arrays. Aside from a few additional variables, no other data structures are used. Therefore, the extra space complexity is $$$O(n)$$$.
J. Escape from the Dungeon
Can you use prime factorization to narrow down which digits are possible?
$$$2^{60} \gt 10^{18}$$$, and $$$3^{38} \gt 10^{18}$$$.
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$$$.
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)
Time Complexity: The preprocessing uses a 3D DP over states $$$(a, b, S)$$$, where $$$a \le 59$$$, $$$b \le 38$$$, and $$$S$$$ is bounded by a small constant range. Each state tries a constant number of digits. Therefore, preprocessing takes $$$O(60 \cdot 39 \cdot 121 \cdot 6)$$$ time. For each test case, we factorize $$$p$$$ by dividing out $$$2$$$, $$$3$$$, $$$5$$$, and $$$7$$$, and then scan the bounded set of possible sums $$$S$$$. Therefore, the per-test work is bounded by a small constant for the given constraints. The time complexity is thus $$$O(1)$$$ per testcase.
Space Complexity: The DP table stores one value for every state $$$(a, b, S)$$$. Therefore, the extra space complexity is $$$O(60 \cdot 39 \cdot 121)$$$.
K. The Lazy Chefs
The problem asks us to find the latest possible start time for each step in a process represented as a Directed Acyclic Graph (DAG), such that the entire process finishes in minimum time.
Let $$$L(i)$$$ be the maximum total duration of any path that starts at node $$$i$$$. This includes the duration of node $$$i$$$ itself. Once $$$L(i)$$$ is known, the latest start time for node $$$i$$$ is determined by how much “slack” it has compared to the longest possible process starting anywhere. The key idea is that nodes on longer paths must start earlier, while nodes on shorter paths can be delayed.
To compute $$$L(i)$$$ efficiently, we use a topological sort approach starting from the leaves of the DAG. We compute the out-degree of each node. Any node with out-degree $$$0$$$ is a leaf, meaning it has no outgoing dependencies. For such a node, $$$L(i) = d_i$$$ since the longest path starting there is just the node itself.
We initialize a queue with all leaf nodes. We also build a reversed adjacency list so that for every edge $$$u \rightarrow v$$$, we can traverse from $$$v$$$ back to $$$u$$$.
We maintain an array \texttt{max_next[u]}, which stores the maximum value of $$$L(v)$$$ over all successors $$$v$$$ of $$$u$$$.
We process nodes in the queue:
- For a node $$$v$$$, we look at all predecessors $$$u$$$. For each such $$$u$$$, we update: $$$\text{max_next[u]} = \max(\text{max_next[u]}, L(v))$$$.
- Then we decrement the out-degree of $$$u$$$. Once the out-degree of $$$u$$$ becomes $$$0$$$, it means all its outgoing neighbors have been processed, so we can compute: $$$L(u) = d_u + \text{max_next}[u]$$$ and push $$$u$$$ into the queue.
After computing all $$$L(i)$$$ values, we use them to determine the latest start times, nodes on longer paths must start earlier, and nodes on shorter paths can be delayed relative to them, which is exactly captured through the computed $$$L(i)$$$ values.
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))
Time Complexity: Each node is pushed into the queue exactly once, and each edge is processed exactly once when traversing from a node to its predecessors. Therefore, the total time complexity is $$$O(n + m)$$$.
Space Complexity: We store the graph using adjacency lists and a reversed adjacency list, along with arrays for out-degree and $$$L(i)$$$ values. Therefore, the extra space complexity is $$$O(n + m)$$$.
L. The Investment
Can you try representing this problem mathematically as an equation?
The relationship between the yearly multiplier $$$x$$$ and the final amount $$$c$$$ can be written as the equation:
So we are asked to find the value of $$$x$$$ that satisfies this equation. We define $$$f(x) = x^7 + 3x^3 + x$$$. To understand the behavior of this function, we compute its derivative: $$$f'(x) = 7x^6 + 9x^2 + 1$$$.
Since $$$7x^6 \ge 0$$$, $$$9x^2 \ge 0$$$, and there is always a $$$+1$$$ term, we have $$$f'(x) \gt 0 \quad \text{for all real } x$$$. This means $$$f(x)$$$ is strictly increasing over all real numbers. Therefore, for any value of $$$c$$$, there exists exactly one unique real solution to the equation $$$f(x) = c$$$.
Next, we determine the range where the solution must lie. Since $$$c$$$ is in the range $$$[-10^{18}, 10^{18}]$$$, we can bound $$$x$$$ using magnitude estimates. We observe that $$$400^7 \approx 1.64 \times 10^{18}$$$. So any valid solution must lie within $$$x \in [-400, 400]$$$.
Now we can solve the equation using binary search. We search for the unique value of $$$x$$$ in the interval $$$[-400, 400]$$$ such that:
- If $$$f(x) \lt c$$$, we move right.
- If $$$f(x) \gt c$$$, we move left.
Because $$$f(x)$$$ is strictly increasing, binary search is guaranteed to converge to the correct unique solution. We compute the result with sufficient precision as required by the problem.
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}")
Time Complexity: The binary search runs for a fixed number of iterations (typically around 60 to achieve sufficient precision for real numbers). Each iteration evaluates the polynomial in constant time. Therefore, the total time complexity is $$$O(60) = O(1)$$$ per testcase.
Space Complexity: The solution uses only a few variables to store bounds and intermediate values. Therefore, the extra space complexity is $$$O(1)$$$.
M. Parity Pulse
Only the last bits of $$$k$$$ or any elements of the array matter.
Note that the same element can only be XORed or not XORed with $$$k$$$. After the second operation, the value cycles, so each index effectively has two choices: apply $$$k$$$ or not.
We analyze how a bitwise XOR with $$$k$$$ affects the parity (even or odd) of an element $$$a_i$$$. The key observation is that parity changes depend only on the least significant bit of $$$k$$$, that is the parity of $$$k$$$.
Case 1: $$$k$$$ is even
If $$$k$$$ is even, then its least significant bit is $$$0$$$. In this case, $$$a_i \oplus k$$$ does not change the parity of $$$a_i$$$. So every element keeps its original parity forever. Therefore, if the array is already alternating in parity, the answer is $$$0$$$. Otherwise, it is impossible to make it alternating, so we output $$$-1$$$.
Case 2: $$$k$$$ is odd
If $$$k$$$ is odd, then its least significant bit is $$$1$$$. In this case, applying XOR with $$$k$$$ flips the parity of the element.
We model the array using a binary array $$$b$$$, where: - $$$0$$$ represents even - $$$1$$$ represents odd
Each operation chooses an index $$$i$$$ and flips both $$$b_i$$$ and $$$b_{i+1}$$$. We want to transform the array into one of the two alternating patterns: $$$T_1 = [0, 1, 0, 1, \dots]$$$ or $$$T_2 = [1, 0, 1, 0, \dots]$$$.
Let $$$\text{diff}_i = b_i \oplus T_i$$$. Our goal is to make all values in $$$\text{diff}$$$ equal to $$$0$$$ using adjacent flips. We process the array from left to right. At each position, we maintain a running state (carry) that represents whether the previous position forces a flip effect onto the current one. If $$$\text{diff}_i \oplus \text{carry} = 1$$$, then we must apply an operation at index $$$i$$$, which flips the current position and propagates a carry of $$$1$$$ to the next position. Otherwise, no operation is needed and the carry becomes $$$0$$$.
This greedy left-to-right process computes the minimum number of operations. Also, the transformation is possible only if the total number of 1s in $$$\text{diff}$$$ is even. If it is odd, we output $$$-1$$$.
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)
Time Complexity: We compute the parity array and then try at most two target patterns, each processed in a single left-to-right pass. Therefore, the total time complexity is $$$O(n)$$$.
Space Complexity: We store the binary parity array and a few auxiliary variables for the greedy traversal. Therefore, the extra space complexity is $$$O(n)$$$.
N. The Boss Fight
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.
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)
Time Complexity: Each half generates at most $$$2^{\small{\frac{n}{2}}}$$$ subset states. Combining both halves requires either sorting and filtering plus a linear two-pointer merge. Therefore, the total time complexity is $$$O(2^{\small{\frac{n}{2}}} \cdot n)$$$.
Space Complexity: We store all subset states for both halves before filtering, each of size at most $$$2^{\small{\frac{n}{2}}}$$$. Therefore, the extra space complexity is $$$O(2^{\small{\frac{n}{2}}})$$$.
O. Factory Machine
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.
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])
Time Complexity: Each index $$$i$$$ is processed once, and for each state we compute a constant number of transitions. Therefore, the total time complexity is $$$O(n)$$$.
Space Complexity: The DP table has size $$$n \times 2$$$, so the extra space complexity is $$$O(n)$$$.
P. The Broken PC
The problem asks us to maximize the number of unique files that can be opened across all folders.
All folders are initially collapsed. To maximize the visibility of folder $$$i$$$, we want it to appear as high as possible on the screen. To do this, we collapse all folders before it (folders $$$1$$$ to $$$i-1$$$). In this configuration, folder $$$i$$$ will appear on row $$$i$$$.
When folder $$$i$$$ is expanded, its $$$a_i$$$ files occupy rows starting from row $$$i+1$$$ to row $$$i + a_i$$$. A file can only be opened if it appears within the screen height limit $$$m$$$, meaning its row index is at most $$$m$$$. So the $$$j$$$-th file of folder $$$i$$$ is visible if $$$i + j \le m \;\;\Rightarrow\;\; j \le m - i$$$.
From folder $$$i$$$, we can open at most $$$\text{files}_i = \max(0, \min(a_i, m - i))$$$ files.
We can freely toggle folders (collapse and expand) any number of times. This allows us to handle each folder independently by isolating it while keeping others collapsed. Therefore, the total answer is simply the sum of contributions from all folders.
If $$$i \ge m$$$, then folder $$$i$$$ can never contribute any visible files, since it would always be below the screen limit. Therefore, we only need to iterate over $$$1 \le i \le \min(n, m-1)$$$ and sum all $$$\text{files}_i$$$.
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)
Time Complexity: We process each folder at most once and perform only constant-time computations per folder. Therefore, the total time complexity is $$$O(n)$$$.
Space Complexity: The solution uses only the input array and a few auxiliary variables. Therefore, the extra space complexity is $$$O(1)$$$.
Comments (0)
