ScoresSequence
SRM 717 · 2017-05-20 · by Arterm
Problem Statement
A tournament is a directed graph on n vertices that can be obtained by taking an undirected complete graph on n vertices and assigning a direction to each edge. The outdegree of a vertex is the number of directed edges that start at that vertex. The score of a tournament is the list of the outdegrees of its vertices, in no particular order.
Alice used to have a tournament T but she lost it.
She only remembers its score.
You are given the score of T in the
Determine and return the number of pairs of vertices (u,v) such that in the tournament T the vertex v was reachable from the vertex u. Note that each vertex is reachable from itself.
You may assume that the answer can always be uniquely determined.
Constraints
- s will contain between 1 and 100 elements, inclusive.
- s will be a valid score of some tournament.
{2, 0, 1}
Returns: 6
There are three vertices. Let's call them A, B, and C, in the order in which they are mentioned in the score. As the outdegree of A is 2, the tournament must contain the edges A -> B and A -> C. As the outdegree of B is 0, the tournament must also contain the edge C -> B. There are six pairs of vertices (u,v) such that there is a path from u to v. These are the pairs (A,A), (B,B), (C,C), (A,B), (A,C), and (B,C).
{1, 0, 2}
Returns: 6
{1, 1, 1}
Returns: 9
This tournament must clearly be a cycle. Hence, each vertex is reachable from each vertex.
{2, 0, 1}
Returns: 6
{8, 0, 2, 4, 7, 5, 3, 1, 9, 6}
Returns: 55
Submissions are judged against all 169 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ScoresSequence with a public method int count(vector<int> s) · 169 test cases · 2 s / 256 MB per case