Simply put, the problem is asking us to represent $$$S$$$, as a summation of numbers from the set $$${1, 2, 3, … ,n }$$$.

Obviously there are many ways to do that, for example one might use $$$1$$$ $$$S$$$ times, but in this problem we are asked to use the minimum number of elements and output how many we used.

Since we have all the numbers from $$$1$$$ to $$$n$$$ and we can use each element repeatedly, we can afford to be greedy and always use the largest value less or equal to $$$S$$$, until we get the sum of the selected elements equal to $$$S$$$. This ensures that we use the fewest possible numbers.

This process can easily be represented by a ceil division of $$$S$$$ by $$$n$$$.

because $$$⌈S/n⌉$$$ tells us how many times we would need to add the largest possible number (which is $$$n$$$) to reach or exceed $$$S$$$.

Time complexity: $$$O(1)$$$. Space complexity: $$$O(1)$$$

n,S = map(int, input().split())
	
print((S + n - 1) //  n) 

The problem involves removing adjacent 01 or 10 pairs from a binary string until no more moves are possible. The goal is to find the minimum possible remaining length of the string.

Stack-Based Solution: Traverse the binary string while maintaining a stack. If the stack is non-empty and the current character forms a removable pair (01 or 10) with the top of the stack, pop the stack. Otherwise, push the current character onto the stack. The size of the stack at the end represents the minimum remaining length.

n = int(input().strip())
s = input().strip()
stack = []
for char in s:
    if stack and stack[-1] != char:
        stack.pop()  # Remove 01 or 10 pair
    else:
        stack.append(char)  # Push character if no pair found
print(len(stack))

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)

• Think of a queue (FIFO structure) to store the most recent k unique chats.
• Use a set to quickly check if a friend's chat is already on the screen.

When a new chat arrives and the screen is full, remove the oldest chat before adding the new one.

The problem requires maintaining the most recent k unique chat messages in order.
Key observations:
1. If a friend sends multiple messages, only the first occurrence matters.
2. If the chat screen is full (k elements), the oldest message is removed when a new unique message arrives.

Approach:

• Use a deque (chat_screen) to store recent unique chats while maintaining order.
• Use a set (seen) to track which friends are currently displayed.
• Process each message:
• If it's already in seen, ignore it.
• Otherwise:
  • If chat_screen is full, remove the oldest chat (last element).
  • Add the new chat to the front of chat_screen and update seen.
• Print the final chat list.

This method ensures an O(n) time complexity, which is efficient for large inputs.

from collections import deque

def chat_screen(n, k, messages):
    chat_screen = deque()
    seen = set()

    for id_i in messages:
        if id_i not in seen:
            if len(chat_screen) == k:
                removed = chat_screen.pop()
                seen.remove(removed)
            
            chat_screen.appendleft(id_i)
            seen.add(id_i)

    print(len(chat_screen))
    print(*chat_screen)

n, k = map(int, input().split())
messages = list(map(int, input().split()))
chat_screen(n, k, messages)

• Think of maintaining two lists to track subsequences ending in 0 and 1.
• A greedy approach helps in assigning characters to subsequences optimally.

• If a 1 appears, assign it to a subsequence that previously ended in 0.
• If a 0 appears, assign it to a subsequence that previously ended in 1.

The problem requires dividing the binary string into the minimum number of subsequences such that each follows an alternating 0-1 or 1-0 pattern.

1. Each character belongs to exactly one subsequence.
2. If a 1 appears, it should ideally continue a subsequence ending in 0, and vice versa.
3. We can efficiently track and assign subsequences using two lists:

• zero → Stores subsequences ending in 0.
• one → Stores subsequences ending in 1.

• Iterate through the binary string:

• If 1 is encountered:
  • Assign it to a subsequence from zero (if available).
  • Otherwise, create a new subsequence.
• If 0 is encountered:
  • Assign it to a subsequence from one (if available).
  • Otherwise, create a new subsequence.
• The maximum number used in our subsequences is the answer.

Complexity:

• Each character is processed once and assigned in O(n) time.
• Given the constraints, this approach is efficient.

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 last 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())