anguerrera1's blog

Tutorial / Editorial for Problem 2172F Cluster Computing System
By anguerrera1, history, 6 months ago, In English

2172F - Cluster Computing System

Submission & Code: https://mirror.codeforces.com/contest/2172/submission/351543743

Intuition & Initial Thoughts

This problem is very interesting. The only piece of information that we are given about each of the nodes in our input graph are their associated values, and the definition of connecting two nodes. The key to solving this problem is to use the gcd(u, u+1, ..., v) fact to guide the solution.

Idea 1: Pick an arbitrary node, and find the smallest weight (similar to something such as Prim's Algorithm)

Challenge to Idea 1: We have N-1 choices to choose from at first. Based on the constraints of the problem, this solution will not pass. However, can we use the intuition to help?

After working through a few examples, you can see that extending the range of possible values only serves to help our solution. You can find that the gcd is a monotonically decreasing function upon a range of values through trial and error.

Idea 2: Since we need an O(N) solution, try and see if precomputing (prefix & suffix) can help.

The main intuition is the following: For a node a, we want to include as many possible values in our range for its connection. Since we have the constraint u < v (for an edge), It's best to consider 2 cases: when a = u (lower bound) and when a = v (upper bound).

When a = v, we want to connect it to node 1 (to get as many possible values in the range). Compute gcd (1, a). When a = u, we want to connect it to node n (again to get as many possible values in the range). Compute gcd(a, n).

We can take the minimum of each case for each node (what is the best way for node u to join the graph?). It will be connected to another node when it is considered at the bounds of this gcd array.

Note that by default, node 1 will be connected with node n. Therefore, we only need to loop through the first n-1 elements to find their optimal connections. node n will be paired with node 1 (work out a few examples)

Why is this optimal and correct?

Each node will only be connected to the graph once it is considered as either a lower or an upper bound. It will not be added to the graph otherwise. Therefore the greedy solution is correct.

(I hope this is a good enough explanation, can also work through a more formal proof by contradiction if anyone would like)

[](https://mirror.codeforces.com/contest/2172/submission/351543743)

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

cluster computing system

import math
import functools
def cluster_computing_system(n: int, p: list) -> int:
    p_ = p[::-1]
    ans = functools.reduce(math.gcd, p)
    g1 = p[0]
    g2 = p_[0]
    pre = []
    suff = []
    for i in range(1, n):
        x = p[i]
        y = p_[i]
        g1 = math.gcd(x, g1)
        g2 = math.gcd(y, g2)
        pre.append(g1)
        suff.append(g2)

    # print(pre)
    # print(suff)
    for i in range(1, n - 1):
        ans += min(pre[i], suff[-i - 1])
    return ans

n = int(input())
p = list(map(int, input().split()))
print(cluster_computing_system(n, p))

based on the above logic this is my implementation..can someone please tell me what is wrong..the code fails testcase 14

→ Reply