To determine whether a melody is perfect, we check each pair of consecutive notes in the sequence. For each pair $$$a_i, a_{i+1}$$$, we calculate the interval as $$$|a_i - a_{i+1}|$$$. We then verify whether this interval is one of the allowed values, 5 or 7. If all consecutive intervals satisfy this condition, the melody is perfect and the answer is "YES". Otherwise, if any interval is not 5 or 7, the melody is not perfect and the answer is "NO".

This method ensures that every adjacent pair is validated exactly once, giving a time complexity of $$$O(n)$$$ and a space complexity of $$$O(1)$$$.

n = int(input())
notes = list(map(int, input().split()))

perfect = True
for i in range(n - 1):
    interval = abs(notes[i] - notes[i + 1])
    if interval not in (5, 7):
        perfect = False
        break

print("YES" if perfect else "NO")

Operation:
- Pick $$$\min(a)$$$ and $$$\max(b)$$$.
- Swap if $$$\min(a) \lt \max(b)$$$.

Repeat:
- Perform up to $$$k$$$ times or until no improvement is possible.

Idea:
- Each swap increases the sum of $$$a$$$ (or decreases $$$b$$$) toward the objective.
- Always choose the best candidates (greedy strategy).

Complexity:
- Naive: $$$O(n \cdot k)$$$ → can be $$$O(n^3)$$$
- Optimized: Sort arrays, use pointers → $$$O(n \log n)$$$

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

    a.sort()
    b.sort(reverse=True)

    for i in range(min(k, n)):
        if a[i] < b[i]:
            a[i], b[i] = b[i], a[i]
        else:
            break

    print(sum(a))

We are given:

• An integer $$$n$$$ (divisible by $$$3$$$).

• An array $$$a_1, a_2, \dots, a_n$$$.

• In one move, we can pick an index $$$i$$$ $$$(1 \le i \le n)$$$ and replace $$$a_i$$$ with $$$a_i + 1$$$.

We define:

• $$$c_0$$$ = number of elements where $$$a_i \bmod 3 = 0$$$

• $$$c_1$$$ = number of elements where $$$a_i \bmod 3 = 1$$$

• $$$c_2$$$ = number of elements where $$$a_i \bmod 3 = 2$$$

The array is balanced if: $$$c_0 = c_1 = c_2$$$

Our task: Find the minimum number of moves to make the array balanced.

Key Observations

Target count for each group:
Since $$$n$$$ is divisible by 3, the balanced state means: $$$\text{target} = \frac{n}{3}$$$

Allowed move effect:

• If $$$a_i \bmod 3 = 0$$$, one increment moves it to remainder $$$1$$$.

• If $$$a_i \bmod 3 = 1$$$, one increment moves it to remainder $$$2$$$.

• If $$$a_i \bmod 3 = 2$$$, one increment moves it to remainder $$$0$$$.

This forms a cycle:$$$0 \to 1 \to 2 \to 0$$$

Excess and deficit handling:

• If $$$c_k \gt \text{target}$$$ for some $$$k$$$, we can move the excess elements to the next group $$$(k+1) \bmod 3$$$.

• Each such move costs 1 increment per element shifted.

Balancing Process

• Count $$$c_0$$$, $$$c_1$$$, $$$c_2$$$.

• While not all equal to target:

• For $$$i \in {0,1,2}$$$:

  • If $$$c_i \gt \text{target}$$$:
    1. $$$\text{excess} = c_i - \text{target}$$$
    2. Transfer $$$\text{excess}$$$ elements to group $$$(i+1) \bmod 3$$$
    3. Increase move counter by $$$\text{excess}$$$

• Stop when:$$$c_0 = c_1 = c_2 = \text{target}$$$

Example Walkthrough

Example:
$$$n = 6$$$, $$$a = [0, 2, 5, 5, 4, 8]$$$

• Initial remainders:

• Target: $$$\frac{6}{3} = 2$$$

Step 1: $$$c_2$$$ has excess $$$2$$$. Move them to $$$c_0$$$:

Step 2: $$$c_0$$$ has excess $$$1$$$. Move it to $$$c_1$$$:

Balanced in 3 moves.

