A-characteristic (Codeforces 1823A)
Tags: Math, combinatorics

Consider an array $$$a_1, a_2, \dots, a_n$$$ consisting of numbers $$$1$$$ and $$$-1$$$. Define $$$A$$$-characteristic of this array as a number of pairs of indices $$$1 \le i < j \le n$$$, such that $$$a_i \cdot a_j = 1$$$.Find any array $$$a$$$ with given length $$$n$$$ with $$$A$$$-characteristic equal to the given value $$$k$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100$$$; $$$0 \le k \le \frac{(n-1) n}{2}$$$) — the length of required array and required $$$A$$$-characteristic.

Output: For each test case, if there is no array $$$a$$$ with given $$$A$$$-characteristic $$$k$$$, print NO.Otherwise, print YES and $$$n$$$ numbers $$$1$$$ and $$$-1$$$, which form the required array $$$a$$$. If there are multiple answers, print any of them.

Note: In the first test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = -1 \neq 1$$$, hence its $$$A$$$-characteristic is $$$0$$$.In the second test case, there is only one pair of different elements in the array, and their product is $$$a_1 \cdot a_2 = 1$$$, hence its $$$A$$$-characteristic is $$$1$$$.In the third test case, there are three pairs of different elements in the array, and their product are: $$$a_1 \cdot a_2 = -1$$$, $$$a_1 \cdot a_3 = 1$$$, $$$a_2 \cdot a_3 = -1$$$, hence its $$$A$$$-characteristic is $$$1$$$.In the fourth test case, we can show, that there is no array with length $$$3$$$, which $$$A$$$-characteristic is $$$2$$$.

Sample Inputs:
7
2 0
2 1
3 1
3 2
3 3
5 4
5 5

Sample Outputs:
YES
1 -1 
YES
1 1 
YES
1 -1 1 
NO
YES
1 1 1 
YES
-1 1 -1 1 1 
NO

Solution (Python):
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    (n, k) = map(int, input().split())
    ok = 0
    for i in range(n):
        j = n - i
        if i * (i - 1) / 2 + j * (j - 1) / 2 == k:
            ok = 1
            print('YES')
            for h in range(i):
                print('1 ', end='')
            for h in range(j):
                print('-1 ', end='')
            print()
            break
    if not ok:
        print('NO')

Solution (Python):
for s in [*open(0)][1:]:
    (n, k) = map(int, s.split())
    i = 0
    while i < n and (n - i) * i != n * (n - 1) // 2 - k:
        i += 1
    print(*(['NO'], ['YES'] + [1] * i + [-1] * (n - i))[i < n])

Solution (Python):
import math
for _ in [0] * int(input()):
    (n, m) = map(int, input().split())
    b1 = n
    b2 = k = 0
    while b2 <= b1:
        if math.comb(b2, 2) + math.comb(b1, 2) == m:
            k = 1
            break
        elif math.comb(b2, 2) + math.comb(b1, 2) < m:
            break
        b2 += 1
        b1 -= 1
    if k == 0:
        print('NO')
    else:
        print('YES')
        for _ in [0] * b1:
            print(-1, end=' ')
        for _ in [0] * b2:
            print(1, end=' ')
        print()