Problem Overview:

The problem involves identifying which song is playing at specific moments during a playlist where each song repeats a defined number of times. The playlist plays sequentially, with song i playing ci times and each play lasting ti minutes. Given moments vi, we need to determine which song is playing at each of those times.

Approach:

Prefix Sum Array: The key idea is to build a prefix sum array where prefix[i] represents the cumulative total duration of songs from the start to the end of song i. If ci is the repetition count and ti is the duration of song i, then the contribution of song i to the prefix sum is ci * ti. The prefix sum allows us to efficiently check which song is playing at any given moment by comparing the vi values against cumulative durations.

Linear Search: For each moment vi, iterate through the prefix sum array until you find the first i where prefix[i] >= vi.

Time Complexity:

Prefix Sum Construction: O(n) Query Handling: O(m) using linear search Overall: O(n + m) Space Complexity: O(n) for storing the prefix sum array.

 n, m = map(int, input().split())
    prefix = []
    for i in range(n):
        c, t = map(int, input().split())
        prefix.append(c * t)
        if i > 0:
            prefix[i] += prefix[i - 1]
    moments = list(map(int, input().split()))
    i = 0
    for j in range(m):
        while prefix[i] < moments[j]:
            i += 1
        print(i + 1)

To efficiently calculate the average sleep time, consider how to sum values over sliding windows without recalculating the entire sum for each new window.

The problem requires calculating the average sleep time over all possible weeks in Polycarp's records. A naive approach would involve iterating through each possible starting index and summing up the next k elements. However, this results in an O(n × k) complexity, which is inefficient for large values of n. Instead, we can use the sliding window technique to efficiently compute the sum for each week in O(n) time:

• First, compute the sum of the first k days and store it as the current sum.
• Iterate from day k to day n, updating the sum by adding the new day's sleep time and removing the sleep time of the day that is no longer in the window.
• Keep a running total of these weekly sums and compute the final average.

n, k = map(int, input().split()) 
a = list(map(int, input().split()))
curr = sum(a[:k])
total = curr
for i in range(k, n):
    curr += a[i] - a[i - k]
    total += curr

print(total / (n - k + 1))

It's easy to see that letter $$$z$$$ appears only in "zero" and $$$n$$$ appears only in "one", so we should print $$$1$$$ $$$\text{count}(n)$$$ times and then $$$0$$$ $$$\text{count}(z)$$$ times.

n = int(input())  
s = input()  
ones = s.count('n')  
zeros = s.count('z')  
print('1 ' * ones + '0 ' * zeros)

Try to find the maximum number of people who can have at least x burles after redistributing the money among selected subsets of people. The key observation is that the redistribution must be fair among the chosen subset.

The problem requires us to maximize the number of people who have at least x burles after any number of redistribution reforms. The key observation is that any subset of people chosen for redistribution will end up with an equal amount of money per person.

Approach:

1. Sort the savings in descending order: This ensures that we consider the wealthiest individuals first.
2. Iterate through the sorted list and track cumulative wealth: We keep summing the wealth and checking if the average wealth of the first i people is at least x.
3. Break when the condition fails: If at any step the cumulative wealth divided by i + 1 is less than x, the answer is i. Otherwise, the answer is n if we can include all individuals.

Example Walkthrough:

1. Case 1 ([5,1,2,1], x=3):

• Sort: [5,2,1,1]
• Sum stepwise: 5, 5+2=7, 7+1=8, 8+1=9
• The condition fails at index 2, so the answer is 2.

1. Case 2 ([11,9,11,9], x=10):

• Sort: [11,11,9,9]
• Sum stepwise: 11, 22, 31, 40
• The condition holds for all, so the answer is 4.

1. Case 3 ([4,3], x=5):

• Sort: [4,3]
• The sum never reaches 5, so the answer is 0.

1. Case 4 ([9,4,9], x=7):

• Sort: [9,9,4]
• Sum stepwise: 9, 18, 22
• The condition holds for 3, so the answer is 3.

Complexity Analysis:

