YamanoteLine

SRM 553 · 2012-06-05 · by wata

SRM 553 · 2012-06-05 · by wata · Graph Theory

Show categories

Class Name: YamanoteLine

Return Type: long

Method Name: howMany

Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>, vector<int>, vector<int>)

Problem Statement

In Tokyo, there is a big circular railroad called "Yamanote Line." It contains n stations, numbered 0 through n-1 in clockwise direction. You are given the int n.

There is a direct track segment between each pair of consecutive stations (between 0 and 1, between 1 and 2, ..., and between n-1 and 0). You do not know the exact lengths of these track segments, but you know for sure that the length of each track segment is a positive integer.

You want to find the length of the entire circular railroad. Two of your friends took some rides on the Yamanote line and reported their findings to you. The first friend was trying to establish some lower bounds. Each of his reports had the form: "The clockwise distance from station S to a different station T is at least L." The second friend was trying to establish some upper bounds. Each of her reports had the form: "The clockwise distance from station S to a different station T is at most L."

You are given 6 int[]s: s1, t1, l1, s2, t2, l2. For each i, the i-th entries of s1, t1, and l1 describe one of the reports you got from your first friend: the total length of railroad tracks from the station s1[i] to the station t1[i] in clockwise direction is at least l1[i]. Similarly, for each i, the i-th entries of s2, t2, and l2 describe one of the reports you got from your second friend: the total length of railroad tracks from the station s2[i] to the station t2[i] in clockwise direction is at most l2[i].

As stated before, you are interested in finding the total length of the entire circle of railroad tracks. Of course, there can be multiple values consistent with the information your friends gave you. It is also possible that your friends made a mistake and there is no set of segment lengths consistent with the information you received.

Your task is to calculate how many different total lengths of the railway are consistent with the information you received. If the number of possibilities is finite, return it. If there are infinitely many possible total lengths, return -1 instead.

Constraints

n will be between 3 and 50, inclusive.
s1, t1, and l1 will contain the same number of elements.
s2, t2, and l2 will contain the same number of elements.
s1 and s2 will each contain between 0 and 50 elements, inclusive.
Each element of s1, t1, s2, and t2 will be between 0 and n-1, inclusive.
Each element of l1, l2 will be between 1 and 10^9, inclusive.
For each i, the i-th element of s1 and the i-th element of t1 will not be equal.
For each i, the i-th element of s2 and the i-th element of t2 will not be equal.

Examples

3
{}
{}
{}
{0,1,2}
{1,2,0}
{1,1,1}
Returns: 1

The input tells us that each of the distances "from 0 to 1", "from 1 to 2", and "from 2 to 0" is at most 1. But as we know, the length of each track segment is a positive integer. Therefore, each of the three segments has length exactly 1. Hence, there is only one possibility: the total length of the Yamanote line is 1+1+1 = 3.

3
{}
{}
{}
{0,1,2}
{1,2,0}
{2,2,2}
Returns: 4

Each direct track segment can have a length of 1 or 2, so the possible total lengths are 3, 4, 5, or 6.

3
{}
{}
{}
{0,1,2}
{2,0,1}
{3,3,3}
Returns: 2

At most one of the three direct track segments can have a length of 2.

4
{0,1,2,3}
{2,3,0,1}
{3,4,4,3}
{1,3}
{3,1}
{5,5}
Returns: 4

4
{0,2}
{2,0}
{5,5}
{1,3}
{3,1}
{4,4}
Returns: 0

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class YamanoteLine with a public method long long howMany(int n, vector<int> s1, vector<int> t1, vector<int> l1, vector<int> s2, vector<int> t2, vector<int> l2) · 106 test cases · 2 s / 256 MB per case