[Here](https://codeforces.me/contests/671638) is the contest link.↵
↵
### [A1. Non-alternating Deck (easy version)](https://codeforces.me/gym/671638/problem/A1)↵
↵
#### Approach 1↵
↵
<spoiler summary="Hint 1.1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 1.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
#### Approach 2↵
↵
<spoiler summary="Hint 2.1">↵
In Approach 1, we distribute cards one by one. ↵
Can we avoid iterating over every single card?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [A2. Alternating Deck (hard version)](https://codeforces.me/gym/671638/problem/A2)↵
↵
#### Approach 1↵
↵
<spoiler summary="Hint 1.1">↵
A1 — Approach 1↵
</spoiler>↵
↵
<spoiler summary="Hint 1.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### Approach 2↵
↵
<spoiler summary="Hint 2.1">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
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).↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [B. Lost Permutation](https://codeforces.me/gym/671638/problem/B)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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?)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [C. Notepad#](https://codeforces.me/gym/671638/problem/C)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [D. Mirror Grid](https://codeforces.me/gym/671638/problem/D)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
  ↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [E. I Love 1543](https://codeforces.me/gym/671638/problem/E)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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) ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [A1. Non-alternating Deck (easy version)](https://codeforces.me/gym/671638/problem/A1)↵
↵
#### Approach 1↵
↵
<spoiler summary="Hint 1.1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 1.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
#### Approach 2↵
↵
<spoiler summary="Hint 2.1">↵
In Approach 1, we distribute cards one by one. ↵
Can we avoid iterating over every single card?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [A2. Alternating Deck (hard version)](https://codeforces.me/gym/671638/problem/A2)↵
↵
#### Approach 1↵
↵
<spoiler summary="Hint 1.1">↵
A1 — Approach 1↵
</spoiler>↵
↵
<spoiler summary="Hint 1.2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 1">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
#### Approach 2↵
↵
<spoiler summary="Hint 2.1">↵
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?↵
</spoiler>↵
↵
<spoiler summary="Hint 2.2">↵
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).↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code 2">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [B. Lost Permutation](https://codeforces.me/gym/671638/problem/B)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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?)↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
### [C. Notepad#](https://codeforces.me/gym/671638/problem/C)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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")↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [D. Mirror Grid](https://codeforces.me/gym/671638/problem/D)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
  ↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
### [E. I Love 1543](https://codeforces.me/gym/671638/problem/E)↵
↵
<spoiler summary="Hint 1">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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) ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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)↵
~~~~~↵
↵
↵
</spoiler>↵
↵
