To determine the language of a sentence, you only need to check its last few characters. Since only four possible suffixes exist, a direct string comparison is the simplest and most efficient approach.

The problem provides a straightforward method for identifying the language of a sentence based on its ending. Since the constraints guarantee that each sentence ends with one of the given suffixes, we can simply check the last characters of the string and classify the language accordingly. To implement this, we observe the following rules:

• If a sentence ends with "po", it is Filipino and the last letter is “o”.
• If it ends with "desu" or "masu", it is Japanese and the last letter is “u”.
• If it ends with "mnida", it is Korean and the last letter is “a”

t = int(input())

for _ in range(t):
    string = input()
    if string[-1] == "u":
        print("JAPANESE")
    elif string[-1] == "o":
        print("FILIPINO")
    else:
        print("KOREAN")

Think about sorting both arrays and then mapping the actual temperatures to the correct days while maintaining the given constraints.

The problem requires us to rearrange the given temperatures in array b such that each temperature matches a day in array a while ensuring the absolute difference constraint |a[i] - b[i]| ≤ k holds.

Approach:

1. Pair Each Forecast with its Index:

• Create an array of pairs (a[i], i), where each pair stores the forecast temperature and its corresponding index.

1. Sort Both Arrays:

• Sort the forecasted temperatures (a) based on their values.
• Sort the actual temperatures (b) in ascending order.

1. Assign the Sorted Temperatures:

• Iterate through both sorted arrays and assign each temperature from b to the corresponding position in a based on their sorted order.
• Since b can always be rearranged to satisfy the condition, sorting ensures that the best possible match is made greedily.

1. Restore the Original Order:

• Since we initially sorted a, we need to place the values in b back into their original positions using the stored indices.

Example Walkthrough:

Case 1

Input:
5 2 1 3 5 3 9 2 5 11 2 4 - Original a: [(1,0), (3,1), (5,2), (3,3), (9,4)]
- Sorted a: [(1,0), (3,1), (3,3), (5,2), (9,4)]
- Sorted b: [2, 2, 4, 5, 11]
- Mapping them in order: [2, 2, 4, 5, 11]
- Restoring order: [2, 2, 5, 4, 11]
Output:
2 2 5 4 11

Case 2

Input:
6 1 -1 3 -2 0 -5 -1 -4 0 -1 4 0 0 - Sorted a: [(-5,4), (-2,2), (-1,0), (-1,5), (0,3), (3,1)]
- Sorted b: [-4, -1, 0, 0, 0, 4]
- Mapping: [-4, -1, 0, 0, 0, 4]
- Restoring order: [0, 4, -1, 0, -4, 0]
Output:
0 4 -1 0 -4 0

Complexity Analysis:

• Sorting a and b each takes O(n log n).
• Mapping elements and restoring order takes O(n).
• Thus, the total complexity per test case is O(n log n).
• Given that the sum of n over all test cases is at most 10^5, this is efficient.

t = int(input())
for _ in range(t):
    n, k =  map(int, input().split())
    a =  list(map(int, input().split()))
    b =  list(map(int, input().split()))
    
    # Pair forecast values with indices
    a = [(a[i], i) for i in range(n)]
    
    # Sort both arrays
    a.sort()
    b.sort()
    
    # Rearrange elements in the correct order
    ans = [0] * n
    for i in range(n):
        _, ind = a[i]
        ans[ind] = b[i]
    
    print(*ans)

Instead of checking all possible sub-arrays, think about how you can maintain a valid segment dynamically while iterating through the prisoners.

A brute-force approach would be to check all possible contiguous sub-arrays of size $$$c$$$, leading to an O($$$n$$$ * $$$c$$$) complexity, which is inefficient for large $$$n$$$. Instead, we can solve this efficiently using a two-pointer (sliding window) approach in O($$$n$$$) time:

• Maintain a window of prisoners that satisfies the severity constraint.
• Use a $$$left$$$ pointer to track the start of the valid segment.
• Iterate with pointer $$$right$$$, and whenever a prisoner exceeds $$$t$$$, reset $$$left$$$ to start a new valid window.
• Whenever the current window size is greater or equal to $$$c$$$, it contributes to a valid selection, so we increment our answer by one.

Time Complexity O($$$n$$$)

space complexity O(1)

n, t, c = [int(i) for i in input().split()]
prisoners = [int(i) for i in input().split()]

answer = 0
left = 0
for right in range(n):
    if prisoners[right] > t:
        left = right + 1 
    
    current_length = right - left + 1
    if  current_length >= c:
        answer += 1

print(answer)

Instead of checking every year (which is too slow), focus only on the years when the population actually changes—births and deaths.

Use a line sweep technique: treat birth years as +1 events and death years as -1 events, then process the years in sorted order.

Approach:

We need to find the year with the most people alive at once. Given the huge range of years (**1 to 10⁹**), checking each year individually is impossible.

Instead, we only care about years where a birth or death happens. We can track these changes efficiently using a dictionary:

1. Mark population changes:

• When someone is born at b, increase the count (+1).
• When someone dies at d, decrease the count (-1).
• Store these events in a dictionary.

1. Sort and process events:

• Extract all unique years, sort them, and process them sequentially.
• Maintain a running total of the population at each step.
• Track the maximum population and the earliest year that achieves it.

Why Use a Dictionary Instead of an Array?

