[Solution] Careless Chef solution codechef

Careless Chef solution codechef – Chef has a sequence of integers AA of length NN. He creates another sequence BB of length 2N2⋅N using sequence AA. Initially, BB is empty. Chef performs the following process.

For each element AiAi (1iN)(1≤i≤N) of AA:

• Choose any arbitrary integer kk (Note that the value of kk can be different for different elements).
• Add AikAi−k and Ai+kAi+k to BB.

Chef then shuffles the sequence BB randomly after this process.

Since Chef is careless, he lost both AA and BB and now only vaguely remembers the elements of BB. Chef would like to know if the sequence BB (which he vaguely remembers) can be correct or not. Can you help him?

Formally, you are provided with a sequence BB of size 2N2⋅N. You are required to tell if the provided sequence can be achieved from any sequence AA of size NN using the given process or not.

Careless Chef solution codechef

• The first line of the input contains a single integer TT – the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line of each test case contains 2N2⋅N space-separated integers B1,B2,,B2N.B1,B2,…,B2⋅N.

Output Format

• For each test case, print YES if the provided sequence BB can be achieved from any sequence AA of size NN using the given process. Otherwise, print NO.

You may print each character of YES and NO in uppercase or lowercase (for example, the strings yEsyesYes and YES will be treated identical).

Constraints

• 1T1041≤T≤104
• 1N1051≤N≤105
• |B|=2N|B|=2⋅N
• 105Bi105−105≤Bi≤105
• It is guaranteed that the sum of NN over all test cases does not exceed 21052⋅105

Careless Chef solution codechef

3
1
1 1
2
16 2 2022 2001
2
2 4 -2 4


Sample Output 1

YES
NO
YES


Careless Chef solution codechef

• Test case 11: The given sequence BB can be generated using A=[1]A=[1] with k=0k=0 for A1A1.
• Test case 22: There doesn’t exist any sequence AA which can generate the given sequence BB by simulating the given process.
• Test case 33: The given sequence BB can be generated using A=[4,0]A=[4,0] with k=0k=0 for A1A1 and k=2k=−2 for A2A2.