• Sorting takes O(n log n).
• Iterating through the array takes O(n).
• Thus, the total complexity per test case is O(n log n).
• Since the sum of n across all test cases is at most 10^5, this solution efficiently handles the constraints.

t = int(input())  # Read number of test cases  

for _ in range(t):  
    n, x = map(int, input().split())  # Read n (number of people) and x (wealth threshold)  
    nums = sorted(map(int, input().split()), reverse=True)  # Sort wealth in descending order  
    
    total = 0  # Track cumulative wealth  
    for i in range(n):  
        total += nums[i]  # Add wealth of the i-th person  
        if total < x * (i + 1):  # Check if the average wealth falls below x  
            print(i)  # Maximum number of wealthy people possible  
            break  
    else:  
        print(n)  # If we never break, all n people can be wealthy  

To solve this problem, we need to determine if there exists a TV segment that can be removed without reducing the total covered time. Intuitively, a segment is redundant if every moment it covers is still covered by at least one other segment. Our goal is to efficiently check for such a segment.

Since the given time values can be large (≤ 10^9), storing them directly is inefficient. Instead, we use coordinate compression to map time values into a smaller range (at most 6 × 10^5). We then use a difference array approach: for each segment [li, ri], we increment coverage at li and decrement at ri + 1. Taking prefix sums over this array gives us the number of active TV sets at each moment. From this, we compute pref[i], which stores how many moments up to i are covered by exactly one segment.

Finally, for each segment [l, r], we check if pref[r] - pref[l - 1] is 0. This means that every moment in this range is covered by at least one other segment, making it redundant. If we find such a segment, we print its index; otherwise, we print -1. This approach runs in O(n log n) due to sorting and coordinate compression, making it efficient.

def solve():
    n = int(input())
    segments = []
    coord_set = set()

    # Collecting segments and unique coordinates
    for _ in range(n):
        l, r = map(int , input().split())
        segments.append((l, r + 1))
        coord_set.add(l)
        coord_set.add(r + 1)

    # Coordinate compression
    coord_list = sorted(coord_set)
    coord_map = {v: i for i, v in enumerate(coord_list)}
    m = len(coord_list)

    # Prefix array to track coverage
    coverage = [0] * (m + 1)
    for l, r in segments:
        coverage[coord_map[l]] += 1
        coverage[coord_map[r]] -= 1

    # Compute prefix sums for coverage
    for i in range(1, m):
        coverage[i] += coverage[i - 1]

    # Compute `pref` array, which stores the count of moments covered exactly once
    pref = [0] * m
    for i in range(1, m):
        pref[i] = pref[i - 1] + (1 if coverage[i - 1] == 1 else 0)

    # Find redundant segment
    for i, (l, r) in enumerate(segments):
        if pref[coord_map[r]] - pref[coord_map[l]] == 0:
            print(i + 1)
            return

    print(-1)

solve()

• What would you do if the constraints for the coordinates were up to (10^5)?

• You could use the line sweep algorithm, but the coordinates go up to (10^9). So, what shall we do?

• What if you use a dictionary instead of an array to store only the relevant positions?

We perform a line sweep using a dictionary to record events at positions where the number of covering segments changes. Sorting the dictionary keys lets us compute the prefix sum between these "critical" points. For each interval ([prev, cur)), the number of integer points is ((cur — prev)) and they are all covered by the current number of segments. This way, we aggregate the answer for every (k) in ([1, n]) without iterating over every integer in a huge range.

import sys
from collections import defaultdict

n = int(sys.stdin.readline().strip())
events = defaultdict(int)

# Record events: +1 when a segment starts, -1 when it ends (at r+1)
for _ in range(n):
    l, r = map(int, sys.stdin.readline().split())
    events[l] += 1
    events[r + 1] -= 1

# Sort the event points
keys = sorted(events.keys())
coverage = 0
prev = keys[0]
result = defaultdict(int)

# Line sweep: update coverage and count points in intervals
for point in keys:
    result[coverage] += point - prev
    coverage += events[point]
    prev = point

# Output counts for points covered by exactly 1 to n segments
ans = [result[k] for k in range(1, n + 1)]
print(*ans)
    

