Overview

A problem to determine whether we can select some computers from \(N\) computers and construct a tree-structured network that uses all ports completely. The answer can be determined by checking whether there exists a computer with \(0\) ports, or whether there are \(2\) or more computers with \(1\) port.

Analysis

Utilizing Properties of Trees

When constructing a tree with \(k\) computers, the following holds: - The number of edges (cables) is \(k-1\) - The sum of degrees (port usage) of all vertices = \(2(k-1)\)

In other words, if the port numbers of the selected computers are \(a_1, a_2, \ldots, a_k\), then \(\sum a_i = 2(k-1)\) is required.

Classical Result on Realizability

If a sequence of positive integers \(d_1, d_2, \ldots, d_k\) satisfies \(\sum d_i = 2(k-1)\), then a tree with that degree sequence always exists (a classical result derived from properties of Prüfer sequences).

Exhaustive Case Analysis

Case \(k = 1\): Selecting \(1\) computer with \(A_i = 0\) suffices → \(cnt_0 \geq 1\)

Case \(k = 2\): \(a_1 + a_2 = 2\) and \(a_1, a_2 \geq 1\), so \(a_1 = a_2 = 1\) → \(cnt_1 \geq 2\)

Case \(k \geq 3\): This is the key. All selected values must be \(\geq 1\), and the sum must equal \(2(k-1)\).

• If all selected values are \(\geq 2\), then the sum \(\geq 2k > 2(k-1)\). Impossible!
• If exactly \(1\) of the selected values is \(1\) and the rest are \(\geq 2\), then the sum \(\geq 1 + 2(k-1) = 2k-1 > 2(k-1)\). Impossible!
• If \(2\) or more are \(1\), there is a possibility, but this requires \(cnt_1 \geq 2\) (in this case, it’s simpler to just select \(2\) computers with \(A_i = 1\)).

Conclusion

The necessary and sufficient condition for the answer to be Yes is:

\[cnt_0 \geq 1 \quad \text{or} \quad cnt_1 \geq 2\]

Algorithm

1. Read the input and count the number of \(A_i = 0\) (\(cnt_0\)) and the number of \(A_i = 1\) (\(cnt_1\)).
2. If \(cnt_0 \geq 1\) or \(cnt_1 \geq 2\), output Yes; otherwise, output No.

Concrete examples: - \(A = [0, 3, 2]\): \(cnt_0 = 1 \geq 1\) → Yes (select only computer 1) - \(A = [1, 1, 5]\): \(cnt_1 = 2 \geq 2\) → Yes (select computers 1 and 2, connect with one cable) - \(A = [2, 3]\): \(cnt_0 = 0, cnt_1 = 0\) → No

Complexity

• Time complexity: \(O(N)\) (only a single pass through the array)
• Space complexity: \(O(1)\) (only counters are maintained)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\), input should be read as long long.

• The condition check is very simple; as long as the counting is done correctly, that’s all that’s needed.

• The essential insight of this problem is that there is no need to individually search for cases where \(k \geq 3\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    int cnt0 = 0, cnt1 = 0;
    for(int i = 0; i < N; i++){
        long long a;
        cin >> a;
        if(a == 0) cnt0++;
        if(a == 1) cnt1++;
    }
    
    if(cnt0 >= 1 || cnt1 >= 2){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.