PROBLEM LINK:
Author: Roman Rubanenko
Tester: Hiroto Sekido
Editorialist: Anton Lunyov
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
The best described in the problem statement.
QUICK EXPLANATION:
It is clear that we have a complete weighted graph where vertices are the points and weight of the edge is the square of the distance between points. The problem asks to find the cycle-free set of edges with maximal product of weights. At first sight it seems to be the maximum spanning tree in this graph. But since some edges can have zero weights we actually should maximize the product of non-zero edges in our spanning tree. Since graph is complete then naive implementation of Prim’s algorithm would be the simplest way here.
Note that Prim’s algorithm works in O(V * V) time while Kruskal algorithm in O(E * log E) time, where V is the number of vertexes in the graph and E is the number of edges. In our case the graph is complete, so E = V * (V − 1) / 2 and hence Kruskal algorithm is much slower (due to log E factor). It was intended that Kruskal should get TLE, while any implementation of Prim (with precalculating all edges or not) will get AC.
The main bottleneck of the Kruskal algorithm is sorting of edges (not DSU stuff) and in the Prim we have no sorting at all. That is the point.
EXPLANATION:
As noted above we can reformulate the problem as follows - find the spanning tree in constructed graph that has maximum possible product of non-zero edges in it. It is well-known that spanning tree found by general greedy algorithm (like Prim’s or Kruskal’s) will maximize any symmetric monotone function of edges (I read this remark 10 years ago in Christofides book and still remember this). The product of non-zero edges is exactly one of such functions since we have no negative edges. Hence well-known algorithms for finding maximum spanning tree will work here.
The implementation of Prim’s algorithm suited for this problem is provided below. Once maximum distance between marked and not marked vertexes becomes zero we could break from the cycle. Also we do not create the adjacency matrix and calculate each needed distance on the fly.
And the most important thing is - the squares of distances should be calculated and compared as is, take them modulo 747474747 only when you multiply them to the answer. For example, if we have only two points, and square of distance between them is 747474747 then in the case of taking this distance modulo at the beginning you break from the cycle and the answer will be 1, but the correct answer is 747474747 and you should output 0. The concrete example is
2 3
0 0 0
19265 19189 2849
The output should 0.
And finally the code snippet:
input points // they are numbered from 1 to N
// d[i] is the farthest distance from point i to the vertexes of the tree
fill d[1..N] by zeros // should be 64bit integer type
// vertex is marked if it is in the current tree
fill mark[1..N] by false // so initially tree is empty
mod = 747474747
ans = 1 // could be int
for iter = 1 to N do
j = 0 // will contain the farthest vertex from current tree
for i = 1 to N do
// we update j once we meet not marked vertex with larger distance to the tree
if (not mark[i] and (j = 0 or d[j] < d[i])) then
j=i
mark[j] = true // we add j to the tree
// now we update the answer
// when iter = 1 we create tree of one vertex
// so d[j] does not make sense
if iter > 1 then
if d[j] <= 1 then
break
else
// note that we take d[j] modulo mod
// otherwise 64bit type overflow is possible
ans = d[j] % mod * ans % mod
// now we should update array d[]
// clearly we need to update each d[i] for not marked i
// by distance to j since this is the only new vertex in the tree
for i = 1 to N do
if not mark[i] then
dist = square of distance between a[i] and a[j]
// use 64bit type here but don't use modulo or the order of edges will be broken
d[i] = max(d[i], dist)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be provided soon.
Tester’s solution can be found here.
(The complete solution took ~24 seconds for a large test case, on my local machine.)