Instead of thinking about “alternating every two steps”, define four explicit turns:
- Alice1 (current is Alice, next is also Alice)
- Alice2 (current is Alice, but next is Bob)
- Bob1 (current is Bob, next is also Bob)
- Bob2 (current is Bob, but next is Alice)

These repeat in a cycle.

If we encode these states as numbers:
- Alice1 = 0
- Alice2 = 1
- Bob1 = 2
- Bob2 = 3

Then after each step: turn = (turn + 1) % 4

This means if turn < 2, it is Alice's turn else it is Bob's turn.

We simulate distributing cards one by one.

We maintain:
- cards (how many cards will be given in this turn)
- cards_given (how many cards we’ve given in this turn)
- turn (whose turn it is (from 0 to 3))

We start from turn = 1 # Alice2

For each card:
- if it is Alice's turn, we increment Alice's card count by one
- if it is Bob's turn, we increment Bob's card count by one

When we finish a turn (cards_given == cards):
- Increase cards
- Reset cards_given
- Move to next turn with (turn + 1) % 4

Time Complexity: O(n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    alice = 0
    bob = 0
    
    cards = 1
    cards_given = 0
    turn = 1
    
    for _ in range(n):
        if turn < 2:
            alice += 1
        else:
            bob += 1
        
        cards_given += 1
        
        if cards_given == cards:
            cards += 1
            cards_given = 0
            turn = (turn + 1) % 4
    
    print(alice, bob)

In Approach 1, we distribute cards one by one.
Can we avoid iterating over every single card?

During a turn, the same player receives all cards cards.
So instead of incrementing one by one, we can directly add the whole amount at once.

At a given turn:
- The number of cards to give is cards.
- These cards all go to the same player in this turn.
- But if the remaining cards are fewer than cards, we give only the remaining cards and stop.

So instead of looping n times, we can:
- Give min(cards, remaining)
- Decrease remaining
- Move to the next turn

How many turns can there be?
Since: 1 + 2 + 3 + ... + k ≈ k² / 2
To reach n cards, k is approximately √(2n)

Time Complexity: O(√n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    alice = 0
    bob = 0
    
    cards = 1
    turn = 1
    remaining = n
    
    while remaining > 0:
        give = min(cards, remaining)
        
        if turn < 2:
            alice += give
        else:
            bob += give
        
        remaining -= give
        cards += 1
        turn = (turn + 1) % 4
    
    print(alice, bob)

A1 — Approach 1

The deck is:

W B W B W B W B ...

So:
- Position 1 → White
- Position 2 → Black
- Position 3 → White
- Position 4 → Black
- Position 5 → White ...

Notice a pattern? Odd positions are White and Even positions are Black.

We simulate distributing cards one by one.

We maintain:
- cards (how many cards will be given in this turn)
- cards_given (how many cards we’ve given in this turn)
- turn → (whose turn it is (from 0 to 3))

We start from turn = 1 # Alice2

For each card:
- if it is Alice's turn and if the current card position is odd, we increment Alice's White card count by one
- if it is Alice's turn and if the current card position is eve, we increment Alice's Black card Count by one
- if it is Bob's turn and if the current card position is odd, we increment Bob's White card count by one
- if it is Bob's turn and if the current card position is eve, we increment Bob's Black card Count by one

When we finish a turn (cards_given == cards):
- Increase cards
- Reset cards_given
- Move to next turn with (turn + 1) % 4

Time Complexity: O(n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    white_alice = 0
    black_alice = 0
    white_bob = 0
    black_bob = 0
    
    cards = 1
    cards_given = 0
    turn = 1
    
    for pos in range(1, n + 1):
        if turn < 2:
            if pos % 2 == 1:
                white_alice += 1
            else:
                black_alice += 1
        else:
            if pos % 2 == 1:
                white_bob += 1
            else:
                black_bob += 1
        
        cards_given += 1
        
        if cards_given == cards:
            cards += 1
            cards_given = 0
            turn = (turn + 1) % 4
    
    print(white_alice, black_alice, white_bob, black_bob)

A1 – Approach 2 and A2 – Approach 1

In A1 – Approach 2, instead of distributing cards one by one, we distribute an entire turn at once.

In A2 – Approach 1, we determined that:
- Odd positions → White
- Even positions → Black

Can we combine both ideas?

Suppose we are giving k consecutive cards starting from position pos.

We want to count how many of those k positions are even.

There are two cases:

Case 1: pos is even The sequence looks like: Even, Odd, Even, Odd, ...

In this case:
- Number of even positions = (k + 1) // 2
- Number of odd positions = k // 2

Case 2: pos is odd The sequence looks like: Odd, Even, Odd, Even, ...

In this case:
- Number of even positions = k // 2
- Number of odd positions = (k + 1) // 2

Since:
- Even positions → Black
- Odd positions → White

We can compute white and black cards in O(1).

We combine the optimized turn simulation from A1 – Approach 2 with the color counting observation.

We maintain:
- cards → size of current turn
- turn → from 0 to 3 (start from 1)
- remaining → cards left
- pos → starting position of current block (initially 1)

At each turn:
- Compute give = min(cards, remaining)
- Compute how many whites and blacks are inside this block
- Assign these counts to Alice's and Bob's White and Black cards count depending on turn
- Update the variables

Time Complexity: O(√n) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    
    white_alice = 0
    black_alice = 0
    white_bob = 0
    black_bob = 0
    
    cards = 1
    turn = 1
    remaining = n
    pos = 1
    
    while remaining > 0:
        give = min(cards, remaining)
        
        if pos % 2 == 1:
            white = (give + 1) // 2
            black = give // 2
        else:
            white = give // 2
            black = (give + 1) // 2
        
        if turn < 2:
            white_alice += white
            black_alice += black
        else:
            white_bob += white
            black_bob += black
        
        remaining -= give
        pos += give
        cards += 1
        turn = (turn + 1) % 4
    
    print(white_alice, black_alice, white_bob, black_bob)

If the final array is a permutation, then it must contain exactly:

1, 2, 3, ..., N for some integer N.

So every number starting from 1 must appear exactly once. This means its length is also N.

We already have some numbers in b. So the only numbers we can append are the numbers missing from the permutation.

Try iterating from 1 upward:
- If the number is already in b, skip it.
- Otherwise, subtract it from s (since it must be one of the lost numbers).

Stop when s ≤ 0.

We simulate constructing the permutation from 1 upward.

Convert b into a set for fast lookup.

Starting from x = 1, until s ≤ 0:
- If x is not in the set: Subtract x from s and Append x to b
- Increase x by 1

If s == 0 and b is a permutation, it is YES, otherwise it is NO.

Time complexity: O(m + √s) (Can you tell why?)

t = int(input())

for _ in range(t):
    m, s = map(int, input().split())
    b = list(map(int, input().split()))
    
    present = set(b)
    
    x = 1
    while s > 0:
        if x not in present:
            s -= x
            b.append(x)
        x += 1
    
    if s == 0 and len(b) == max(b):
        print("YES")
    else:
        print("NO")

If you type the string using only append, you need exactly n operations.

To use strictly less than n operations, you must use at least one copy-paste operation.

Copy-paste is useful only if some substring appears at least twice in the string, and the two occurrences do not overlap.

You type the first occurrence normally, then copy it to produce the second one.

To actually save operations, the copied substring must have length ≥ 2.

Copying a substring of length 1 costs the same as appending one character, so it gives no benefit.

If any substring of length ≥ 2 appears twice (non-overlapping), then its first two characters also form a substring of length 2 that appears twice (non-overlapping).

So it is enough to check only substrings of length 2.

We iterate over all substrings of length 2.

For each substring:
- Store its ending index in a dictionary. (to avoid overlapping similar substrings like 'aaa')
- When we see it again: If the current starting index is strictly greater than the previous ending index, it is YES.

If we didn't get any substring that was repeated correctly, the answer is NO.

t = int(input())

for _ in range(t):
    n = int(input())
    s = input()
    
    seen = {}  # substring -> ending index
    
    for i in range(n - 1):
        sub = s[i:i+2]
        
        if sub in seen:
            # previous ending index
            prev_end = seen[sub]
            
            # current starting index is i
            if i > prev_end:
                print("YES")
                break
        else:
            seen[sub] = i + 1  # store ending index
    
    else:
        print("NO")

If the grid must look the same after 0°, 90°, 180° and 270° rotations, then any cell must have the same value as all the cells it maps to under these rotations.

So instead of thinking about the whole grid at once, think in terms of rotation groups.

If a cell is at position (i, j), its rotated positions are:
- 0° → (i, j)
- 90° → (j, n — 1 — i)
- 180° → (n — 1 — i, n — 1 — j)
- 270° → (n — 1 — j, i)

So every cell belongs to a group of 4 symmetric cells.

All 4 cells in such a group must have the same value in the final grid.

If among those 4 cells:
- k cells contain '1'
- 4 − k cells contain '0'

Then to make them equal, we need: min(k, 4 − k) flips.

Each group of 4 cells would be counted 4 times if we iterate over the entire grid. So we need to divide the total number of flips by 4.

Cells with the same color and letter in these two matrices belong to the same rotation group — they map to each other under 90°, 180°, and 270° rotations and therefore must be equal.

We process each rotation group independently.

For every cell (i, j), We collect its 4 symmetric positions:
- (i, j)
- (j, n − 1 − i)
- (n − 1 − i, n − 1 − j)
- (n − 1 − j, i)

We count how many of these are '1'. If there are k ones, then we need min(k, 4 − k) operations to make them equal.

We sum this value for all groups.

Then we divide the total by 4 since we counted each group 4 times.

Time Complexity: O(n²) per test case.

t = int(input())

for _ in range(t):
    n = int(input())
    grid = [list(map(int, list(input().strip()))) for _ in range(n)]
    
    ans = 0
    
    for i in range(n):
        for j in range(n):
            ones = grid[i][j]
            ones += grid[j][n - 1 - i]
            ones += grid[n - 1 - j][i]
            ones += grid[n - 1 - i][n - 1 - j]
            
            ans += min(ones, 4 - ones)

    ans //= 4

    print(ans)

The carpet is divided into layers.

Each layer is a closed strip around the border of the remaining matrix.

So instead of checking the entire grid at once, process one layer at a time.

For each layer, traverse it clockwise starting from the top-left corner of that layer and build a string representing the digits in traversal order.

Be careful with the traversal order:
1. Top row (left → right)
2. Right column (top+1 → bottom-1)
3. Bottom row (right → left)
4. Left column (bottom-1 → top+1)

The layer is circular.

So after building the string s, append its first 3 characters to the end:

s += s[:3]

This allows detecting occurrences of "1543" that wrap around the end of the layer.

We process the carpet layer by layer.

Let i be the current layer index.

For each layer:
- Extract its boundary in clockwise order into a string s.
- Append the first 3 characters to s to simulate circular traversal.
- Count how many times "1543" appears using s.count("1543").
- Add to the total answer then move to the next inner layer.

We stop when: i < n // 2 (we reached half mark in height of carper) or i < m // 2 (we reached half mark in width of carpet)

Since both n and m are even, every layer is well-defined.

Time Complexity: O(n × m) per test case, because every cell belongs to exactly one layer and is visited once.

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    grid = [input() for _ in range(n)]
    
    ans = 0
    i = 0
    
    while i < n // 2 and i < m // 2:
        chars = []
        
        # top row
        for col in range(i, m - i):
            chars.append(grid[i][col])
        
        # right column
        for row in range(i + 1, n - i - 1):
            chars.append(grid[row][m - i - 1])
        
        # bottom row
        for col in range(m - i - 1, i - 1, -1):
            chars.append(grid[n - i - 1][col])
        
        # left column
        for row in range(n - i - 2, i, -1):
            chars.append(grid[row][i])
        
        s = "".join(chars)
        
        # circular handling
        s += s[:3]
        
        ans += s.count("1543")
        
        i += 1
    
    print(ans)