Progressive Square (Codeforces 1955B)
Tags: Implement, sortings

A progressive square of size $$$n$$$ is an $$$n \times n$$$ matrix. Maxim chooses three integers $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$ and constructs a progressive square according to the following rules:$$$$$$a_{i+1,j} = a_{i,j} + c$$$$$$$$$$$$a_{i,j+1} = a_{i,j} + d$$$$$$For example, if $$$n = 3$$$, $$$a_{1,1} = 1$$$, $$$c=2$$$, and $$$d=3$$$, then the progressive square looks as follows:$$$$$$ \begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix} $$$$$$Last month Maxim constructed a progressive square and remembered the values of $$$n$$$, $$$c$$$, and $$$d$$$. Recently, he found an array $$$b$$$ of $$$n^2$$$ integers in random order and wants to make sure that these elements are the elements of that specific square.It can be shown that for any values of $$$n$$$, $$$a_{1,1}$$$, $$$c$$$, and $$$d$$$, there exists exactly one progressive square that satisfies all the rules.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le {10} ^ 4$$$) — the number of test cases.The first line of each test case contains three integers $$$n$$$, $$$c$$$, and $$$d$$$ ($$$2 \le n \le 500$$$, $$$1 \le c, d \le 10^6$$$) — the size of the square and the values of $$$c$$$ and $$$d$$$ as described in the statement.The second line of each test case contains $$$n \cdot n$$$ integers $$$b_1, b_2, \dots, b_{n \cdot n}$$$ ($$$1 \le b_i \le 10^9$$$) — the elements found by Maxim.It is guaranteed that the sum of $$$n ^ 2$$$ over all test cases does not exceed $$$25 \cdot {10} ^ 4$$$.

Output: For each test case, output "YES" in a separate line if a progressive square for the given $$$n$$$, $$$c$$$, and $$$d$$$ can be constructed from the array elements $$$a$$$, otherwise output "NO".You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.


Sample Inputs:
5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15

Sample Outputs:
NO
YES
YES
NO
NO

Solution (Python):
def helper(start, inc, n):
    ans = []
    val = start
    for i in range(n):
        ans.append(val)
        val += inc
    return ans
tc = int(input())
for _ in range(tc):
    (n, c, d) = list(map(int, input().split()))
    li = list(map(int, input().split()))
    li.sort()
    val = li[0]
    grand = []
    for _ in range(n):
        grand.extend(helper(val, d, n))
        val += c
    grand.sort()
    if grand == li:
        print('YES')
    else:
        print('NO')

Solution (Python):
w = int(input())
for i in range(w):
    (n, c, c2) = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    d = []
    d2 = []
    q = a[0]
    for i in range(n):
        d.append(q)
        q = q + c
    for i in d:
        x = i
        for j in range(n):
            d2.append(x)
            x += c2
    d2.sort()
    if d2 == a:
        print('YES')
    else:
        print('NO')

Solution (Python):
def is_progressive_square(n, c, d, elements):
    se = sorted(elements)
    f = se[0]
    e = []
    for i in range(n):
        for j in range(n):
            e.append(f + i * c + j * d)
    return se == sorted(e)
t = int(input())
for _ in range(t):
    (n, c, d) = map(int, input().split())
    elements = list(map(int, input().split()))
    if is_progressive_square(n, c, d, elements):
        print('YES')
    else:
        print('NO')