Hide

# Problem LUnterwave Distance

The first sample input.

The year is 2312, and Humanity’s Rush to the Stars is now $200$ years old. The problem of real-time communication between star systems remains, however, and the key is the unterwave.

Unterwave (UW) communication works as follows: direct UW links have been set up between certain pairs of star systems, and two systems without a direct link communicate by hopping along existing links through intermediary systems. Although no system has more than $20$ direct links to other systems, any two systems can communicate, either directly or indirectly.

You have been asked to select two star systems for your company’s new home offices—one in a human system, and one in an alien system. (Oh yeah, there are aliens.) You are to select them so that the UW distance (a measure of communication latency) is minimized.

Every star system has a gravity value that affects UW communication. Just as no two snowflakes on earth have the same crystalline structure, no two star systems in the universe have the same gravity. If a communication path from from one system to another encounters the sequence $G = g_1, g_2, \ldots , g_ n$ of gravity values, including the source and destination of the message, then three sequences of $n-1$ terms each may be defined, relating to physical characteristics of UW communication:

\begin{align*} \operatorname {cap}(G) & = g_2+g_1,\ g_3+g_2,\ \ldots ,\ g_ n+g_{n-1} & \textrm{(Capacitance)} \\ \operatorname {pot}(G) & = g_2-g_1,\ g_3-g_2,\ \ldots ,\ g_ n-g_{n-1} & \textrm{(Potential)} \\ \operatorname {ind}(G) & = g_2\cdot g_1,\ g_3\cdot g_2,\ \ldots ,\ g_ n\cdot g_{n-1} & \textrm{(Inductance)} \end{align*}

For two sequences $A=a_1,\ a_2,\ \ldots ,\ a_ m$ and $B=b_1,\ b_2,\ \ldots ,\ b_ m$ we define:

\begin{align*} A\cdot B & = a_1\cdot b_1,\ a_2\cdot b_2,\ \ldots ,\ a_ m\cdot b_ m & A-B & = a_1- b_1,\ a_2- b_2,\ \ldots ,\ a_ m- b_ m \end{align*}

Finally, the UW distance is given by the absolute value of the sum of the values of the sequence

$\operatorname {pot}(G)\cdot \left(\left[\operatorname {cap}(G)\cdot \operatorname {cap}(G)\right]-\operatorname {ind}(G)\right).$

The UW distance can be quite large. Fortunately, your company has a gravity dispersal device, which may be placed in any single system (and remain there). It reduces by $1$ the gravity of that system, but increases by $1$ the gravities of all systems directly linked to it. Use of this device is optional.

## Input

The first line has a single integer $2\leq n\leq 50\, 000$, giving the number of star systems. The next $n$ lines describe the star systems, numbered $1$ to $n$. Each line has the form $g\ d$ where $g$ is the gravity value of that system ($1\leq g\leq 1\, 000\, 000$) and $d$ is either ‘h’ or ‘a’, designating the system as human or alien (there is at least one system of each type). All values of $g$ are distinct. The next line has a positive integer $e$ giving the number of direct links between systems. Each of the next $e$ lines contains two integers separated by a single space, which are the numbers of two systems that are directly linked. Links are bidirectional, and no link appears more than once in the input. No system links directly to more than $20$ other systems.

## Output

Output the minimum UW distance that can be achieved between an alien and human system.

Sample Input 1 Sample Output 1
9
377 a
455 h
180 a
211 a
134 a
46 h
111 h
213 h
17 a
15
1 2
1 4
1 6
2 3
2 4
2 5
3 5
4 6
4 7
4 9
5 7
5 8
6 9
7 9
7 8

85293

Sample Input 2 Sample Output 2
3
20 h
21 h
19 a
3
1 2
2 3
3 1

0

CPU Time limit 5 seconds
Memory limit 1024 MB
Statistics Show
The passage describes a problem involving the calculation of the minimum UW distance between a human and an alien star system, considering the effects of gravity and a gravity dispersal device. The problem is structured with a detailed explanation of the UW distance formula and the input/output format for a computational solution.
single_question_with_answer

the text contains a single mathematical question (determining the minimum uw distance) and provides answers for two sample inputs (85293 and 0).
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
Hide

