Since we can only utilize either the length or width of all the blankets, the best choice for creating the longest possible rope is to first utilize all the blankets and use the longest side (length or width) of each blanket.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(1)$$$

import sys
input = lambda : sys.stdin.readline().strip()


for _ in range(int(input())):
    n, h = map(int, input().split())
   
    rope = 0
    for i in range(n):
        l, w = map(int, input().split())
        rope += max(l, w)
   
    if rope >= h:
        print('YES')
    else:
        print('NO')

Output binary search.

The key insight is that if we have a wagon size greater than or equal to $$$\max(d_1, d_2, \dots, d_n)$$$, we only need to go once for every village. Hence, the sum of all $$$a_i$$$ is the minimum achievable time to deliver the water with any size.

If $$$\sum_{i=1}^{n} a_i$$$ is already greater than $$$k$$$, we can't make Empress Taytu happy with any size. If not, starting from 1 (left) up to $$$\max(d_1, d_2, \dots, d_n)$$$ (right), we can perform a binary search by checking whether it's achievable with a given size within $$$k$$$ hours.

For a single village, we can calculate the number of trips the wagon has to make by ceil dividing its demand by the wagon size. Then, we can calculate the total time needed for one village by multiplying the number of trips with the time it takes for one trip ($$$a_i$$$). After adding the total time for all villages, we will check if it is less than or equal to $$$k$$$. Overall, the complexity of the checker is $$$O(n)$$$.

The complexity of the binary search algorithm used in this solution is $$$O(\log(\max(d_1, d_2, \dots, d_n)))$$$. Since we need to check for each possible size of the wagon, the overall complexity of the algorithm is $$$O(n \log m)$$$, where $$$m = \max(d_1, d_2, \dots, d_n)$$$.

• Space Complexity: $$$O(1)$$$

from math import ceil
from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    d = list(map(int, input().split()))
    a = list(map(int, input().split()))

    if sum(a) > K:
        print(-1)
        continue

    def checker(size):
        time = 0
        for i in range(N):
            time += ceil(d[i]/size)*a[i]
        return time <= K
    
    left = 1
    right = max(d)
    while left <= right:
        mid = left + (right - left)//2
        if checker(mid):
            right = mid - 1
        else:
            left = mid + 1
    print(left)

Observation: After an increment operation, there is always a corresponding decrement operation.

Let's represent the characters with numerical values, such as their ASCII values. During an increment operation, the ASCII value of that character increases by $$$1$$$, and during a decrement operation, it decreases by $$$1$$$. Importantly, after an increment operation, the total sum of ASCII values of the word decreases by $$$1$$$, and after a decrement operation, the total sum increases by $$$1$$$. However, since one operation combines both increment and decrement, the total ASCII sum remains unchanged.

Therefore, to decrypt the message, we only need to check if there exists a substring with a size equal to the size of the sensitive word (let's denote it as $$$m$$$) and the sum of ASCII values of its characters is equal to that of the sensitive word. For this, we can employ a fixed-size sliding window approach with size $$$m$$$.

• Time Complexity: $$$O(n)$$$ where $$$n$$$ is the size of the decrypted message.
• Space Complexity: $$$O(1)$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    s = input()
    w = input()

    target = 0
    window_sum = 0
    for i in range(M):
        target += ord(w[i])
        window_sum += ord(s[i])
    
    found = False
    for i in range(M, N):
        if window_sum == target:
            found = True
            break
        window_sum += ord(s[i])
        window_sum -= ord(s[i - M])
    
    if window_sum == target or found:
        print("YES")
    else:
        print("NO")

In the first round, each group consists of two teams. Then, in the second round, every two consecutive groups are merged, and so on. This problem resembles a typical divide and conquer approach. Now, the question is, given the left group and the right group, how can we merge them and calculate the number of wins for every team efficiently?

One possible solution is to perform a binary search on the right team for each team in the left group, determining the number of players with strength strictly less than the current player's strength. Repeat this process for all players in the right group. Then, combine the two arrays using two pointers. The time complexity for this solution is $$$O(2^n * log^2(2^n))$$$, where $$$2^n$$$ is the size of the array.

Another approach is to use two pointers to calculate the wins. After calculating and updating both arrays, we can merge them together. This approach has a time complexity of $$$O(2^n*log(2^n)))$$$.

