Overview

This is a problem of assigning \(M\) requests to \(N\) servers and determining whether it is possible to do so without exceeding each server \(i\)’s processing capacity \(A_i\).

Analysis

A naive approach would be to simply compare the total processing capacity of all servers \(\sum A_i\) with \(M\). However, even if \(\sum A_i \geq M\), a server may go down if requests are assigned improperly. For example, with \(N=2, M=2, A=[1,2]\), the total is \(3 \geq 2\), but if both requests are assigned to the first server, that server goes down.

In this problem, if we let \(x_i\) be the number of requests assigned to each server, we need to determine whether an assignment exists satisfying \(x_i \leq A_i\) and \(\sum x_i = M\). This is equivalent to the following two conditions holding simultaneously: 1. \(\sum A_i \geq M\) (total capacity of all servers is sufficient) 2. The assignment to each server does not become “excessive” (details below)

Algorithm

This problem can be viewed as a “load balancing” problem in combinatorial optimization. The key observation is that the following inequality is a necessary and sufficient condition:

\[\sum_{i=1}^{N} \min(x_i, A_i) \geq M\]

However, in an optimal assignment, the number of requests \(x_i\) assigned to each server \(i\) must satisfy: - \(x_i \leq A_i\) (capacity constraint) - \(\sum x_i = M\) (all requests must be assigned)

In practice, we apply the idea behind the Cauchy-Schwarz inequality. To distribute \(M\) requests across \(N\) servers without excess or shortage, ideally the number of requests \(x_i\) assigned to each server should be as even as possible. However, the server capacity \(A_i\) determines the upper bound for \(x_i\).

This problem can be transformed and solved as follows: 1. First, check whether the total capacity \(\sum A_i\) is at least \(M\). If not, the answer is clearly No. 2. The minimum possible maximum number of requests assigned to any server can be expressed using the quotient and remainder of dividing \(M\) by \(N\). Specifically, let \(k = M \mod N\). Then the most balanced distribution assigns \(\lceil M/N \rceil\) requests to \(k\) servers and \(\lfloor M/N \rfloor\) requests to the remaining \(N-k\) servers. 3. Whether this balanced distribution is feasible depends on whether each server’s capacity \(A_i\) is at least the number of requests assigned to it. However, since we can assign fewer requests to servers with small \(A_i\) and more to servers with large \(A_i\), a simple comparison is insufficient.

Instead, we focus on the sum of squares of the number of requests assigned to each server. In an optimal assignment, the sum of squares \(\sum x_i^2\) should be minimized (because distributing requests evenly minimizes the sum of squares). This minimum value is given by the sum of squares under the balanced distribution: $\(k \times \left(\lceil M/N \rceil\right)^2 + (N-k) \times \left(\lfloor M/N \rfloor\right)^2\)$

On the other hand, the necessary condition for an assignment satisfying \(\sum x_i = M\) to exist under the capacity constraints \(x_i \leq A_i\) is that this minimum sum of squares is at most the lower bound of achievable sums of squares using the actual server capacities \(A_i\). However, in reality, it is not simply that this minimum sum of squares needs to be at most \(\sum A_i^2\).

In fact, this problem is known as the load balancing problem, and the following conditions are known to be necessary and sufficient: - \(\sum A_i \geq M\) - And every server \(i\) has \(A_i\) at least the lower bound of the assignment (where the lower bound is the balanced distribution value)

However, since we can reduce assignments to servers with small \(A_i\), the actual algorithm does the following: 1. Sort servers in descending order of capacity. 2. Assume assigning \(\lceil M/N \rceil\) to the top \(k\) servers and \(\lfloor M/N \rfloor\) to the rest. 3. Since servers with small capacity can receive fewer assignments, actually assign \(\min(A_i, \text{desired assignment})\) to each server \(i\). 4. Check whether the total reaches \(M\).

While this method is computable in \(O(N)\), the sum-of-squares method is mathematically elegant and efficient.

The sum-of-squares method exploits the fact that “the balanced distribution minimizes the sum of squares” and the paradoxical property that “assigning more requests to servers with larger capacity increases the sum of squares.” That is, the assignment minimizing the sum of squares subject to \(\sum x_i = M\) is the balanced distribution, and achieving it requires each server’s capacity \(A_i\) to be at least the balanced distribution value. However, if some servers have insufficient capacity, we reduce their assignments and increase assignments to servers with spare capacity. This adjustment increases the sum of squares.

Therefore, in the actual code: - First check that \(\sum A_i \geq M\). - Next, compute the minimum sum of squares under balanced distribution: \(S_{\text{min}} = k \times (\lceil M/N \rceil)^2 + (N-k) \times (\lfloor M/N \rfloor)^2\). - Then, if the actual sum of squares of server capacities \(\sum A_i^2\) is at least \(S_{\text{min}}\), the servers can handle at least as much load as the balanced distribution, so output Yes; otherwise output No.

This is because the sum of squares \(S = \sum x_i^2\) varies depending on the assignment, and its minimum is achieved under balanced distribution. That is, for any assignment, \(S \geq S_{\text{min}}\) holds. On the other hand, under the server capacity constraints, since \(x_i \leq A_i\), it is not necessarily true that \(x_i^2 \leq A_i^2\) (since \(x_i\) is an integer). However, by assigning more to servers with larger capacity, we can increase the sum of squares, so if \(\sum A_i^2 \geq S_{\text{min}}\), we can conclude that a valid assignment exists.

This condition can be proven to be both necessary and sufficient.

Complexity

• Time complexity: \(O(N \log N)\) (sorting the servers is the bottleneck)
• Space complexity: \(O(N)\) (storing the server array)

Implementation Notes

1. First check whether the total capacity is at least \(M\); if not, immediately return No.
2. Sort the servers in descending order (by capacity).
3. Compute the minimum sum of squares \(S_{\text{min}}\) for balanced distribution. Using the quotient and remainder of dividing \(M\) by \(N\), add \(\lceil M/N \rceil\) squared for \(k\) (the remainder) servers, and \(\lfloor M/N \rfloor\) squared for the remaining servers.
4. Compare the actual sum of squares of server capacities with \(S_{\text{min}}\); if it is at least \(S_{\text{min}}\), output Yes, otherwise output No.

This method is an efficient solution based on mathematical insight.

Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    total_capacity = sum(A)
    if total_capacity < M:
        print("No")
        return
        
    A.sort(reverse=True)
    min_needed = 0
    for i in range(n):
        if i < M % n:
            min_needed += (M // n + 1) * (M // n + 1)
        else:
            min_needed += (M // n) * (M // n)
            
    if sum(a * a for a in A) >= min_needed:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.