CF 104076E - Identical Parity

Rating: -
Tags: -
Solve time: 56s
Verified: yes

Solution

Problem Understanding

We are given a permutation of numbers from 1 to n and a fixed segment length k. For every contiguous block of length k inside the permutation, we compute its sum. The requirement is that all these window sums must have identical parity, meaning every such sum is either always even or always odd.

The task is not to construct the permutation but only to decide whether at least one valid permutation exists for each test case.

The constraints are extremely large, with n and k up to 10^9 and up to 10^5 test cases. Any solution that tries to simulate permutations or inspect windows explicitly is immediately impossible. Even a linear scan per test case would already be too slow, so the answer must come from a direct structural condition on n and k.

A subtle edge case appears when k equals 1. Each window then consists of a single element, so the condition forces all values in the permutation to share the same parity. Since a permutation of 1 to n always contains both odd and even numbers when n ≥ 2, this is impossible. For example, with n = 3 and k = 1, any permutation like [1, 2, 3] produces window sums 1, 2, 3, which do not share parity, so the correct answer is No. When n = 1 and k = 1, there is only one window, so the condition is trivially satisfied and the answer is Yes.

Another potential pitfall is assuming that large k always makes the condition easier. For instance, when k = n, there is only one window, so the condition always holds regardless of the permutation.

Approaches

The brute-force perspective starts by choosing a permutation and checking all subarrays of length k. For each test case, this would involve computing n − k + 1 window sums, each taking O(k) time unless prefix sums are used. Even with prefix sums, each test still costs O(n) time, which is impossible when n can reach 10^9.

The key simplification comes from comparing adjacent windows. Let S_i be the sum of the subarray starting at position i. Then the difference between consecutive windows is

S_{i+1} − S_i = p[i+k] − p[i].

Since we only care about parity, subtraction behaves like addition modulo 2, so the condition that all S_i have the same parity forces

p[i] ≡ p[i+k] (mod 2).

This means that elements separated by exactly k positions must have the same parity. The array is therefore partitioned into k independent chains based on indices modulo k, and each chain must consist entirely of numbers of a single parity.

So the problem becomes: can we assign each of these k position-groups either all odd numbers or all even numbers so that the total number of odd slots equals the number of odd integers in 1 to n?

At this point, the structure becomes simple. The k groups have sizes differing by at most 1, and we are allowed to choose which groups are “odd groups”. Because the available group sizes form a consecutive structure (only floor(n/k) and ceil(n/k)), every target sum of group sizes can be achieved as long as we are not forced into a contradiction.

The only genuine obstruction appears when k = 1. In that case, there is a single group containing all positions, and it must be entirely odd or entirely even. That would require all numbers from 1 to n to share the same parity, which is impossible unless n = 1.

For every k ≥ 2, the flexibility of choosing which groups take odd numbers is sufficient to match the required count of odd integers.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Window Checking	O(nk) or O(n) per test	O(1)	Too slow
Parity Decomposition Insight	O(1) per test	O(1)	Accepted

Algorithm Walkthrough

Check if k equals 1. If it does, then the condition forces every element in the permutation to have the same parity. This is only possible when n equals 1, because any larger permutation contains both odd and even numbers.
If k is greater than or equal to 2, constructability is always possible. The parity constraint only enforces equality within index classes modulo k, and those classes can always be assigned odd and even roles in a way that matches the required global counts.
Output “Yes” for all cases except when k equals 1 and n is greater than 1.

Why it works

The parity constraint reduces the array into independent index classes where all elements at positions i, i + k, i + 2k, and so on must share parity. These classes are the only structure that matters for validity. Since we are free to assign parity per class, the problem becomes a partitioning of required odd counts across k adjustable groups. The only time this partitioning becomes impossible is when there is only one group, which happens exactly when k = 1 and n > 1.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        if k == 1 and n > 1:
            print("No")
        else:
            print("Yes")

if __name__ == "__main__":
    solve()

The implementation directly encodes the structural conclusion. The only conditional branch corresponds to the degenerate case where all elements must lie in a single parity class. No simulation or construction is needed because the problem reduces entirely to whether the modular index graph has more than one component.

Worked Examples

Example 1

Input: n = 4, k = 2

We have two position classes: indices (1,3) and (2,4). Each class must have uniform parity. The number of odd values in 1 to 4 is 2, so we can assign one class to odds and the other to evens.

Step	Observation
k check	k = 2, so multiple classes
parity requirement	positions i and i+2 share parity
assignment	one class odd, one even
result	valid

This demonstrates that flexibility in class assignment allows balancing parity counts.

Example 2

Input: n = 3, k = 1

There is a single class containing all positions. All elements must share parity, but the set {1,2,3} contains both odd and even values.

Step	Observation
k check	k = 1, single class
constraint	all values must have same parity
feasibility	impossible for n > 1
result	No

This shows the collapse of all structure into a single forced parity group.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(T)	each test is handled with a constant check
Space	O(1)	no auxiliary structures are needed

The solution comfortably fits within limits since even the maximum number of test cases only requires a simple conditional evaluation.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = []
    t = int(sys.stdin.readline())
    for _ in range(t):
        n, k = map(int, sys.stdin.readline().split())
        if k == 1 and n > 1:
            output.append("No")
        else:
            output.append("Yes")
    return "\n".join(output)

# provided samples
assert run("3\n3 1\n4 2\n5 3\n") == "No\nYes\nYes"

# minimum edge case
assert run("1\n1 1\n") == "Yes"

# k = 1 impossible case
assert run("2\n2 1\n10 1\n") == "No\nNo"

# large k always yes
assert run("3\n10 10\n5 6\n7 100\n") == "Yes\nYes\nYes"

# mixed cases
assert run("4\n6 2\n6 3\n6 1\n1 5\n") == "Yes\nYes\nNo\nYes"

Test input	Expected output	What it validates
n=1,k=1	Yes	trivial base case
k=1,n>1	No	single parity class failure
k>=2	Yes	general feasibility
k>n	Yes	degenerate large window case

Edge Cases

The most important edge case is when k = 1. In that situation, every window is a single element, so all numbers in the permutation must share the same parity. For any n > 1, this immediately fails because the permutation contains both odd and even values. The algorithm correctly identifies this and outputs No.

For example, with input n = 2, k = 1, the code enters the special condition and rejects the case. If we trace the logic, the single class contains both positions, forcing both numbers to have identical parity, which contradicts the structure of the set {1, 2}.

When k ≥ 2, even extreme values like k = n behave correctly. The algorithm accepts them immediately because there is only one window, so no parity conflict can arise.