test = int(input())
for _ in range(test):
    n = int(input())
    arr = list(map(int, input().split()))
    
    # Count remainders
    cnt = [0, 0, 0]
    for x in arr:
        cnt[x % 3] += 1
    
    target = n // 3
    moves = 0
    
    # Keep balancing
    while cnt[0] != target or cnt[1] != target or cnt[2] != target:
        for i in range(3):
            if cnt[i] > target:
                excess = cnt[i] - target
                cnt[i] -= excess
                cnt[(i + 1) % 3] += excess
                moves += excess
    
    print(moves)

We are given $$$n$$$ days of vacation.

• For each day, Vasya knows:

  1. Whether the gym is open.
  2. Whether there is a contest.

• On each day, Vasya can:

  • Rest
  • Write the contest (if available)
  • Go to the gym (if open)

Constraint:
He cannot do the same activity (contest or gym) on two consecutive days.

Goal:
Minimize the number of rest days.

Observation

This is a Dynamic Programming (DP) problem because:

• The decision for day $$$i$$$ depends on what was done on day $$$i-1$$$.

• There’s a constraint to avoid repeating the same activity consecutively.

State Definition

Let:

• $$$dp[i][0]$$$ → Minimum rest days till day $$$i$$$ if Vasya rests on day $$$i$$$.
• $$$dp[i][1]$$$ → Minimum rest days till day $$$i$$$ if Vasya participates in a contest on day $$$i$$$.
• $$$dp[i][2]$$$ → Minimum rest days till day $$$i$$$ if Vasya goes to the gym on day $$$i$$$.

Transition

1. Rest Case

• If Vasya rests on day $$$i$$$:

  • $$$dp[i][0] = 1 + \min(dp[i-1][0],\ dp[i-1][1],\ dp[i-1][2])$$$
  • Because resting adds 1 rest day to the minimum of all possible previous states.

2. Contest Case

• If there is a contest on day $$$i$$$ and he didn't do a contest yesterday:

  • $$$dp[i][1] = \min(dp[i-1][0],\ dp[i-1][2])$$$
  • We take the minimum rest days from rest yesterday or gym yesterday.
  • If no contest is available, $$$dp[i][1]$$$ is infinite (or invalid).

3. Gym Case

• If the gym is open on day $$$i$$$ and he didn’t go to the gym yesterday:

  • $$$dp[i][2] = \min(dp[i-1][0],\ dp[i-1][1])$$$
  • We take the minimum rest days from rest yesterday or contest yesterday.
  • If the gym is closed, $$$dp[i][2]$$$ is infinite (or invalid).

Initialization

• For day $$$1$$$:

  • If rest: $$$dp[1][0] = 1$$$
  • If contest possible: $$$dp[1][1] = 0$$$
  • If gym possible: $$$dp[1][2] = 0$$$
  • If both possible: choose based on availability.

Answer

The final answer is:$$$\min(dp[n][0],\ dp[n][1],\ dp[n][2])$$$

This gives the minimum number of rest days possible after $$$n$$$ days.

def solve():
    n = int(input().strip())
    days = list(map(int, input().strip().split()))
    
    INF = float('inf')
    # dp[i][0] → rest day
    # dp[i][1] → contest day
    # dp[i][2] → gym day
    dp = [[INF] * 3 for _ in range(n + 1)]
    
    # Base case (day 0 — no days taken yet)
    dp[0][0] = dp[0][1] = dp[0][2] = 0

    for i in range(1, n + 1):
        activity = days[i - 1]

        # rest day
        dp[i][0] = 1 + min(dp[i - 1])

        if activity in (1, 3):
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2])

        # didn't do gym yesterday
        if activity in (2, 3):
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1])

    print(min(dp[n]))


solve()

You are given an array $$$a = [a_1, a_2, \dots, a_n]$$$. In one operation, you can choose two distinct elements $$$a_i$$$ and $$$a_j$$$ ($$$i \neq j$$$) and decrease each of them by 1.

You need to determine whether it is possible to reduce all elements to zero.

Step 1: Understanding the Operation

• Each operation reduces the sum of all elements by 2: $$$\text{new sum} = \text{old sum} - 2$$$

