Doremy’s Connecting Plan Solution

Doremy’s Connecting Plan Solution

Doremy lives in a country consisting of n cities numbered from 1 to n , with ai people living in the i -th city. It can be modeled as an undirected graph with n nodes.

Doremy resides in a country composed of $n$ cities, numbered from 1 to $n$, each housing ��ai​ people in the $i$-th city. This country can be represented as an undirected graph with $n$ nodes.

Initially, the graph is devoid of any edges. Doremy’s objective is to create a connected graph. To achieve this, she can connect nodes $i$ and $j$ by adding an edge if the condition ∑�∈���≥�⋅�⋅�∑k∈S​ak​≥i⋅j⋅c is satisfied, where $S$ represents the set of all nodes within the same connected component as either $i$ or $j$, and $c$ is a given constant.

Can Doremy effectively establish a connected graph?

The input entails multiple test cases. The first line contains a single integer $t$ (1≤�≤1041≤t≤104), denoting the number of test cases. The subsequent lines describe each test case.

For each test case: Doremy’s Connecting Plan Solution

• The first line holds two integers: $n$ and $c$ (2≤�≤2×1052≤n≤2×105, 1≤�≤1061≤c≤106)—the number of nodes and the constant, respectively.
• The second line of each test case comprises $n$ integers �1,�2,…,��a1​,a2​,…,an​ (0≤��≤10120≤ai​≤1012)—representing the population in each city.

Output is “YES” if it’s possible to make the graph connected, or “NO” otherwise.

For instance, in the first test case, Doremy can establish connections as follows:

1. Connect (1,2) as �1+�2=20≥�⋅�⋅�=20a1​+a2​=20≥i⋅j⋅c=20.
2. Connect (1,3) as �1+�2+�3=35≥�⋅�⋅�=30a1​+a2​+a3​=35≥i⋅j⋅c=30.
3. Connect (1,4) as �1+�2+�3+�4=45≥�⋅�⋅�=40a1​+a2​+a3​+a4​=45≥i⋅j⋅c=40.

The other test cases follow similar conditions and connectivity rules.