Google Big Code

You are managing a distributed datacenter network with N server nodes connected by M bidirectional fiber-optic links. The network may consist of multiple connected components, nodes within the same component can communicate with each other, while nodes in different components cannot.

Each node i has a computational capacity value. You must assign the N available capacity values to the N nodes, each node receives exactly one value and each value is used exactly once, to maximize the total network efficiency.

Node Score

For each node i, define:

• degree[i] — the number of fiber-optic links directly connected to node i
• component_size[i] — the number of nodes in the connected component containing node i, including node i itself

The score of node i is:

If the graph has no edges (M = 0), every node forms its own component of size 1 with degree 0, giving every node a score of 1.

Objective

Find an assignment of capacity values to nodes that maximizes:

Function Description

Complete the solve function. It receives N, M, A, and edges, and returns the maximum possible total efficiency as a long long integer.

Function Parameters

• N: integer — the number of server nodes in the datacenter network
• M: integer — the number of bidirectional fiber-optic links
• A: vector<int> — the N available capacity values that must be assigned to nodes
• edges: vector<vector<int>> — each pair (u, v) represents a bidirectional

Explanation The Optimal Assignment: To get the highest possible efficiency, we multiply the highest scores (7, 7, 7) by the largest available capacities (50, 40, 30), and the lower scores (6, 6) by the remaining capacities (20, 10). Adding those products gives the final answer of 1020.