To solve this problem efficiently, we simulate the sequence of operations while maintaining two values: the current number of ice cream packs and the count of distressed children. We start with $$$x$$$ packs and iterate through $$$n$$$ operations. If a carrier ($$$+d$$$) arrives, we increase our stock by $$$d$$$. If a child ($$$-d$$$) requests d packs, we check if we have enough ice cream. If yes, we serve the request and decrease our stock; otherwise, we increment the count of distressed kids. By processing all operations sequentially, we determine the final ice cream count and the number of distressed kids. This approach runs in $$$O(n)$$$ time, making it efficient given the constraints.

def solve():
    n, cur = map(int, input().split())
    distress = 0
    
    for _ in range(n):
        op, d = input().split()
        d = int(d)
        
        if op == '+':
            cur += d
        elif cur >= d:
            cur -= d
        else:
            distress += 1
    
    print(cur, distress)

solve()

To solve this problem, we need to construct a sequence $$$b$$$ that satisfies the given conditions. The key idea is to ensure that $$$b$$$ is strictly increasing and does not contain any elements from $$$a$$$.

Steps to Solve:

1. Initialize a variable Last_elem to $$$0$$$, which will keep track of the last value added to the sequence $$$b$$$.
2. Iterate through each element in the sequence $$$a$$$.
3. For each element $$$a_i$$$:
   • Increment Last_elem by $$$1$$$.
   • If Last_elem is equal to $$$a_i$$$, increment Last_elem by $$$1$$$ again to ensure $$$b_i \neq a_i$$$.
4. After processing all elements, Last_elem will hold the minimum value of $$$b_n$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    last_elem = 0
    for num in a:
        last_elem += 1
        if last_elem == num:
            last_elem += 1
    print(last_elem)

We need the deque data structure to solve this problem. We iterate the given permutation starting from the first element and we append to the left of our deque either if it is empty or the element at the 0-th index of our deque is larger than the current element we are about to add to our deque. Otherwise we append to the end of our deque because appending a larger number than what we currently have at the 0-th index of our deque will definitly make our final answer lexicographically larger.

from collections import deque

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

    ans = deque()
    for num in arr:
        if ans and num < ans[0]:
            ans.appendleft(num)
        else:
            ans.append(num)
    
    print(*ans)

Try breaking the problem into smaller subproblems by dividing the string into two halves and ensuring one half follows the rule while the other is recursively solved.

We define a recursive function calc(l, r, c), where:

• l and r represent the start and end indices of the current segment.
• c represents the character we are trying to make this segment follow.
• The function returns the minimum number of moves needed to convert the substring s[l:r] into a c-good string.

Base Case: If the length of the segment is 1 (r = l):

• If s[l] = c, return 0 (no changes needed).
• Otherwise, return 1 (we must change s[l] to c).

Recursive Case: We split the segment into two halves and consider two possible transformations:

• case 1: The first half should be fully filled with c, and the second half should be (c+1)-good.
• case 2: The second half should be fully filled with c, and the first half should be (c+1)-good.

For each case, we compute the number of changes needed:

• left_result: Changes required to make the first half fully filled with c + recursive call on the second half to make it (c+1)-good.
• right_result: Changes required to make the second half fully filled with c + recursive call on the first half to make it (c+1)-good.

The final result for this segment is: min(left_result,right_result)

Time Complexity The function processes each segment by counting characters (in $$$O(n)$$$ time) and then recursively splitting it into two halves. Since each level of recursion does a total of $$$O(n)$$$ work and there are $$$\log n$$$ levels (because the segment size halves each time), the total complexity is $$$O(n \log n)$$$.

Space complexity The only space used in this solution is the call stack due to recursion. Since the recursion divides the problem into two halves at each step, the maximum depth of the recursion tree is $$$\log n$$$. Therefore, the space complexity is determined by the depth of the recursion, which is $$$O(\log n)$$$.

def calc(l, r, c):
    if l == r:
        if s[l] == c:
            return 0
        return 1
    
    mid = (l + r) // 2
    
    left_changes = (mid - l + 1) - s[l:mid + 1].count(c)    
    left_result = left_changes + calc(mid + 1, r, chr(ord(c) + 1))
 
    right_changes = (r - mid) - s[mid + 1:r + 1].count(c)
    right_result = right_changes + calc(l, mid, chr(ord(c) + 1))
 
    return min(left_result, right_result)
 
for _ in range(int(input())):
    n = int(input())
    s = input()
 
    print(calc(0, len(s) - 1, 'a'))

Instead of building the whole transformed string, find a way to track where each character comes from in the original string. Notice that each step doubles the string and follows a clear pattern.

The problem asks us to find the $$$k^{th}$$$ character after repeatedly transforming a string. Since the string grows extremely fast, it is impossible to generate the final version directly. Instead, we need a smarter way to determine the answer.

Each transformation doubles the string: the first half stays the same, and the second half is the same as the first but with uppercase and lowercase letters swapped. This means that any character in the final string can be traced back to its original position in the first version.

