The problem requires us to find the n-th digit in an infinite sequence formed by concatenating all positive integers starting from 1.

Observations:

1. The sequence starts as: 123456789101112131415..., and we need to determine the digit at position (n).

2. A simple way to construct the sequence is to append numbers as strings until we reach the required length.

   Approach:

• Initialize an empty string sequence.
• Iterate from 1 onwards, converting each number to a string and appending it to sequence.
• Stop when sequence reaches at least n characters.

• Print the n-th digit (adjusting for 0-based indexing).

  Complexity Analysis:

  Since numbers grow in length, the loop runs approximately O(sqrt{n}) times, making the approach efficient.

n = int(input())
sequence = ""
for num in range(1, 1000):
    sequence += str(num)
    if len(sequence) >= n:  # You can stop early when sequence is long enough
        break
print(sequence[n - 1])

Anansi needs to arrange 2n A2SVians into two rows: - Front row: Shorter individuals. - Back row: Taller individuals.

Each person in the back row must be at least x units taller than the corresponding person in the front row.

We need to determine if this arrangement is possible for each test case.

Hint 1
How can sorting help in organizing the two rows optimally?

Hint 2
Try to place the smallest n people in the front row and the largest n people in the back row.

Hint 3
After sorting, check if every person in the back row is at least x units taller than their corresponding person in the front row.

Approach

1. Sorting for optimal arrangement

• To maximize our chances of meeting the height requirement, we sort the heights in non-decreasing order.
• Assign:
  • Front row: First n elements.
  • Back row: Last n elements.

1. Checking the Condition

• Ensure that for every j: [ \text{back}[j] — \text{front}[j] \geq x ]
• If all pairs satisfy the condition, print "YES", otherwise print "NO".

# Input handling
t = int(input())  # Number of test cases
for _ in range(t):
    n, x = map(int, input().split())  # Read n and x
    heights = list(map(int, input().split()))  # Read 2n heights

    heights.sort()  # Step 1: Sort the heights
    front_row = heights[:n]  # Step 2: First n people go to the front row
    back_row = heights[n:]   # Step 3: Last n people go to the back row

    # Step 4: Check if each person in the back row is at least x units taller
    for j in range(n):
        if back_row[j] - front_row[j] < x:
            print("NO")
	break
    else:
print("YES")

Time Complexity

1. Sorting the array: (O(2n \log (2n)) = O(n \log n))
2. Splitting into front and back rows: (O(n))
3. Checking the height condition: (O(n))

Total Time Complexity:
[ O(n \log n) + O(n) + O(n) = O(n \log n) ] which is efficient for ( n \leq 100 ).

Space Complexity

1. Input storage: (O(2n)) for storing heights.
2. Two separate lists: (O(n)) each for front and back row.
3. Overall auxiliary space: (O(n))

Since sorting is done in-place, Total Space Complexity = O(n).

To solve this problem efficiently, consider how the shows are distributed over the days and how you can dynamically track the number of unique shows in each window of consecutive days.

The problem asks us to determine the minimum number of TV show subscriptions needed to ensure that we can watch at least d consecutive days without missing any episodes. The key is to use a sliding window approach to efficiently count the number of unique shows in each window of d consecutive days.

• Sliding Window: We first initialize a window with the first d shows and count how many unique shows are in that window using a hash table (Counter). Then, as the window slides forward by one day, we update the count of unique shows by adding the new day’s show and removing the show that is no longer in the window.
• Efficiency: Instead of recalculating the number of unique shows for every possible window from scratch, we only adjust the window by removing one show and adding another, making the solution efficient.

We start by counting the unique shows in the first d days. As the window slides through the entire schedule, we keep track of the minimum number of unique shows across all windows of length d. This minimum gives us the answer.

