FOCUS-ASTU-TECH-COMMUNITY-CONTEST-3

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])