To find the character at position $$$k$$$, we work backwards to see where it came from. If $$$k$$$ is in the first half of a transformation step, it remains unchanged. If it is in the second half, we can shift it back to the first half of the previous step and apply a case swap. We repeat this process until we reach the original string.

import sys 

def solve():
    
    # Read input: length of binary string
    n = int(sys.stdin.readline().strip())
    
    # Convert input string into a list of integers (0s and 1s)
    nums = [int(i) for i in sys.stdin.readline().strip()]

    zero = []   # Tracks subsequences ending in 0
    one = []    # Tracks subsequences ending in 1
    ans = []    # Stores the assigned subsequence number for each character
    maxi = 0    # Keeps track of the total number of subsequences used

    # Process each character in the binary string
    for val in nums:
        if val == 1:  # If the current character is '1'
            if zero:
                # If there exists a subsequence ending in '0', use it
                temp = zero.pop()
            else:
                # Otherwise, create a new subsequence
                maxi += 1
                temp = maxi 
              
            # Mark that this subsequence now ends in '1'
            one.append(temp)
            ans.append(temp)

        else:  # If the current character is '0'
            if one:
                # If there exists a subsequence ending in '1', use it
                temp = one.pop()
            else:
                # Otherwise, create a new subsequence
                maxi += 1
                temp = maxi 

            # Mark that this subsequence now ends in '0'
            zero.append(temp)
            ans.append(temp)

    # Print the total number of subsequences used
    print(max(ans))
    
    # Print the assigned subsequence number for each character
    print(*ans)

q = int(sys.stdin.readline().strip())

for _ in range(q):
    solve()

If we have a list of subarrays where the element at index $$$i$$$ is the max, which subarrays should we check to be sufficient?

Checking subarrays which end or start at index $$$i$$$ is sufficient, so we can optimize our solution with this observation as the basis.

Let's look at the problem from the perspective of each $$$a_i$$$. We want to check whether the sum of the subarrays, where $$$a_i$$$ is the maximum element, exceeds $$$a_i$$$ or not.

Firstly, we must find out in which subarrays is $$$a_i$$$ the maximum. This involves finding the previous greater element index and the next greater element index of $$$i$$$, which can be done for all indices in $$$O(n)$$$ using monotonic stack. Take these indices as $$$x_i$$$, $$$y_i$$$.

Take $$$(j,k)$$$, which represents the sum of a subarray which starts at index $$$j$$$ and ends at index $$$k$$$, where $$$j∈[x_i +1, i]$$$, $$$k∈[i,y_i−1]$$$. If $$$(j,k)>a_i$$$, then $$$(j,i−1)+(i,i)+(i+1,k)>a_i$$$, giving us $$$(j,i−1)+(i+1,k)>0$$$. Hence, at least one of the subarrays, $$$(j,i−1)$$$ or $$$(i+1,k)$$$ has a sum greater than $$$0$$$, which implies that one of subarrays $$$(j,i)$$$, $$$(i,k)$$$ has sum greater than $$$a_i$$$, so only checking subarrays which start or end at index $$$i$$$ suffices.

To determine whether there exists a subarray where the sum exceeds its maximum value, we utilize a Monotonic Stack to efficiently find the previous greater element indices and Prefix Sums to enable quick subarray sum queries.

For any index $$$i$$$, the monotonic stack ensures that:

While processing $$$a_i$$$ , we pop all elements from the stack that are less than or equal to $$$a_i$$$. This guarantees that for all popped indices, $$$a_i$$$ is the first greater element to their right. For the current popped index $$$v$$$, we check the sum from $$$v$$$ to $$$(i-1)$$$ > $$$0$$$ If true, it implies that some subarray sum exceeds its maximum, violating the required condition. In this case, we immediately return $$$NO$$$ since at least one problematic subarray exists.

$$$Why$$$ $$$This$$$ $$$is$$$ $$$Sufficient?$$$

The monotonic stack guarantees that we only check valid subarrays where the current element is the maximum, ensuring:

No problematic subarray is missed.

Minimal subarray checks, avoiding an exhaustive search.

Since we apply the same check on both the original and reversed array, we ensure correctness across all possible subarrays.

$$$Final$$$ $$$Steps$$$

Process the array from left to right: Use a monotonic stack to track the next greater elements. As elements are popped, check if the suffix sum (from the popped index up to $$$i−1$$$) is greater than 0. If true, print $$$NO$$$ and terminate early. Reverse the array and repeat the process to handle Next greater elements efficiently.

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

import sys

def solve():
    n = int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))

    def prevGreater(nums):
        stack = []
        pref = [0]
        
        for num in nums:
            pref.append(pref[-1] + num)
    
        for i in range(n):

            while stack and nums[stack[-1]] <= nums[i]:
                v = stack.pop()

                if  pref[i] - pref[v]> 0:
                    return False
                
            stack.append(i)

        return True
    
    if prevGreater(nums) and prevGreater(nums[::-1]):
        return "YES"
    
    return "NO"

t = int(sys.stdin.readline().strip())
for _ in range(t):
    print(solve())