[Solution] Social Distance solution codeforces

Social Distance solution codeforces𝑚m chairs are arranged in a circle sequentially. The chairs are numbered from 00 to 𝑚1m−1𝑛n people want to sit in these chairs. The 𝑖i-th of them wants at least 𝑎[𝑖]a[i] empty chairs both on his right and left side.

[Solution] Social Distance solution codeforces

More formally, if the 𝑖i-th person sits in the 𝑗j-th chair, then no one else should sit in the following chairs: (𝑗𝑎[𝑖])mod𝑚(j−a[i])modm(𝑗𝑎[𝑖]+1)mod𝑚(j−a[i]+1)modm, … (𝑗+𝑎[𝑖]1)mod𝑚(j+a[i]−1)modm(𝑗+𝑎[𝑖])mod𝑚(j+a[i])modm.

Decide if it is possible to sit down for all of them, under the given limitations.


The input consists of multiple test cases. The first line contains a single integer 𝑡t (1𝑡51041≤t≤5⋅104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (2𝑛1052≤n≤1051𝑚1091≤m≤109) — the number of people and the number of chairs.

The next line contains 𝑛n integers, 𝑎1a1𝑎2a2, … 𝑎𝑛an (1𝑎𝑖1091≤ai≤109) — the minimum number of empty chairs, on both sides of the 𝑖i-th person.

It is guaranteed that the sum of 𝑛n over all test cases will not exceed 105105.

[Solution] Social Distance solution codeforces

For each test case print “YES” (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and “NO” (without quotes) otherwise.

You may print every letter in any case you want (so, for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be recognized as positive answers).


3 2
1 1 1
2 4
1 1
2 5
2 1
3 8
1 2 1
4 12
1 2 1 3
4 19
1 2 1 3


Social Distance solution codeforces

Test case 11𝑛>𝑚n>m, so they can not sit down.

Test case 22: the first person can sit 22-nd and the second person can sit in the 00-th chair. Both of them want at least 11 empty chair on both sides, chairs 11 and 33 are free, so this is a good solution.

Test case 33: if the second person sits down somewhere, he needs 22 empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only 55 chairs.

Test case 44: they can sit in the 11-st, 44-th, 77-th chairs respectively.


For Solution

Click here

Leave a Comment