CF 1352B - Same Parity Summands

Rating: 1200
Tags: constructive algorithms, math
Solve time: 6m 28s
Verified: no

Solution

Problem Understanding

We are asked to split a given integer $n$ into exactly $k$ positive parts such that all parts share the same parity. This means we must choose either all odd numbers or all even numbers, and these $k$ numbers must sum exactly to $n$.

The output is either a concrete construction of such a sequence or a declaration that no such construction exists. We are free to output any valid decomposition, so we are not searching for an optimal or unique solution, only feasibility plus one example.

The constraints allow $n$ up to $10^9$ and up to 1000 test cases, with $k \le 100$. This immediately rules out any exponential or per-test brute force enumeration of partitions. Even an $O(n)$ approach per test would be too slow in aggregate. The structure of the problem strongly suggests a constant-time arithmetic check per test case.

The main difficulty is not constructing numbers once a parity is chosen, but ensuring that such a choice is even possible while maintaining positivity constraints.

A few edge situations expose where naive reasoning fails. If we try to always use odd numbers, we might run into a parity mismatch. For example, $n = 10, k = 3$ works, but $n = 8, k = 7$ does not, because the smallest possible sum of 7 odd positives is 7, but parity constraints also fail. Another subtle failure happens when mixing parity implicitly, for instance trying to "fix parity at the end" after choosing most values greedily, which breaks the requirement that all $k$ numbers must have identical parity.

Approaches

A brute-force interpretation would try all ways to pick $k$ positive integers and check whether their sum is $n$, restricting to either all odd or all even. Even restricting to one parity, the number of compositions grows combinatorially, roughly $\binom{n-1}{k-1}$, which is completely infeasible even for tiny values of $n$. This approach is mathematically correct but computationally unusable.

The key observation is that once parity is fixed, the structure of valid numbers becomes extremely rigid. If all numbers are odd, each is at least 1. If all numbers are even, each is at least 2. This reduces the problem to checking whether the remaining sum after assigning minimal values can be distributed in steps of 2.

For odd parity, we assign $k$ ones, consuming $k$ from $n$. The remaining sum must be even so it can be split into increments of 2 added to these ones. For even parity, we assign $k$ twos, consuming $2k$ from $n$. The remaining sum must still be non-negative and even.

This transforms the problem into two simple feasibility checks followed by straightforward construction.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	exponential	O(1)	Too slow
Optimal	O(1) per test	O(k)	Accepted

Algorithm Walkthrough

We evaluate each test case independently.

Check if we can use odd numbers. Start by assigning 1 to all $k$ positions. This uses $k$ total sum. We compute the remainder $r = n - k$. If $r \ge 0$ and $r$ is even, this configuration can be completed. The even remainder can be distributed by adding 2 repeatedly to any of the positions without breaking positivity or parity.
If the odd construction fails, try even numbers. Assign 2 to all $k$ positions. This uses $2k$, leaving $r = n - 2k$. If $r \ge 0$ and $r$ is even, we can distribute it in steps of 2 across the array.
If both attempts fail, output NO.
When a construction succeeds, start from the base array (all 1s or all 2s) and distribute the remainder by adding 2 repeatedly to any positions, typically the first one for simplicity.

The reason adding 2 preserves validity is that it keeps parity unchanged while maintaining positivity.

Why it works

Any valid solution must be entirely odd or entirely even. If it is all odd, subtracting 1 from each element leaves a non-negative even number distributed across $k$ slots. That implies the total sum must be at least $k$ and differ from $k$ by an even number. The same logic applies for even numbers with base value 2. These are not just sufficient conditions but also necessary ones, since every odd number contributes at least 1 and every even number contributes at least 2, and parity fixes the step size to 2 increments.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())

    # try odd: all 1s
    if n >= k and (n - k) % 2 == 0:
        base = [1] * k
        rem = n - k
        base[0] += rem
        print("YES")
        print(*base)
        continue

    # try even: all 2s
    if n >= 2 * k and (n - 2 * k) % 2 == 0:
        base = [2] * k
        rem = n - 2 * k
        base[0] += rem
        print("YES")
        print(*base)
        continue

    print("NO")

The first block checks feasibility for all-odd construction. The condition $n \ge k$ ensures positivity since each element is at least 1. The parity condition ensures the leftover can be split into increments of 2.

The second block repeats the same reasoning for all-even construction, where the minimum per element is 2 instead of 1.

We distribute the remainder entirely to the first element for simplicity. This is safe because adding an even number preserves both positivity and parity.

Worked Examples

Example 1: n = 10, k = 3

We attempt odd construction first.

Step	Base array	Remaining sum	Condition
odd check	[1, 1, 1]	10 - 3 = 7	7 is odd → fail
even check	[2, 2, 2]	10 - 6 = 4	valid

We succeed with the even construction and distribute 4 into the first element, producing [6, 2, 2].

This confirms that even-parity construction can absorb extra sum in steps of 2 while preserving validity.

Example 2: n = 8, k = 7

Step	Base array	Remaining sum	Condition
odd check	[1,1,1,1,1,1,1]	1	insufficient parity condition fails
even check	[2,2,2,2,2,2,2]	-6	negative

Both constructions fail because the smallest possible odd sum is 7 and smallest even sum is 14, and 8 lies between them.

This demonstrates that feasibility is entirely determined by two tight lower bounds.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(t)	Each test performs constant arithmetic checks and at most one construction
Space	O(k)	Only stores up to k integers for output

The solution easily fits within limits since $t \le 1000$ and $k \le 100$, leading to at most $10^5$ output operations total.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    from io import StringIO as _StringIO

    out = _StringIO()
    _stdout = _sys.stdout
    _sys.stdout = out

    # solution
    import sys
    input = sys.stdin.readline

    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())

        if n >= k and (n - k) % 2 == 0:
            res = [1] * k
            res[0] += n - k
            print("YES")
            print(*res)
        elif n >= 2 * k and (n - 2 * k) % 2 == 0:
            res = [2] * k
            res[0] += n - 2 * k
            print("YES")
            print(*res)
        else:
            print("NO")

    _sys.stdout = _stdout
    return out.getvalue().strip()

# provided samples
assert run("""8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9
""") == """YES
6 2 2
YES
97 1 1 1
NO
NO
YES
2 2 2 2 2 2 2 2
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120""", "sample 1"

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

# impossible small
assert run("1\n2 2\n") == "YES\n2 2" or run("1\n2 2\n") == "YES\n2 2"

# odd feasibility edge
assert run("1\n3 2\n") == "NO"

# large even construction
assert run("1\n1000000000 2\n") != ""

Test input	Expected output	What it validates
1 1	YES 1	minimal valid configuration
2 2	YES 2 2	even construction base case
3 2	NO	parity impossibility
1000000000 2	valid pair	large-scale feasibility

Edge Cases

For $n = k$, the odd construction always succeeds because all ones sum exactly to $k$, producing a valid all-odd sequence. The algorithm correctly accepts since $n - k = 0$, which satisfies the even remainder condition.

For $n = 2k$, the even construction produces all twos with zero remainder. The condition $n \ge 2k$ and $(n - 2k) % 2 = 0$ holds, so the output is valid.

For $n < k$, both constructions fail immediately because even the smallest possible sum of $k$ positive integers is $k$ when all are 1. The algorithm rejects correctly before any construction attempt.

For cases where $n - k$ is odd but non-negative, the odd construction fails even though there is enough total sum. This captures the key parity restriction: leftover mass must be divisible into steps of 2, not just non-negative.