RecursiveTournament | Topcoder Archive

Problem Statement

A tournament graph is a graph where every pair of distinct nodes has a single directed edge between them. Consider a touranment graph with b nodes such that the nodes are labeled with the digits of the base b. For example, if b=3, then there would be three nodes, labeled 0, 1, and 2. You are given this tournament graph in the String[] graph. graph has exactly b strings each of length b. The j-th character in the i-th string is 'Y' if there exists a directed edge from node i to node j, and 'N' otherwise. It's guaranteed that the given graph is a valid tournament graph.

You are given a int k. Consider a tournament graph in which there are b^k nodes labeled with integers from 0 to b^k-1 for a given k. To determine which way the directed edge between any two nodes x and y of this big graph points, relate it back to the input graph described above. Consider the values of x and y in base b with exactly k digits, padding the left with leading zeros if necessary. Find the leftmost digit that differs between x and y. The direction of the edge between those two digits in the input graph determines the direction of the edge between x and y in the big graph.

For example, if b=3 and k=4, then consider the nodes 1 and 6. 1 in base 3 with 4 digits is 0001, and 6 in base 3 with 4 digits is 0020. The leftmost digit in which they differ is the third digit from the left, so the edge between 1 and 6 in the big graph would have the same direction as the edge between 0 and 2 in the input graph.

An induced subgraph of a graph is a subset of its nodes along with all the edges between those nodes. A non-empty graph is strongly connected if it contains directed paths from every node to every other node. In particular, a graph with a single node is considered strongly connected. Given the input graph and number k, how many non-empty strongly connected induced subgraphs are there in the big tournament graph? Since this number can get very large, return it modulo 998244353.

Definition

Class:: RecursiveTournament
Method:: count
Parameters:: String[], int
Returns:: int
Method signature:: int count(String[] graph, int k)
(be sure your method is public)

Constraints

b will be between 3 and 23.
graph will have exactly b elements.
Each element of graph will have exactly b characters, each of which is either 'Y' or 'N'.
graph describes a valid tournament graph.
k will be between 1 and 1000.

Examples

```
{
"NYN",
"NNY",
"YNN"
}
```
```
2
```
```
Returns: 355
```
```
{
"NYY",
"NNY",
"NNN"
}
```
```
2
```
```
Returns: 9
```
```
{
"NYN",
"NNY",
"YNN"
}
```
```
1
```
```
Returns: 4
```

{
"NYYYNNYNNYYNNYYYYYNNYNN",
"NNYNYYNYYNNNYNYNYNNNNYY",
"NNNNYNNNNYNYYNYYNYYNYNN",
"NYYNYNNNYNNYYYNYYYNNYYN",
"YNNNNNYYNYNNYYNNYNYNYYY",
"YNYYYNNNYNYNYNYNNYNYNYN",
"NYYYNYNNNYYNNNNYNNNNYNN",
"YNYYNYYNYYYNYNYYYNYNNYY",
"YNYNYNYNNYYYNYNYNYYYNYN",
"NYNYNYNNNNYNYYYNNYYYNYN",
"NYYYYNNNNNNNNYNYYNNYNYN",
"YYNNYYYYNYYNNYYYYNYYYNY",
"YNNNNNYNYNYYNNNNYNYNYNY",
"NYYNNYYYNNNNYNYNNNNYNYN",
"NNNYYNYNYNYNYNNYNNNYNNY",
"NYNNYYNNNYNNYYNNYNYYNYN",
"NNYNNYYNYYNNNYYNNNYNNNN",
"NYNNYNYYNNYYYYYYYNYYYNN",
"YYNYNYYNNNYNNYYNNNNNYNY",
"YYYYYNYYNNNNYNNNYNYNYNN",
"NYNNNYNYYYYNNYYYYNNNNNY",
"YNYNNNYNNNNYYNYNYYYYYNY",
"YNYYNYYNYYYNNYNYYYNYNNN"
}

Returns: 71573222

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.