Subgraphs
SRM 730 · 2018-02-19 · by lg5293
Problem Statement
You are given an
More precisely, your graph must satisfy the following:
- The number n of nodes must be between 1 and 46, inclusive.
- The nodes must be labeled from 0 to n-1.
- The graph must be a simple undirected graph. (I.e., there cannot be any self-loops or multiple edges.)
- For every number x between 0 and k*(k-1)/2, inclusive, there must be a way to choose exactly k nodes so that there will be exactly x edges between them.
Return a
- The first n elements of the return value should contain the adjacency matrix of your graph. Character j of element i of the return value should be '1' of nodes i and j are connected by an edge and '0' if they aren't. Note that the main diagonal of the adjacency matrix must contain only '0's.
- The remaining k*(k-1)/2 + 1 elements of the return value should describe the subsets of nodes that correspond to the last constraint the graph should satisfy. More precisely, the i-th of these
String s (0-based index) describes one set of k nodes such that the subgraph induced by these nodes contains exactly i edges. Encode the subset as aString of length n: character j of this string should be 'Y' if node j belongs into the subset and 'N' otherwise.
You may assume that there is always a graph with the desired properties. If there are multiple correct answers, you may return any of them.
Constraints
- k will be between 2 and 23, inclusive.
2
Returns: {"010", "100", "000", "NYY", "YYN" }
The returned graph has three nodes and only one edge: (0,1). The first set of nodes are the nodes {1,2}. There are no edges between these nodes. The second set of nodes are the nodes {0,1}. The corresponding subgraph contains one edge. Note that each node may appear in arbitrarily many of these sets.
3
Returns: {"000000000000", "000000000000", "000000000000", "000010000000", "000100000000", "000000000000", "000000011000", "000000100000", "000000100000", "000000000011", "000000000101", "000000000110", "YYYNNNNNNNNN", "NNNYYYNNNNNN", "NNNNNNYYYNNN", "NNNNNNNNNYYY" }
The graph described by the example return value has 12 nodes. It contains the following edges: (3,4), (6,7), (6,8), (9,10), (9,11), and (10,11). The sets of nodes described by the example return value are the following ones: The set {0,1,2} with 0 edges among these nodes. The set {3,4,5} with 1 edge among these nodes: the edge (3,4). The set {6,7,8} with 2 edges among these nodes: (6,7) and (6,8). The set {9,10,11} with 3 edges among these nodes: the remaining three edges.
4
Returns: {"01111000", "10111100", "11011110", "11101111", "11110000", "01110000", "00110000", "00010000", "YNNNNYYY", "YYNNNNYY", "YNYNNNYY", "YNYNNYYN", "YNYNYYNN", "YNYYNYNN", "YYYYNNNN" }
5
Returns: {"0111110000", "1011111000", "1101111100", "1110111110", "1111011111", "1111100000", "0111100000", "0011100000", "0001100000", "0000100000", "YNNNNNYYYY", "YNNNNYYYYN", "NYNNNYYYYN", "NNYNNYYYYN", "YNYNNYYNYN", "YYYNNNYNYN", "YYYNNNYYNN", "YNYNYNYYNN", "YYYNYNNYNN", "YNYYYNNYNN", "YYYYYNNNNN" }
6
Returns: {"011111100000", "101111110000", "110111111000", "111011111100", "111101111110", "111110111111", "111111000000", "011111000000", "001111000000", "000111000000", "000011000000", "000001000000", "NNNNNNYYYYYY", "NYNNNNYNYYYY", "NYNNNNYYYNYY", "NNNYNNYYYNYY", "YNNYNNYYNNYY", "YNNYNNYYYNNY", "YYNYNNNYYNNY", "YNYYNNNYYNNY", "YNYYNNNYYYNN", "YNYYNNYYNYNN", "YNNYNYYYNYNN", "YNYYNYNYNYNN", "YNYYNYNYYNNN", "NYYYNYNYYNNN", "NYYYYYNNYNNN", "YYYYYYNNNNNN" }
Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Subgraphs with a public method vector<string> findGroups(int k) · 22 test cases · 2 s / 256 MB per case