• Space Complexity: $$$O(2^n)$$$

def mergeSort(arr,l,r):
    if l == r:
   	 return
    
    # get the mid point of the current array and merge sort it
    mid = (l + r)//2
    mergeSort(arr,l,mid)
    mergeSort(arr,mid + 1, r)
    # merge the two halves after sorting them and calculating the answer
    merge(arr,l,mid,r)
 
def merge(arr,l,mid, r):
    # wins array to hold the number of wins each team have
 
    wins = [0]*(r - l + 1)
    # array to hold merged list
    merged = []
    
    # calculate the wins for the first group
    ptr = mid + 1
 
    # for every element of the first group
    for i in range(l,mid + 1):
   	 # move the second groups point to an element which is greater or equal to it
  	 
   	 while ptr <= r and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
 
   	 # the total numbe of wins for the current element
   	 #is the nubmer of element in the second group
   	 #that is lower than it
   	 wins[i - l] = ptr - (mid + 1)
 
    # same thing for the second group
    ptr = l
    for i in range(mid + 1,r+1):
   	 while ptr <= mid and arr[ptr][1] < arr[i][1]:
   		 ptr += 1
   	 wins[i - l] = ptr - l
 
    # merge the two groups based on the new value
    pt1 = l
    pt2 = mid + 1
 
    while pt1 <= mid or pt2 <= r:
   	 if (pt2 > r) or (pt1 <= mid and arr[pt1][1] + wins[pt1 - l] < arr[pt2][1] + wins[pt2 - l]):
   		 arr[pt1][1] += wins[pt1 - l]
   		 merged.append(arr[pt1])
   		 pt1 += 1
   	 else:
   		 arr[pt2][1] += wins[pt2 - l]
   		 merged.append(arr[pt2])
   		 pt2 += 1
 
    arr[l:r + 1] = merged
 
 
 
def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr = [[i,j] for i,j in enumerate(arr)]
    mergeSort(arr,0,2**n - 1)
    ans = [i[1] for i in sorted(arr,key = lambda x: x[0])]
    
    print(*ans)
 
t = int(input())
for _ in range(t):
    solve()

Find the time each gun explodes then you can take the maximum one.

Use monotonic stack to track the damage a gun receives for a gun behind him.

To determine the time it takes for each gun to explode, we can employ a monotonic stack approach. Starting from the first gun, which we know for sure will explode at infinity, we can represent each gun as a tuple $$$(t_i, p_i)$$$, where $$$t_i$$$ is the life of the $$$i$$$-th gun and $$$p_i$$$ is its power. These tuples are then pushed onto the stack.

For each gun $$$i$$$, we can understand that it receives a hit from the last gun on the stack. The damage it receives can be calculated as stack[-1][-1] * (stack[-1][0] - d), where stack[-1][0] and stack[-1][-1] represent the life and power of the gun at the end of the stack, respectively. Here, $$$d$$$ represents the duration of gun $$$i$$$ before it encounters the gun at the end of the stack. If the gun at the end of the stack cannot reduce the health of gun $$$i$$$ to zero, we decrement the received damage with the gun's health and pop from the stack.

• Time Complexity: $$$O(n)$$$
• Space Complexity: $$$O(n)$$$

import sys
from math import ceil, inf
input = lambda : sys.stdin.readline().strip()


