[Solution] Mark the Photographer solution codeforces

Mark the Photographer solution codeforces – Mark is asked to take a group photo of 2𝑛2n people. The 𝑖i-th person has height 𝑖hi units.

To do so, he ordered these people into two rows, the front row and the back row, each consisting of 𝑛n people. However, to ensure that everyone is seen properly, the 𝑗j-th person of the back row must be at least 𝑥x units taller than the 𝑗j-th person of the front row for each 𝑗j between 11 and 𝑛n, inclusive.

Table of Contents

[Solution] Mark the Photographer solution codeforces

Help Mark determine if this is possible.

Input

The first line contains one integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases. Each test case consists of two lines.

The first line of each test case contains two positive integers 𝑛n and 𝑥x (1𝑛1001≤n≤1001𝑥1031≤x≤103) — the number of people in each row and the minimum difference Mark wants.

The second line of each test case contains 2𝑛2n positive integers 1,2,,2𝑛h1,h2,…,h2n (1𝑖1031≤hi≤103) — the height of each person in units.

Note that the sum of 𝑛n over all test cases is not bounded.

[Solution] Mark the Photographer solution codeforces

For each test case, print a single line containing “YES” if Mark could arrange people satisfying his condition and “NO” otherwise.

You may print each letter in any case (for example, YESYesyesyEs will all be recognized as positive answers).

Example
input

Copy
3
3 6
1 3 9 10 12 16
3 1
2 5 2 2 2 5
1 2
8 6
output

Copy
YES
NO
YES

[Solution] Mark the Photographer solution codeforces

In the first test case, one possible order is to have the third, fifth, and sixth person on the back row and the second, first, and fourth on the front row. The heights of the people will look like this.

Back 99 1212 1616
Front 33 11 1010

It works because

  • 32=936h3−h2=9−3≥6,
  • 51=1216h5−h1=12−1≥6, and
  • 64=16106h6−h4=16−10≥6.

In the second test case, it can be shown there is no way to order people in a way that satisfies the condition.

In the third test case, the only way to arrange people to satisfy the condition is to have the first person on the back row and the second person on the front row.

For Solution

Click Here

Leave a Comment