WalkingToSchool
SRM 668 · 2015-08-31 · by zxqfl
SRM 668 · 2015-08-31 · by zxqfl · Dynamic Programming, Graph Theory, Math
Problem Statement
Problem Statement
Little Liz lives on a graph with N vertices, which are numbered from 0 to N-1. For each valid i, a directed edge goes from vertex from[i] to vertex to[i]. Little Liz's house is on vertex 0 and her school is on vertex 1. Little Liz wants to walk from her home to her school and back. Little Liz knows that it is often wise to arrive neither too late nor too early. For example, if she arrives late to school, she is scolded by her teacher. But if she arrives early to school, it is a waste of time because she could have awoken later. Likewise, arriving late home causes her to miss dinner, but if she arrives early, her parents will give her chores.
For these reasons, Little Liz has defined a k-walk as a walk which uses exactly k edges. (A single edge is counted more than once if it is used more than once.) A k-route has two parts: a k-walk which starts at vertex 0 and ends at vertex 1, and a k-walk which starts at vertex 1 and ends at vertex 0. Note that the two k-walks are allowed to visit vertices 0 and 1 arbitrarily many times. (Liz just passes by her house / her school without going inside.)
Please determine whether there exists a k-route for all sufficiently large k. If there exists a k-route for all sufficiently large k, return "Freedom". Otherwise, return "Chores". In other words, return "Chores" if one can find an arbitrarily large k such that there is no k-route in the given graph.
For these reasons, Little Liz has defined a k-walk as a walk which uses exactly k edges. (A single edge is counted more than once if it is used more than once.) A k-route has two parts: a k-walk which starts at vertex 0 and ends at vertex 1, and a k-walk which starts at vertex 1 and ends at vertex 0. Note that the two k-walks are allowed to visit vertices 0 and 1 arbitrarily many times. (Liz just passes by her house / her school without going inside.)
Please determine whether there exists a k-route for all sufficiently large k. If there exists a k-route for all sufficiently large k, return "Freedom". Otherwise, return "Chores". In other words, return "Chores" if one can find an arbitrarily large k such that there is no k-route in the given graph.
Notes
- The statement "there exists a k-route for all sufficiently large k" is true if and only if there is some integer x such that there exists a k-route for all k greater than x.
Constraints
- N will be between 2 and 2000, inclusive.
- M will be between 0 and 2000, inclusive.
- from will contain exactly M elements.
- to will contain exactly M elements.
- Each element of from will be between 0 and N-1, inclusive.
- Each element of to will be between 0 and N-1, inclusive.
- The edges will be distinct.
- No edge will connect a vertex to itself.
Examples
0)
2
{0, 1}
{1, 0}
Returns: "Chores"
Little Liz's path could use any odd number of edges, but it can never use an even number of edges.
1)
3
{0, 1, 1, 2}
{1, 0, 2, 0}
Returns: "Freedom"
2)
4
{0, 2, 2, 3, 0}
{2, 0, 3, 0, 1}
Returns: "Chores"
In this test case, there exists a k-walk from vertex 0 to vertex 1 for all sufficiently large k, but there is not a k-walk from vertex 1 to vertex 0 for all sufficiently large k.
3)
10
{0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 8, 9, 9, 9, 9}
{4, 5, 6, 7, 9, 4, 6, 0, 1, 3, 8, 4, 6, 1, 4, 8, 1, 7, 8, 1, 4, 2, 5, 6, 8}
Returns: "Chores"
4)
8
{0, 1, 4, 6, 7, 5, 2, 3, 0}
{1, 4, 6, 7, 5, 2, 3, 0, 7}
Returns: "Freedom"
Submissions are judged against all 66 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WalkingToSchool with a public method string canWalkExactly(int N, vector<int> from, vector<int> to) · 66 test cases · 2 s / 256 MB per case