JAG summer 2015 Day4 (= OpenCup GP of Japan), J: Black Company

Revision en1, by Darsein, 2015-10-02 08:09:53

JAG summer 2015 Day4 (= OpenCup GP of Japan) J: Black Company

At first, we define persons A and B are friends each other if they are close to each other or there is a person C s.t. A and B are close to C.

To simplify, we assume all ci is distinct. Then all salary relationships between two friends must be directed, i.e. we obtain a DAG, which is a subgraph of the total-order graph with respect to ci's. Here, the salary pv of a person v must be greater than the salary of all the persons who point to v on the DAG. We want to minimize pv, hence must be satisfied. Since the graph is a DAG, optimal pv for all v can be calculated by dynamic programming according to its topological order (with initializing 0-in-degree vertices to 1). If the DAG has E edges, this algorithm is O(N + E).

But how large is E? If we calculate all the friend relations naively, E = O(N2) in the worst case (e.g. star graph). We can avoid such situation by storing persons at vertex v who are (directly) close to v. Then we sort these persons with respect to ci's, and connect only adjacent persons in the sorted list. It is sufficient because the friend relations between persons in the list are total-order, and total-order is well-represented by a single linear extension. The sum of persons stored at each vertex is at most 2M, this pre-computation takes only O(MlogM) time, and E = O(M).

Finally, we should think of the case in which there are persons who have the same ci. In this case, we can consider as these persons are equivalent, so we merge vertices representing them. We note that the output is the sum of

Unable to parse markup [type=CF_TEX]

$. We can use Union-Find tree, strongly connected component decomposition, or something in order to calculate for merge, and these cost about O(M) time.

In conclusion, we can solve this problem in O(MlogM) time.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Darsein 2015-10-02 08:23:50 147 Tiny change: 'vertex is at most $2M$, thi' - (published)
en1 English Darsein 2015-10-02 08:09:53 2136 Initial revision (saved to drafts)