for t in range(int(input())):
    n = int(input())
    health = list(map(int, input().split()))
    power = list(map(int, input().split()))


    stack = [(inf, power[0])]
    ans = 0
    for i in range(1, n):
        duration = 0
        while health[i] - (stack[-1][0] - duration)*stack[-1][-1] > 0:
            t, p = stack.pop()


            health[i] -= (t-duration)*p
            duration += (t-duration)
       
        duration += ceil(health[i]/stack[-1][-1])
        stack.append((duration, power[i]))
        ans = max(ans, duration)
   
    print(ans)

Topic: Greedy

What is the maximum number of points for the $$$(k + 1)$$$-th team?

If $$$k$$$ equals $$$n$$$ (the last position), the answer is $$$0$$$ since $$$0$$$ points are needed to secure the last position.

Let's calculate for other positions:

Firstly, let's determine the maximum number of points the $$$(k + 1)$$$-th team can have. To maximize this, the first $$$(k + 1)$$$ teams will win all matches against the remaining $$$n - (k + 1)$$$ teams, resulting in the first $$$(k + 1)$$$ teams having points equal to $$$(n - (k + 1)) \cdot 3$$$.

Now, our task is to maximize the points of both the $$$k$$$-th and $$$(k + 1)$$$-th teams. To achieve this, we focus on the remaining matches involving the $$$k$$$ teams (excluding the $$$(k + 1)$$$-th team). Since we aim to maximize the minimum points within these $$$k$$$ teams, we need to maximize the minimum points in the remaining matches.

For $$$k = 2$$$, there is only $$$k - 1 = 1$$$ match remaining for a team. If a team wins, the other team will have $$$0$$$ points, resulting in a minimum of $$$0$$$ points. However, to maximize the minimum points, it's better if the match ends in a draw, resulting in a minimum of $$$1$$$ point. For $$$k = 3$$$, there are $$$k - 1 = 2$$$ matches remaining for a team. If a team wins one and loses one, all teams will have $$$3$$$ points, resulting in a minimum of $$$3$$$ points. However, if one team wins both matches, the minimum points will be $$$0$$$ or $$$1$$$.

We observe that if a match ends in a win or a loss, the overall points are $$$3$$$, whereas if it is a draw, it is $$$2$$$ (with $$$1$$$ point for each team). We aim to avoid losing points in a draw. The issue arises when there is only one match remaining and it's either a win or a loss, resulting in a minimum of $$$0$$$ points. However, with a draw, the minimum is $$$1$$$ point. For two matches, we can achieve an overall of $$$6$$$ points with wins, distributing $$$3$$$ points to each team.

Hence, to maximize the minimum points within the $$$k$$$ teams, we have $$$(k - 1)$$$ matches for each team. If $$$(k - 1)$$$ is even, the team wins $$$\frac{k - 1}{2}$$$ matches and loses $$$\frac{k - 1}{2}$$$ matches. If $$$(k - 1)$$$ is odd, the team wins $$$\frac{k - 2}{2}$$$ matches, loses $$$\frac{k - 2}{2}$$$ matches, and draws $$$1$$$ match. Generally (for even or odd), the points it can obtain is $$$\left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$.

Now, both the $$$k$$$-th and $$$(k + 1)$$$-th teams have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2$$$ points. The only match remaining is between them. We can secure the $$$k$$$-th team in the $$$k$$$-th position by ensuring it wins the match against the $$$(k + 1)$$$-th team. However, if both teams have the same number of points, they will both secure the $$$k$$$-th position. Therefore, to minimize the points required to guarantee the $$$k$$$-th position, the match should end in a draw. Finally, the $$$k$$$-th team will have $$$(n - (k + 1)) \cdot 3 + \left\lfloor \frac{k - 1}{2} \right\rfloor \cdot 3 + (k - 1) \% 2 + 1$$$ point.

• Time Complexity: $$$O(1)$$$
• Space Complexity: $$$O(1)$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())

    if N == K:
        print(0)
        continue

    ans = (N - (K + 1))*3 + ((K - 1)//2)*3 + (K - 1)%2 + 1
    print(ans)