• Therefore, if the sum of all elements is initially odd, we can never reach zero because subtracting 2 repeatedly will always leave an odd number.

Condition 1: $$$\sum_{i=1}^{n} a_i$$$ must be even.

Step 2: Considering the Largest Element

Let $$$M = \max(a_1, a_2, \dots, a_n)$$$ and $$$S_{\text{rest}} = \sum_{i=1}^{n} a_i - M$$$

• To reduce $$$M$$$ to zero, we need to pair it with other elements in each operation.
• If $$$M \gt S_{\text{rest}}$$$, there aren’t enough elements to pair with $$$M$$$ to bring it down to zero.

Condition 2: $$$M \le S_{\text{rest}} = \sum_{i=1}^{n} a_i - M$$$

Step 3: Proof of Sufficiency

If both conditions hold:

1. $$$\sum_{i=1}^{n} a_i$$$ is even.
2. $$$M \le \sum_{i=1}^{n} a_i - M$$$

Then we can always reduce all elements to zero using a greedy pairing strategy:

• Always pair the two largest remaining elements.
• Each operation decreases the sum by 2.
• Because the total sum is even, we can eventually reach a sum of zero.
• The largest element $$$M$$$ can always find a partner (since $$$M \le S_{\text{rest}}$$$).

This proves that both conditions are sufficient.

Step 4: Algorithm

1. Compute the sum of all elements:$$$\text{sum_a} = \sum_{i=1}^{n} a_i$$$

2. Find the maximum element: $$$M = \max(a_1, a_2, \dots, a_n)$$$

3. Check the two conditions: $$$\sum_{i=1}^{n} a_i \equiv 0 \pmod{2} \quad \text{and} \quad M \le \sum_{i=1}^{n} a_i - M$$$

   • If both are true → "YES"
   • Otherwise → "NO"

Step 5: Examples

• Example 1:[0, 0, 2, 2]

  • Sum: $$$\sum a_i = 1+1+2+2 = 6 \quad \text{(even)}$$$
  • Maximum element:$$$M = 2$$$

• Sum of others:$$$S_{\text{rest}} = 6 - 2 = 4 \quad (\text{and } M \le S_{\text{rest}})$$$

• Both conditions satisfied → YES

• Operations:

  1. Decrease $$$a_1$$$ and $$$a_2$$$: [0,0,2,2]
  2. Decrease $$$a_3$$$ and $$$a_4$$$: [0,0,1,1]
  3. Decrease $$$a_3$$$ and $$$a_4$$$: [0,0,0,0]

• Example 2:[1, 2, 3, 4, 5, 6]

  • Sum: $$$\sum a_i = 1+2+3+4+5+6 = 21 \quad \text{(odd)} $$$
  • Sum is odd → NO
  • Even if the sum were even, check $$$M$$$: $$$M = 6, \quad S_{\text{rest}} = 15 \quad (M \le S_{\text{rest}}) $$$

• Condition 1 fails → impossible to reach zero.

def solve(arr):
    total_sum = sum(arr)
    max_elem = max(arr)
    
    # First Condition 
    if total_sum % 2 != 0:
        return "NO"
    
    # Second Condition
    if max_elem > total_sum - max_elem:
        return "NO"
    
    return "YES"


n = int(input())
arr = list(map(int, input().split()))

print(solve(arr))

If you are not interested in competitive programming, this problem is not interview-friendly. You don’t have to solve or understand it, but if you do, it will be a plus for your problem-solving skills

Even if the approach is optimal, it is not accepted by Codeforces.

• You can either change the code to C++ or Java
• Or just understand it and analyze its time complexity

Note: I will update it as soon as I find a more optimal solution than this one.

The key idea is to flatten the tree into an array so that every subtree becomes a contiguous segment.
We run a DFS from the root 1 and record:

• Entry time tin[v] when a vertex v is first visited
• Exit time tout[v] after all its descendants are processed

If t is a global time incremented on entry, we define an order array ord[t] such that
ord[tin[v]] = v.

It is standard that the subtree of v corresponds exactly to the segment
[tin[v], tout[v]] in this DFS order (Euler tour).
Hence, every query “on the subtree of v” reduces to a range operation on [tin[v], tout[v]].

