You are not logged in. Please login at www.codechef.com to post your questions!

×

MXPATH - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes

Problem Link

Practice
Contest

Difficulty

Medium - Hard

PREREQUISITES:

Data Structure and Tree

Problem

Given a tree, with values in its vertices, and distances in its edges. We are asked to find the path that maximizes dist(u, v) · min(u, v) · gcd(u,v). Where dist denotes the distance (sum of distances on edges) between vertices, min and gcd denote the minimum and the greatest common divisor of the values of vertices between u and v.

Explanation

The strategy to solve this problem is similar to CO92TREE. First, we will fix the gcd, then the minimum and then we'll maximize the distance.

Let's suppose that we want a path with gcd equal to g. Then we only have to look at vertices that have a value multiple of g. Some of this nodes will be connected. Our goal is to maximize min(u,v) · dis(u,v) for every pair of vertices (u,v) that are in the same connected component.

Let's add the nodes that are multiple of g one by one in decreasing order of value, this will allow us to know which element is the minimum. When vertex u is added, maybe some of its adjacent vertices have already been added, and we'll have to merge their respective components (this can be done with a disjoint set union data structure).

So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components. So it only remains to know how does the diameter changes when two trees are merged.

Suppose that we merged trees T1 and T2 by drawing an edge e that joins vertices u in T1 with v in T2. The new diameter can be either the diameter of T1, the diameter of T2, or maybe there is a larger path that goes through e. In the last case, we have to find the farthest node to u that is in T1 and the farthest node to v that is in T2.

Now the problem is given a tree, what is the farthest node to a given vertex u. It turns out that if path x, y is a diameter of the tree, then either x or y will be one of the farthest nodes to u. This is more intuitive if we root the tree on its center.

A node with value x will be added once per divisor of x. So the total complexity O(N * max number of divisors of a[i]). We are ignoring the cost of calculating LCA since it can be done in O(1) after preprocessing a sparse table. Also, the cost of DSU is small in practice.

Implementation

Author's Solution
Tester's and Editorialist's Solution

This question is marked "community wiki".

asked 18 Mar, 23:46

alei's gravatar image

7★alei
1815
accept rate: 0%

edited 21 Mar, 19:57

admin's gravatar image

0★admin ♦♦
19.6k349497539


Can u explain this line : "So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components. "?

I am assuming that when we add a vertex u,we are calculating maximum value of dist(u,some v in its connected component).

I couldnt understand why we are calculating diameter.

link

answered 22 Mar, 08:30

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

1

We want to maximize distance. in a graph the distance between the two farthest nodes is called diameter.

(22 Mar, 08:36) alei7★

Thank you so much!! (My fault,didnt read the question properly

(22 Mar, 08:41) vivek_19982996★

Really sorry if this question feels stupid,but can u explain this line: "So far we have fixed gcd and minimum. To maximize distance, we need the diameters of the resulting components",i mean what if the minimum doesnt lie on the diameter path.

(22 Mar, 08:56) vivek_19982996★
2

note that we are adding the vertices in descending order. If the minimum is not in the diameter, then we already processed it before.

(22 Mar, 20:55) alei7★

Its really rare to see editorialists heartily replying to queries. The community appreciates your gesture @alei :)

(22 Mar, 21:53) vijju123 ♦5★

@alei ,got it

Thank you soo much!!

(23 Mar, 09:52) vivek_19982996★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,116
×1,188
×834
×685
×32
×3

question asked: 18 Mar, 23:46

question was seen: 586 times

last updated: 23 Mar, 09:52