The Idea

Polycarp answers "Yes" by repeating it many times:

YesYesYesYesYes...

But you only hear a substring of that long string.

What You Need to Check

Given a string s, determine:

Is s a substring of the infinite string "YesYesYes..."?

Important Notes

• Case matters: "YES" is NOT the same as "Yes".
• The pattern strictly repeats "Yes".

• Build a long enough string like "YesYesYesYes...".
• Check if s exists inside it.
• Since |s| ≤ 50, repeating "Yes" about 20 times is enough.

Approach

Instead of dealing with an infinite string, we simulate it.

Step-by-step:

1. Create a long string: base = "YesYesYesYesYes..."
2. For each test case:

• Read string s
• Check if s is a substring of base

1. If yes, print "YES", otherwise print "NO"

Why This Works

Any valid substring of "YesYesYes..." must appear in a sufficiently long repetition.

Since: - Maximum |s| = 50 - "Yes" length = 3

Repeating "Yes" around 20 times (length = 60) is enough.

Common Mistakes

• Using "YES" instead of "Yes"
• Forgetting substring must be continuous
• Not repeating "Yes" enough times

```python

def solve(): t = int(input())

base = "Yes" * 20  # long enough for all cases

for _ in range(t):
    s = input().strip()

    print("YES" if s in base else "NO")

solve()

Complexity: Time: O(t × |s|) Space: O(1)

The Goal

We are given: - An integer array a of size n

Operation

You can: - Pick two indices i < j - Such that: — a[i] == a[j] — Both indices are not used before

Each such pair gives +1 score.

Task

Find the maximum score.

• Count how many times each number appears
• From each value, you can form:

count // 2 pairs

Approach

We need to maximize the number of valid pairs.

Key Observation

• Each pair needs 2 equal elements
• So for a value appearing k times:

number of pairs = k // 2

Step-by-Step Logic

1. Read n and array a
2. Count frequency of each number
3. For each frequency:

• Add count // 2 to score

1. Print total score

Example

Input: 6
1 2 3 1 2 3

Frequencies: 1 → 2
2 → 2
3 → 2

Pairs: 1 → 1 pair
2 → 1 pair
3 → 1 pair

Total = 3

Why this works

Each pair uses exactly 2 equal elements, and we cannot reuse indices.

Complexity

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

def solve():
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        
        freq = {}
        for x in arr:
            freq[x] = freq.get(x, 0) + 1
        
        score = 0
        for count in freq.values():
            score += count // 2
        
        print(score)
 
 
solve()

The Goal

We are given: - An array a of size n - An integer x

Task

Select exactly x elements such that: - Their sum is odd

Key Observation

• Sum is odd ⇔ number of odd elements selected is odd
• Even numbers do not change parity of the sum

Count how many odd and even numbers exist.

Try to pick an odd count of odd numbers (at least 1), and fill the rest with even numbers.

Let: - o = number of odd elements
- e = number of even elements

You need to pick k odd numbers such that: - k is odd
- 0 ≤ k ≤ o
- x - k ≤ e

Check if such k exists.

Approach

We only care about parity, not actual values.

Step-by-step:

1. Count:

• o = number of odd elements
• e = number of even elements

1. We want to pick x elements with odd sum
2. That means:

• pick an odd number of odd elements (k)
• remaining (x - k) must be even elements

1. Compute:

• l = max(1, x - e) → minimum odd elements needed
• r = min(x, o) → maximum odd elements possible

1. Check if there exists an odd k in [l, r]

Why this works

• Odd + Odd = Even
• Even + Even = Even
• Odd + Even = Odd

So we must ensure an odd count of odd numbers is selected.

Example

Input: n = 3, x = 3
a = [101, 102, 103]

Odds = 2, Evens = 1

We must pick all 3: - Odd count = 2 → even sum → not valid

Answer: No

Complexity

• Time: O(n) per test case
• Space: O(1)

t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    
    # count odd and even numbers
    o = sum(1 for v in a if v % 2)
    e = n - o
    
    # possible range of odd numbers we can take
    l = max(1, x - e)
    r = min(x, o)
    
    # check if there exists an odd number in [l, r]
    print("Yes" if l <= r and (l % 2 == 1 or r > l) else "No")

The Goal

We are given: - A string s consisting of '.' and '#' - m queries, each with (l, r)

Task

For each query, count how many indices i satisfy: - l ≤ i < r - s[i] == s[i+1]

In other words, count how many adjacent equal characters exist in the range.

Directly checking each query will be too slow.

Precompute results using a prefix sum array.

Build an array where: - pref[i] = number of positions j ≤ i such that s[j] == s[j-1]

Then each query becomes: - pref[r-1] - pref[l-1]

Approach

We preprocess the string to answer queries in constant time.

Step-by-step:

1. Create a prefix array pref
2. For each position i:

• If s[i] == s[i-1], increment count

1. Store cumulative counts in pref
2. For each query (l, r):

• Answer = pref[r-1] - pref[l-1]

Why this works

• pref[i] stores how many equal adjacent pairs exist up to index i
• Subtracting gives count within a range

Example

s = "......"

Pairs: (1,2), (2,3), (3,4), (4,5), (5,6) → all equal

So prefix: [0,1,2,3,4,5]

Query (1,6): Answer = pref[5] — pref[0] = 5

Complexity

• Preprocessing: O(n)
• Each query: O(1)
• Total: O(n + m)
• Space: O(n)

s = input().strip()
n = len(s)

# build prefix array
pref = [0] * n
for i in range(1, n):
    pref[i] = pref[i-1] + (1 if s[i] == s[i-1] else 0)

m = int(input())
res = []

for _ in range(m):
    l, r = map(int, input().split())
    
    # convert to 0-based and use prefix sum
    res.append(str(pref[r-1] - pref[l-1]))

print('\n'.join(res))

The Goal

We are given: - n ranges [l, r] (recipes) - A threshold k - q queries [a, b]

Task

A temperature is admissible if: - It is covered by at least k ranges

For each query [a, b], count how many admissible temperatures exist in that range.

Use a difference array to efficiently count how many ranges cover each temperature.

Convert the coverage into a prefix sum array.

Build another prefix array where: - pref[i] = number of admissible temperatures ≤ i

Then each query becomes: - pref[b] - pref[a-1]

Approach

We solve this in three steps.

Step 1: Range Frequency using Difference Array

• For each range [l, r]:
• diff[l] += 1
• diff[r+1] -= 1

Then compute prefix sum to get: - cnt[i] = how many ranges include temperature i

Step 2: Mark Admissible Temperatures

• If cnt[i] ≥ k, then temperature i is valid
• Build a prefix array:
• pref[i] = number of admissible temperatures up to i

Step 3: Answer Queries

For each query [a, b]: - Answer = pref[b] - pref[a-1]

Why this works

• Difference array handles range updates in O(1)
• Prefix sum converts it into actual frequencies
• Another prefix sum enables fast queries

Complexity

• Building arrays: O(MAX)
• Each query: O(1)
• Total: O(n + q + MAX)
• Space: O(MAX)

(MAX ≈ 200000)

n, k, q = map(int, input().split())

MAX = 200005

# difference array
diff = [0] * MAX
for _ in range(n):
    l, r = map(int, input().split())
    diff[l] += 1
    diff[r + 1] -= 1

# build coverage count
cnt = [0] * MAX
for i in range(1, MAX):
    cnt[i] = cnt[i-1] + diff[i]

# build admissible prefix
pref = [0] * MAX
for i in range(1, MAX):
    pref[i] = pref[i-1] + (1 if cnt[i] >= k else 0)

# answer queries
for _ in range(q):
    a, b = map(int, input().split())
    print(pref[b] - pref[a-1])

The Goal

We are given n magnets, each represented as:

• "10" → minus-plus
• "01" → plus-minus

Magnets are placed one after another in a row.

Key Idea

• If two adjacent magnets are the same → they stick together → same group
• If they are different → they repel → new group

What is a Group?

A group is formed when magnets are connected (same pattern continues).

So we need to count the number of times the pattern changes.

Input Constraints

• Start with 1 group (because at least one magnet exists).
• Compare each magnet with the previous one.
• Every time they are different, increase the group count.

Since the constraints are large (n up to 100000), we need an efficient approach. Fortunately, we only need a single pass through the magnets.

Step-by-Step Logic

1. Initialize: We start with groups = 1 since at least one magnet forms a group.
2. Traverse: Loop through the magnets starting from the second one.
3. Compare: For each magnet, compare it with the previous one.
   if magnets[i] != magnets[i — 1]
4. Update: If they are different, increment groups by 1.
5. Result: After processing all magnets, groups is the answer.

Why this works

Each time the pattern changes: "10" → "01" OR "01" → "10"
a new group is formed.

Example Walkthrough

Input: 4
01
01
10
10

Process: Start → groups = 1
01 → 01 → same
01 → 10 → different → groups = 2
10 → 10 → same

Final Answer = 2

Common Mistake

Forgetting to initialize groups = 1.
If you start from 0, your answer will always be wrong.

n = int(input())

magnets = [input().strip() for _ in range(n)]

groups = 1

for i in range(1, n):
    if magnets[i] != magnets[i - 1]:
        groups += 1

print(groups)

Optimized Version

n = int(input())

prev = input().strip()
groups = 1

for _ in range(n - 1):
    curr = input().strip()
    if curr != prev:
        groups += 1
    prev = curr

print(groups)

Complexity:

• Time: O(n)
• Space: O(n) (or O(1) optimized)

The Goal

We are given: - Number of games n - A string s of length n

Each character represents the winner: - 'A' → Anton wins
- 'D' → Danik wins

Task

• Count how many times Anton wins
• Count how many times Danik wins

Then: - If Anton > Danik → print "Anton"
- If Danik > Anton → print "Danik"
- If equal → print "Friendship"

• Just count characters in the string
• You can use:
• a loop
• or built-in count()

This problem is straightforward.

Step-by-Step Logic

1. Read integer n
2. Read string s
3. Count:

• number of 'A'
• number of 'D'

1. Compare the counts:

• If A > D → Anton wins
• If D > A → Danik wins
• Else → Friendship

Example

Input: 6
ADAAAA

Count: A = 5
D = 1

Answer: Anton

Why this works

We only need to compare frequencies of characters.

Complexity

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

n = int(input())
s = input().strip()

anton = s.count('A')
danik = s.count('D')

if anton > danik:
    print("Anton")
elif danik > anton:
    print("Danik")
else:
    print("Friendship")

The Goal

We are given a binary string s of length n.

We can perform exactly one operation: - Choose a segment [l, r] - Flip all bits in that segment: — '0' → '1' — '1' → '0'

Task

Determine if it is possible to make the string a palindrome after exactly one inversion.

Key Observation

A palindrome means: s[i] == s[n — i — 1]

So we only care about mismatched pairs.

Use two pointers: - l = 0 - r = n — 1

Compare characters while moving inward.

Count positions where: s[l] != s[r]

These are mismatches we must fix.

• If mismatches are continuous → one segment can fix them ✅
• If mismatches are separated → impossible ❌

Step-by-Step Logic

1. Use two pointers: l = 0, r = n — 1

2. Move inward and store mismatch indices

3. If no mismatches: Already palindrome → still possible (flip whole or middle)

4. Otherwise: Let: L = first mismatch
   R = last mismatch

5. Flip the segment covering mismatches and check if it becomes palindrome

Why this works

Flipping one segment can only fix mismatches if they are inside one continuous range.

Example

Input: 10010

Mismatches occur in a continuous segment → can fix → Yes

Complexity

Time: O(n)
Space: O(1)

def solve():
    t = int(input())
    
    for _ in range(t):
        n = int(input())
        s = input().strip()
        
        l, r = 0, n - 1
        
        # 1. Skip matching pairs from the outside
        while l < r and s[l] == s[r]:
            l += 1
            r -= 1
            
        # Already a palindrome
        if l >= r:
            print("Yes")
            continue
            
        # 2. Skip all consecutive mismatched pairs
        while l < r and s[l] != s[r]:
            l += 1
            r -= 1
            
        # 3. Remaining pairs must all match
        while l < r and s[l] == s[r]:
            l += 1
            r -= 1
            
        # If we met/crossed in the middle, mismatches were contiguous → valid
        print("Yes" if l >= r else "No")

if __name__ == "__main__":
    solve()

The Goal

We are given n products with prices and k discount vouchers. Each voucher b[j] allows us to buy b[j] products, but we only pay for the b[j] - 1 most expensive ones (the cheapest in the group is free).

Task

Minimize the total cost to buy all n products using the vouchers optimally.

Key Observation

To maximize savings, we want the cheapest possible items to be free. By grouping expensive items together, the "free" item in each group will be as cheap as possible relative to that block, saving us the most money.

Sort the prices in ascending order and the vouchers in ascending order.

Process vouchers from smallest to largest, applying them to the most expensive remaining items (right end of the array).

Use a pointer right starting at n-1. For each voucher v, the free item is at index right - v + 1. Subtract it from the total cost and move right left by v.

Step-by-Step Logic

1. Sort prices a ascending, vouchers b ascending
2. Start with total = sum(a)
3. Initialize right = n - 1 (most expensive item)
4. For each voucher v in b:

• Check if enough items remain: right - v + 1 >= 0
• The item at a[right - v + 1] is the cheapest in the current group → make it free
• total -= a[right - v + 1]
• right -= v

1. Print the minimized total cost

Why this works

Sorting ensures we always pick the optimal group boundaries. Applying vouchers from the expensive end guarantees that the free item in each group is the smallest possible within that block, maximizing overall savings.

Example

Input: a = [2, 3, 7, 9, 18], b = [1, 1, 3] - Voucher 1: covers [18] → free: 18 - Voucher 1: covers [9] → free: 9 - Voucher 3: covers [2, 3, 7] → free: 2 Total saved: 18 + 9 + 2 = 29 → Pay: 3 + 7 = 10

Complexity

Time: O(n log n + k log k)
Space: O(1) extra

def solve():
    t = int(input())

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

        a.sort()  # sort prices ascending
        b.sort()  # sort vouchers ascending

        total = sum(a)
        right = n - 1  # pointer at most expensive item

        for voucher in b:
            # check if group fits in remaining items
            if right - voucher + 1 < 0:
                break
            # cheapest item in current group becomes free
            total -= a[right - voucher + 1]
            right -= voucher  # move pointer left

        print(total)

if __name__ == "__main__":
    solve()

The Goal

We are given a string s formed after pressing keys on a keyboard.

Each key behaves in one of two ways: - Working → prints 1 character - Broken → prints 2 characters

Task

Determine which characters are guaranteed to be from working keys.

Key Observation

• Working key → produces odd-length groups (1, 3, 5, …)
• Broken key → produces even-length groups (2, 4, …)

If a character appears in any odd-length group, it must be working.

Use two pointers i and j to group consecutive identical characters.

For each group, compute its length using j - i.

If the group length is odd, mark that character as working.

Step-by-Step Logic

1. Read integer t (number of test cases).
2. For each string s:

• Initialize empty set good.
• Traverse using pointer i.

1. For each position:

• Set j = i.
• Move j forward while characters are the same.
• Compute group length = j - i.
• If length is odd, add character to good.

1. Move i = j and continue.
2. Output sorted characters in good.

Why this works

Each key behaves consistently: - Working → always contributes 1 character - Broken → always contributes 2 characters

Thus, only odd-length segments prove a key is working.

Example

Input: cbddbb

Groups: - c → length 1 - b → length 1 - dd → length 2 - bb → length 2

Output: bc

Complexity

Time: O(n)
Space: O(1)

def solve():
    t = int(input())
    
    for _ in range(t):
        s = input().strip()
        good = set()
        i = 0
        n = len(s)
        
        while i < n:
            j = i
            
            while j < n and s[j] == s[i]:
                j += 1
            
            if (j - i) % 2 == 1:
                good.add(s[i])
            
            i = j
        
        print(''.join(sorted(good)))

if __name__ == "__main__":
    solve()

The Goal

We are given a binary array a of length n and an integer k. We can flip at most k zeros to ones.

Task

Maximize the length of the longest consecutive subsegment consisting only of ones after the flips. Output the maximum length and the final modified array.

Key Observation

Finding the longest subsegment of ones with at most k flips is equivalent to finding the longest subarray that contains at most k zeros. Flipping those zeros turns the entire window into ones.

Use two pointers left and right to maintain a sliding window.

Expand right to include elements. Keep a counter of zeros inside the current window.

If zeros exceed k, shrink the window from left until the constraint is satisfied. Track the boundaries of the longest valid window found.

Step-by-Step Logic

1. Initialize left = 0, zeros = 0, and variables to store the best window (best_len, best_l, best_r)
2. Iterate right from 0 to n-1:

• If a[right] is 0, increment zeros
• While zeros > k, shrink from left: decrement zeros if a[left] is 0, then increment left
• If current window length > best_len, update best boundaries

1. After scanning, flip all elements in a[best_l...best_r] to 1
2. Print best_len and the modified array

Why this works

The sliding window guarantees that every considered subarray satisfies the ≤ k zeros constraint. Since both pointers only move forward, we evaluate all optimal candidates in linear time. The longest valid window directly corresponds to the maximum possible consecutive ones.

Example

Input: a = [1, 0, 0, 1, 1, 0, 1], k = 1
- Window expands until it contains 2 zeros → shrink left until valid
- Longest valid window found: indices 3..6 → [1, 1, 0, 1] (length 4, 1 zero)
- Flip zero at index 5 → array becomes 1 0 0 1 1 1 1

Complexity

Time: O(n)
Space: O(1) extra

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    left = 0
    zeros = 0
    best_len = 0
    best_l = 0
    best_r = -1
    
    for right in range(n):
        # expand window: count zeros
        if a[right] == 0:
            zeros += 1
        
        # shrink window if zeros exceed k
        while zeros > k:
            if a[left] == 0:
                zeros -= 1
            left += 1
        
        # update best window found so far
        if right - left + 1 > best_len:
            best_len = right - left + 1
            best_l = left
            best_r = right
    
    # flip zeros in the best window to ones
    for i in range(best_l, best_r + 1):
        a[i] = 1
    
    print(best_len)
    print(' '.join(map(str, a)))

if __name__ == "__main__":
    solve()