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: back[j] - front[j] ≥ 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 <= 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 initialize two pointers $$$l$$$ and $$$r$$$ at the beginning and at the end of the given string $$$s$$$. We will move $$$l$$$ to the right and $$$r$$$ to the left is $$$s[l]$$$ == $$$s[r]$$$. If $$$l$$$ and $$$r$$$ become equal or move past each other at some point, that means the given string is a palindrome and we don’t need to delete any character. Our answer in this case would be $$$0$$$.

If that is not the case then $$$s[l]$$$ != $$$s[r]$$$ at some point. Since we are only allowed to delete one character, to make $$$s$$$ a palindrome, one of these characters must be deleted. We try deleting each character separately and we will take the alternative that requires minimum deletion. If it’s not possible to make $$$s$$$ a palindrome in both cases, we will print $$$-1$$$.

So, the first time $$$s[l]$$$ becomes different from $$$s[r]$$$, let’s say deleting the character $$$c$$$ = $$$s[l]$$$ is our first option. We will have a variable $$$deleted$$$ to count the number of characters we will delete to try to make $$$s$$$ a palindrome. So every time $$$s[l]$$$ is not equal to $$$s[r]$$$, if either of them are equal to $$$c$$$, we can increment $$$deleted$$$ by one and move the pointer that’s pointing at a character that is equal to $$$c$$$. If $$$l$$$ becomes greater or equal to $$$r$$$, that means by deleting $$$deleted$$$ number of character $$$c$$$, we successfully made $$$s$$$ a palindrome. We do the same for the other case, $$$c$$$ = $$$s[r]$$$ as well, and print the option that requires minimum deletions. We have three cases

• $$$case 1:$$$ if it is not possible to make $$$s$$$ a palindrome in both of our options, we print $$$-1$$$.
• $$$case 2:$$$ if it is not possible to make $$$s$$$ a palindrome in one of the options, and possible in the other by deleting $$$deleted$$$ number of characters, we print $$$deleted$$$.
• $$$case 3:$$$ if it is possible to make $$$s$$$ a palindrome in both of our options, our answer will be the option that requires the minimum deletions.

• $$$\text{Time Complexity: } O( n)$$$
• $$$\text{Space Complexity: } O(1)$$$

def count_deletions(c):
    l, r = 0, n - 1
    deleted = 0
    while l < r:
        if melodies[l] != melodies[r]:
            if melodies[l] == c:
                deleted += 1
                l += 1
            elif melodies[r] == c:
                deleted += 1
                r -= 1
            else: # It's impossible to make 'melodies' a palindrome by deleting c
                return float('inf')
        else:
            l += 1
            r -= 1
    
    return deleted

t = int(input())
for _ in range(t):
    n = int(input())
    melodies = input()

    is_palindrome = True
    l, r = 0, n - 1
    while l < r:
        if melodies[l] != melodies[r]:
            is_palindrome = False
            break
        l += 1
        r -= 1
    
    if is_palindrome: #the given string is already a palindrome
        print(0)
    else:
        deleted1 = count_deletions(melodies[l])
        deleted2 = count_deletions(melodies[r])

        ans = min(deleted1, deleted2)

        print(ans if ans != float('inf') else -1)

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)

Consider how to count subarrays with at most ( k ) ones efficiently. Think about using a sliding window to maintain the number of ones.

To find exactly ( k ) ones, calculate subarrays with at most ( k ) ones and subtract those with at most ( k-1 ) ones.

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: Result = atmostk(k) — 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

    # Expand window with right pointer
    for right in range(n):
        if nums[right] == "1":
            count += 1  # Count the 1s in the window

        # If count exceeds k, shrink window from the left
        while count > k:
            if nums[left] == "1":
                count -= 1  # Remove 1 from count
            left += 1 
        
        # Number of subarrays ending at right is (right - left + 1)
        ans += right - left + 1
    
    return ans 

# Subarrays with exactly k ones = atmostk(k) - atmostk(k-1)
print(atmostk(k) - atmostk(k-1)) 

Try using prefix sums to keep track of the number of ones encountered so far.

Assume you are currently at the right end of a subarray.
To find subarrays that sum to exactly ( k ), think about which prefix sum should be removed.
The required prefix to remove is ( current_sum — k ), since removing this would leave a subarray with a sum of ( k ).

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)  # Dictionary to store frequency of prefix sums
ans = 0
summ = 0
count[0] = 1  # To handle the case when subarray starts from index 0

for val in nums:
    summ += val  # Calculate prefix sum
    
    # Check how many subarrays end at current index and sum to k
    ans += count[summ-k]
    
    # Update the frequency of the current prefix sum
    count[summ] += 1 

print(ans)