from collections import Counter, defaultdict, deque
t = int(input())  # Number of test cases
for _ in range(t):
    n, k, d = map(int, input().split())  # Read values for n, k, d
    arr = list(map(int, input().split()))  # Read the show schedule
    window = Counter(arr[:d])  # Initialize window with first 'd' shows
    ans = len(window)  # Track minimum unique shows
    
    for i in range(d, n):  # Slide the window through the array
        window[arr[i]] += 1  # Add new show to window
        window[arr[i - d]] -= 1  # Remove old show from window
        
        if window[arr[i - d]] == 0:  # Remove show from counter if it no longer exists in window
            del window[arr[i - d]]
        
        ans = min(ans, len(window))  # Update the minimum unique shows
    
    print(ans)  # Output the result for the test case

Let's prove that next greedy solution works: each step we will find prefixes of minimal length of arrays $$$A$$$ and $$$B$$$ such that its sums are equal and we will cut them forming next block. If we will get valid partition in result so it is an optimal solution, otherwise there is no solution. Since length of prefix proportional to its sum, so prefixes are minimal since its sums are minimal.

Let's prove this algorithm: let optimal solution have alternative partition. Since our solution cuts minimal possible prefixes, so (at some step) optimal solution cuts prefix with greater sum (and greater length). But this prefixes in optimal solutions contain smaller prefixes, found by greedy solution, so it can be divided on two parts — contradiction.

So we can keep prefixes and increase one which have smaller sum.

Time complexity: $$$O(n)$$$.

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
m = int(sys.stdin.readline().strip())
b = list(map(int, sys.stdin.readline().strip().split()))

if sum(a) != sum(b):
    print(-1)
    exit()

p1, p2 =0, 0

cur_sum1, cur_sum2 = 0, 0

ans = 0

while p1 < n:
    
    cur_sum1 += a[p1]
    cur_sum2 += b[p2]
    p1 += 1
    p2 += 1

    while cur_sum1 != cur_sum2:
        if cur_sum1 < cur_sum2:
            cur_sum1 += a[p1]
            p1 += 1
        else:
            cur_sum2 += b[p2]
            p2 += 1
    ans += 1
print(ans)

We need to find the number of subarrays containing exactly ( k ) ones. This can be done by calculating the number of subarrays with at most ( k ) ones and subtracting the number of subarrays with at most ( k-1 ) ones:
[ \text{Result} = \text{atmostk}(k) — \text{atmostk}(k-1) ]

The function atmostk(k) calculates the number of subarrays containing at most ( k ) ones using a sliding window approach: - Two pointers (left and right) are used to maintain a window. - Expand the window by moving right. If a '1' is encountered, increment the count. - If count exceeds ( k ), move left until count is within the limit. - For each position of right, add right - left + 1 to the answer, as this is the number of subarrays ending at right.

This approach works in ( O(n) ) time complexity because each pointer moves at most ( n ) times.

k = int(input())
nums = input()
n = len(nums)

def atmostk(k):
    if k == -1:
        return 0
    
    left = 0 
    count = 0
    ans = 0

    for right in range(n):
        if nums[right] == "1":
            count += 1

        while count > k:
            if nums[left] == "1":
                count -= 1
            left += 1 
            
        ans += right - left + 1
    
    return ans 

print(atmostk(k) - atmostk(k-1))

Another approach is to use the Subarray Sum Equals K method, which utilizes prefix sums and a hash map to efficiently count subarrays with exactly ( k ) ones.
- Maintain a running sum (summ) of elements as we traverse the array. - Use a hash map (count) to store the frequency of each prefix sum. - If the difference between the current sum and ( k ) has been seen before, then all subarrays ending at the current index with that prefix sum difference contribute to the answer. - This works because the subarray sum equals ( k ) when the difference between the current sum and a previously seen sum is exactly ( k ).

This solution also works in ( O(n) ) time complexity due to the single pass over the array and ( O(n) ) space complexity for the hash map.

from collections import defaultdict

k = int(input())
nums = list(map(int, list(input())))

count = defaultdict(int)
ans = 0
summ = 0
count[0] = 1 
for val in nums:
    summ += val 
    ans += count[summ-k]
    count[summ] += 1 

print(ans)