SnowStorm

TCCC06 Spon 1 · 2006-08-22 · by Cosmin.ro

TCCC06 Spon 1 · 2006-08-22 · by Cosmin.ro · Brute Force, Dynamic Programming

Show categories

Class Name: SnowStorm

Return Type: int

Method Name: countWays

Arg Types: (vector<string>)

Problem Statement

Last night in Eskimo village it snowed heavily, so all the paths between the different igloos have been covered with snow. The mayor wants to help keep the community together and clean up the snow so that you can reach every igloo from all other igloos.

You are given a String[] paths, where character j of element i is 'Y' if there's a path between the ith igloo and the jth igloo, or 'N' otherwise. All paths are bidirectional. Determine the number of different sets of paths that can be cleaned to achieve the mayor's goal, and return this number modulo 10,000.

Constraints

paths must have between 1 and 15 elements, inclusive.
Each element of paths must have exactly n characters, where n is the number of elements of paths.
Each character in paths must be either 'Y' or 'N'.
Character i of element i of paths will always be 'N'.
Character j in row i of paths will be equal to character i in row j of paths.

Statement by TopCoder, Inc. — view the original on the archive.

Examples

{
 "NYY",
 "YNY",
 "YYN"}
Returns: 4

There are 4 different snow clearing possibilities: - clear the paths 1-2 and 2-3. - clear the paths 1-3 and 2-3. - clear the paths 1-3 and 1-2. - or clear the paths 1-2, 1-3, 2-3.

{
 "NYNN",
 "YNYY",
 "NYNN",
 "NYNN"}
Returns: 1

To be able to get from every igloo to any other igloo, we must clear all the paths. So the number of solutions is 1.

{
 "NYYY",
 "YNYY",
 "YYNY",
 "YYYN"}
Returns: 38

{
 "NN",
 "NN"}
Returns: 0

There are no paths to be cleaned, and you can't reach igloo 2 from igloo 1, so the number of solutions is 0.

{ "NYYYNYYYYYNYYYY",
 "YNYYYYYYYNNYYYY",
 "YYNYYNYYNYYYYYY",
 "YYYNYYYYYYNNNYN",
 "NYYYNNYYYYYYYYY",
 "YYNYNNYYYYYYYYY",
 "YYYYYYNYYYYYYYY",
 "YYYYYYYNYNYYYYY",
 "YYNYYYYYNYNYYYY",
 "YNYYYYYNYNYYYYY",
 "NNYNYYYYNYNYYYY",
 "YYYNYYYYYYYNYYY",
 "YYYNYYYYYYYYNNY",
 "YYYYYYYYYYYYNNY",
 "YYYNYYYYYYYYYYN"}
Returns: 2704

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

Coding Area

Language: C++17 · define a public class SnowStorm with a public method int countWays(vector<string> paths) · 54 test cases · 2 s / 256 MB per case