Color Representation as Bitmask

Each vertex color c ∈ {1, …, 60} is represented as a bitmask in a 64-bit integer:

mask(c) = 1 << (c - 1)

For the flattened array A of length n:

A[i] = mask(c_ord[i])

A segment’s set of colors is then the bitwise OR of its elements.
If a segment covers colors S, its mask is:

mask(S) = OR_{x ∈ S} mask(x)

The number of distinct colors is:

#colors = popcount(mask(S))

Segment Tree with Lazy Propagation

We build a segment tree over A with lazy propagation.

For each node x in the tree:

• M_x = bitwise OR of all A[i] for i in this node's segment
• L_x = lazy tag, initially unset (e.g., -1), meaning “no pending assignment.”
  If set, it holds a uniform mask meaning “paint this entire segment with this mask.”

Operations

1) Range Paint (Type 1)

Painting all vertices in the subtree of v with color c means assigning:

V = mask(c)

to the segment [tin[v], tout[v]].

For a fully covered segment:

• Set M_x = V
• Set L_x = V

For partial overlap:

• Push L_x down to children if needed
• Recurse into children

2) Range Query (Type 2)

Counting distinct colors in the subtree of v means:

Ans(v) = popcount(OR_query([tin[v], tout[v]]))

The segment tree merges results by bitwise OR:

res = M_left | M_right

Correctness

We maintain two invariants:

1. If L_x is unset, then M_x is the OR of the actual values in the segment.
2. If L_x is set, then the entire segment is painted with that mask.

Updates replace segments with a constant mask. Push operations ensure children remain consistent.
Because bitwise OR matches set union on these masks, the query result is correct,
and popcount returns the correct count of distinct colors.

Complexity

• Preprocessing (DFS): O(n)
• Range Paint: O(log n)
• Range Query: O(log n)

Total time: O((n + m) log n)
Space: O(n) for the tree and segment tree.

Summary:

1. Flatten the tree via DFS (tin, tout).
2. Store colors as 64-bit masks.
3. Maintain a segment tree with lazy range assignment and range OR queries.
4. Answer queries with popcount of the returned mask.

import sys
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

n, m = map(int, input().split())
colors = list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

# Euler Tour Flattening
tin = [0] * (n + 1)
tout = [0] * (n + 1)
order = [0] * (n + 1)
timer = 0

def dfs(u, p):
    global timer
    timer += 1
    tin[u] = timer
    order[timer] = u
    for v in adj[u]:
        if v != p:
            dfs(v, u)
    tout[u] = timer

dfs(1, -1)

size = 1
while size < n:
    size <<= 1

tree = [0] * (2 * size)
lazy = [-1] * (2 * size)

def build():
    for i in range(1, n + 1):
        node = order[i]
        tree[size + i - 1] = 1 << (colors[node - 1] - 1)
    for i in range(size - 1, 0, -1):
        tree[i] = tree[i * 2] | tree[i * 2 + 1]

def apply(node, value):
    tree[node] = value
    lazy[node] = value

def push(node):
    if lazy[node] != -1:
        apply(node * 2, lazy[node])
        apply(node * 2 + 1, lazy[node])
        lazy[node] = -1

def update(l, r, value, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return
    if l <= lx and rx <= r:
        apply(node, value)
        return
    push(node)
    mid = (lx + rx) // 2
    update(l, r, value, node * 2, lx, mid)
    update(l, r, value, node * 2 + 1, mid + 1, rx)
    tree[node] = tree[node * 2] | tree[node * 2 + 1]

def query(l, r, node=1, lx=1, rx=size):
    if r < lx or rx < l:
        return 0
    if l <= lx and rx <= r:
        return tree[node]
    push(node)
    mid = (lx + rx) // 2
    return query(l, r, node * 2, lx, mid) | query(l, r, node * 2 + 1, mid + 1, rx)

build()

for _ in range(m):
    q = list(map(int, input().split()))
    if q[0] == 1:
        v, c = q[1], q[2]
        update(tin[v], tout[v], 1 << (c - 1))
    else:
        v = q[1]
        res = query(tin[v], tout[v])
        print(res.bit_count())  # Python 3.10+