Let's consider a very special case of equal distances. What if all distances were equal to $$$1$$$? It implies that if some letter appears exactly twice, both occurrences are placed right next to each other.

That construction can be achieved if you sort the string, for example: first right down all letters '$$$a$$$', then all letters '$$$b$$$' and so on. If a letter appears multiple times, all its occurrences will be next to each other, just as we wanted.

Overall complexity: $$$O(|s|log|s|)$$$ or $$$O(|s|)$$$ per testcase.

for _ in range(int(input())):
  print(''.join(sorted(input())))

This is a 2D prefix sum problem.

Do the 2D prefix sum for the horizontal and vertical arrangements separately.

h, w = map(int, input().split())

grid = []
for i in range(h):
    grid.append(input())


horizontal = [[0] * w for _ in range(h)]
vertical = [[0] * w for _ in range(h)]

# indicate valid arrangements by 1 and invalid arrangements by 0.
# horizontal[r][c] == 1 means we can place a domino horizontally from grid[r][c - 1] to grid[r][c]
# vertical[r][c] == 1 means we can place a domino vertically from grid[r - 1][c] to grid[r][c]
for r in range(h):
    for c in range(w):

        if c > 0 and grid[r][c] == grid[r][c - 1] == '.':
            horizontal[r][c] = 1

        if r > 0 and grid[r][c] == grid[r - 1][c] == '.':
            vertical[r][c] = 1


# perform row-wise prefix sums
for r in range(h):
    for c in range(1, w):
        horizontal[r][c] += horizontal[r][c - 1]
        vertical[r][c] += vertical[r][c - 1]

# perform column-wise prefix sums
for c in range(w):
    for r in range(1, h):
        horizontal[r][c] += horizontal[r - 1][c]
        vertical[r][c] += vertical[r - 1][c]


q = int(input())

for i in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    r1, c1, r2, c2 = r1 - 1, c1 - 1, r2 - 1, c2 - 1 # changing 1-indexed input to 0-indexed

    horizontal_count = horizontal[r2][c2] - horizontal[r2][c1]
    if r1 - 1 >= 0:
        horizontal_count += horizontal[r1 - 1][c1] - horizontal[r1 - 1][c2]
    
    vertical_count = vertical[r2][c2] - vertical[r1][c2]
    if c1 - 1 >= 0:
        vertical_count += vertical[r1][c1 - 1] - vertical[r2][c1 - 1]
    
    answer = horizontal_count + vertical_count

    print(answer)

We have an array ( a ) of length ( n ) and must answer ( q ) queries. Each query modifies all elements in a given range ( [l, r] ) by setting them to ( k ) and asks whether the sum of the updated array is odd.

Each query is independent, meaning changes do not persist for subsequent queries.

Observe that changing a subarray to a fixed value (k) affects the total sum in a predictable way. The effect on the total sum can be computed by removing the sum of the existing subarray and adding the contribution of the new values.

How can prefix sum help us here?

1. Compute the initial sum of the array.
2. Compute the prefix sum for quick range sum retrieval.
3. For each query:
   • Compute the sum of the range ( [l, r] ).
   • Replace it with ( (r — l + 1) \times k ).
   • Check if the new sum is odd.
   • Print "YES" if odd, else "NO".

t = int(input())
    
for _ in range(t):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + a[i]
    
    total_sum = prefix[-1]
    results = []
    for _ in range(q):
        l, r, k = map(int, input().split())
        replaced_range_old_sum = prefix[r] - prefix[l - 1]
        replaced_range_new_sum = (r - l + 1) * k
        new_sum = total_sum - replaced_range_old_sum + replaced_range_new_sum
        
        if new_sum % 2 == 1:
            results.append("YES")
        else:
            results.append("NO")

    print("\n".join(results) + "\n")

• Computing the total sum: ( O(n) )
• Computing the prefix sum: ( O(n) )
• Each query: ( O(1) ) (using prefix sum)
• Total complexity: ( O(n + q) ) per test case, which is optimal given constraints.