# Problem LUnterwave Distance

The first sample input.

The year is 2312, and Humanity’s Rush to the Stars is now $200$ years old. The problem of real-time communication between star systems remains, however, and the key is the unterwave.

Unterwave (UW) communication works as follows: direct UW links have been set up between certain pairs of star systems, and two systems without a direct link communicate by hopping along existing links through intermediary systems. Although no system has more than $20$ direct links to other systems, any two systems can communicate, either directly or indirectly.

You have been asked to select two star systems for your company’s new home offices—one in a human system, and one in an alien system. (Oh yeah, there are aliens.) You are to select them so that the UW distance (a measure of communication latency) is minimized.

Every star system has a gravity value that affects UW communication. Just as no two snowflakes on earth have the same crystalline structure, no two star systems in the universe have the same gravity. If a communication path from from one system to another encounters the sequence $G = g_1, g_2, \ldots , g_ n$ of gravity values, including the source and destination of the message, then three sequences of $n-1$ terms each may be defined, relating to physical characteristics of UW communication:

\begin{align*} \operatorname {cap}(G) & = g_2+g_1,\ g_3+g_2,\ \ldots ,\ g_ n+g_{n-1} & \textrm{(Capacitance)} \\ \operatorname {pot}(G) & = g_2-g_1,\ g_3-g_2,\ \ldots ,\ g_ n-g_{n-1} & \textrm{(Potential)} \\ \operatorname {ind}(G) & = g_2\cdot g_1,\ g_3\cdot g_2,\ \ldots ,\ g_ n\cdot g_{n-1} & \textrm{(Inductance)} \end{align*}

For two sequences $A=a_1,\ a_2,\ \ldots ,\ a_ m$ and $B=b_1,\ b_2,\ \ldots ,\ b_ m$ we define:

\begin{align*} A\cdot B & = a_1\cdot b_1,\ a_2\cdot b_2,\ \ldots ,\ a_ m\cdot b_ m & A-B & = a_1- b_1,\ a_2- b_2,\ \ldots ,\ a_ m- b_ m \end{align*}

Finally, the UW distance is given by the absolute value of the sum of the values of the sequence

$\operatorname {pot}(G)\cdot \left(\left[\operatorname {cap}(G)\cdot \operatorname {cap}(G)\right]-\operatorname {ind}(G)\right).$

The UW distance can be quite large. Fortunately, your company has a gravity dispersal device, which may be placed in any single system (and remain there). It reduces by $1$ the gravity of that system, but increases by $1$ the gravities of all systems directly linked to it. Use of this device is optional.

## Input

The first line has a single integer $2\leq n\leq 50\, 000$, giving the number of star systems. The next $n$ lines describe the star systems, numbered $1$ to $n$. Each line has the form $g\ d$ where $g$ is the gravity value of that system ($1\leq g\leq 1\, 000\, 000$) and $d$ is either ‘h’ or ‘a’, designating the system as human or alien (there is at least one system of each type). All values of $g$ are distinct. The next line has a positive integer $e$ giving the number of direct links between systems. Each of the next $e$ lines contains two integers separated by a single space, which are the numbers of two systems that are directly linked. Links are bidirectional, and no link appears more than once in the input. No system links directly to more than $20$ other systems.

## Output

Output the minimum UW distance that can be achieved between an alien and human system.

Sample Input 1 Sample Output 1
9
377 a
455 h
180 a
211 a
134 a
46 h
111 h
213 h
17 a
15
1 2
1 4
1 6
2 3
2 4
2 5
3 5
4 6
4 7
4 9
5 7
5 8
6 9
7 9
7 8

85293

Sample Input 2 Sample Output 2
3
20 h
21 h
19 a
3
1 2
2 3
3 1

0

CPU Time limit 5 seconds
Memory limit 1024 MB
Statistics Show
user
The passage describes a problem involving the calculation of the minimum UW distance between a human and an alien star system, considering the effects of gravity and a gravity dispersal device. The problem is structured with a detailed explanation of the UW distance formula and the input/output format for a computational solution.

TYPE: SINGLE_QUESTION_WITH_ANSWER

The text contains a single mathematical question (determining the minimum UW distance) and provides answers for two sample inputs (85293 and 0).