A naive approach would be to use an array indexed by years, but since the range of years can go up to 10⁹, this would require an unfeasible amount of memory. Instead, we use a dictionary to store only the relevant years where changes occur, making the approach both memory-efficient and fast.

Why This Works:

By focusing only on important years (births and deaths), we avoid unnecessary calculations and solve the problem efficiently. This is a classic line sweep technique used in event-based problems.

This approach works in O(n log n) time due to sorting, which is efficient for n ≤ 10⁵.

from collections import defaultdict

n = int(input())
events = defaultdict(int)

# Mark birth and death events
for _ in range(n):
    birth, death = map(int, input().split())
    events[birth] += 1
    events[death] -= 1  # Death marks the end of life

# Sort event years
years = sorted(events.keys())

# Sweep through the years
max_people = 0
year = 0
current_population = 0

for y in years:
    current_population += events[y]
    if current_population > max_people:
        max_people = current_population
        year = y  # Pick the smallest year in case of ties

print(year, max_people)

To efficiently determine the temperature for each cell, consider how to propagate the air conditioner temperatures while minimizing unnecessary computations.

The problem requires finding the minimum temperature in each cell, given that each air conditioner contributes its temperature plus the absolute difference from its position. A naive approach would be to iterate over each cell and compute the minimum temperature using all air conditioners, resulting in an O(n * k) complexity, which is inefficient for large values of (n). Instead, we use a more optimized approach with two sweeps (forward and backward) in O(n)time:

• First, initialize an array with infinity and set the temperature at air conditioner positions.
• Perform a left-to-right sweep, propagating the minimum temperature possible at each position.
• Perform a right-to-left sweep to ensure that we get the minimum valid temperature at each position.

t = int(input())
for _ in range(t):
n, k = map(int, input().split()) 
pos = list(map(int, input().split())) temp = list(map(int, input().split()))
all = [float('inf')] * n  
for i in range(k):  
    all[pos[i] - 1] = temp[i]  

forward = [float('inf')] * n  
forward[0] = all[0]  
for i in range(1, n):  
    forward[i] = min(forward[i - 1] + 1, all[i])  

backward = [float('inf')] * n  
backward[-1] = all[-1]  
for i in range(n - 2, -1, -1):  
    backward[i] = min(backward[i + 1] + 1, all[i])  

result = [min(forward[i], backward[i]) for i in range(n)]  
print(*result)  

In this problem, you are given two integer arrays, $$$a$$$ and $$$b$$$, and the task is to maximize the sum of the products of corresponding elements from the two arrays. You are allowed to reverse at most one continuous subarray (subsegment) from the array $$$a$$$ to achieve the maximum possible sum. The challenge is to efficiently determine the best subarray to reverse in order to maximize this sum.

The first step is to calculate the original sum of the dot product between $$$a$$$ and $$$b$$$ without any reversals. This serves as the baseline. Then, we explore how reversing different subarrays of $$$a$$$ impacts the sum. The key observation is that reversing a subarray alters the interactions between elements of $$$a$$$ and $$$b$$$. By considering both odd-length and even-length subarrays centered around different points, we calculate how the reversal changes the sum. For each potential subarray, we compute the difference in the products of the elements before and after the reversal, which is referred to as the delta.

For odd-length subarrays, the reversal will be centered around a single element. The key is to consider each possible center of the subarray and expand outwards symmetrically. For example, if we have a center at index $$$i$$$, the subarray can be expanded outward to include $$$a_{i-1}$$$, $$$a_{i+1}$$$, and so on, forming an odd-length subarray like [ $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$], [$$$a_{i-2}$$$, $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ ], and so on.

When we reverse this subarray, we swap the elements symmetrically, and we want to compute how this reversal changes the sum of the element-wise products. We calculate the difference between the products of $$$a$$$ and $$$b$$$ before and after the reversal. For each odd-length subarray, we check if this reversal gives us a better sum.

For even-length subarrays, the reversal is centered between two adjacent elements. For example, if we have a center between indices $$$i$$$ and $$$i+1$$$, the subarray will start at $$$a_i$$$ and end at $$$a_{i+1}$$$. This forms an even-length subarray that can be expanded symmetrically outwards. The subarrays could look like [ $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$ ], [ $$$a_{i-2}$$$, $$$a_{i-1}$$$, $$$a_i$$$, $$$a_{i+1}$$$, $$$a_{i+2}$$$, $$$a_{i+3}$$$ ], and so on.

Just like with odd-length subarrays, we reverse the elements of the subarray, compute the change in the sum of the product, and check if this reversal provides a better sum.

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# Calculate the original sum S.
original_sum = sum(a[i] * b[i] for i in range(n))

best = 0  # Best improvement found by reversing a subarray

# Check odd-length reversals (centered at i)
for center in range(n):
    current_delta = 0
    l, r = center - 1, center + 1
    while l >= 0 and r < n:
        # Calculate the delta added by expanding to include a[l] and a[r]
        current_delta += a[l] * b[r] + a[r] * b[l] - a[l] * b[l] - a[r] * b[r]
        best = max(best, current_delta)
        l -= 1
        r += 1

# Check even-length reversals (center between i and i+1)
for center in range(n - 1):
    current_delta = 0
    l, r = center, center + 1
    while l >= 0 and r < n:
        current_delta += a[l] * b[r] + a[r] * b[l] - a[l] * b[l] - a[r] * b[r]
        best = max(best, current_delta)
        l -= 1
        r += 1

# Output the maximum sum achievable after at most one reversal
print(original_sum + best)