Connection Status:
Competition Arena > CubeColoring

CubeColoring

SRM 484 · 2010-03-12 · by rng_58

SRM 484 · 2010-03-12 · by rng_58 · Brute Force, Graph Theory
Class Name: CubeColoring
Return Type: long
Method Name: theCount
Arg Types: (vector<string>)
Problem Statement

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Rabbit Taro wants to color the vertices of a cube. He thinks the cube will be beautiful if:
  • Each vertex is colored by a color that is suitable for it.
  • No two adjacent vertices have the same color.


There are N types of colors. You are given a String[] colors. The j-th color is suitable for the i-th vertex if the j-th character of the i-th element of colors is 'Y'. Return the number of different ways to color the cube.

Notes

  • Two ways are different if there exists an i such that the i-th vertex has a different color in one way than it does in the other way.

Constraints

  • colors will contain exactly 8 elements.
  • Each element in colors will contain between 1 and 32 characters, inclusive.
  • Each element in colors will contain the same number of characters.
  • Each character in colors will be 'Y' or 'N'.
Examples
0)
{"Y", "Y", "Y", "Y", "Y", "Y", "Y", "Y"}
Returns: 0

It's impossible to color the cube by only 1 color.

1)
{"YNNNNNNN", "NYNNNNNN", "NNYNNNNN", "NNNYNNNN", "NNNNYNNN", "NNNNNYNN", "NNNNNNYN", "NNNNNNNY"}
Returns: 1

Color the i-th vertex by the i-th color.

2)
{"YNNYN", "YYYYY", "NYYNY", "YNYYN", "YNNYY", "YNNYY", "NNNYY", "NYYYY"}
Returns: 250
3)
{"YNNYN", "YYYYY", "NNNNN", "YNYYN", "YNNYY", "YNNYY", "NNNYY", "NYYYY"}
Returns: 0

No color is suitable for vertex 2.

4)
{"YNNYNYYYYYNN", "NNNYNYYNYNNY", "YYNNYYNNNYYN", "YYYYYNNYYYNN", "NNNYYYNNYNYN", "YYYNYYYYNYNN", "NNNNNNYYNYYN", "NNYNYYNNYNYY"}
Returns: 611480

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

Coding Area

Language: C++17 · define a public class CubeColoring with a public method long long theCount(vector<string> colors) · 73 test cases · 2 s / 256 MB per case

Submitting as anonymous