PROBLEM STATEMENT
Consider a string T containing exactly L characters. The string T(i) is a cyclic shift of T
starting from position i (0 <= i < L). T(i) contains exactly the same number of characters as T.
For each j between 0 and L-1, inclusive, character j of T(i) is equal to character (i+j)%L of T.
Let's call T a magic word if there are exactly K positions i such that T(i) = T.
You are given a vector S containing exactly N words. For each permutation p = (p[0],
p[1], ..., p[N-1]) of integers between 0 and N-1, inclusive, we can define a string generated by
this permutation as a concatenation S[p[0]] + S[p[1]] + ... + S[p[N-1]]. Return the number of
permutations that generate magic words. All indices in this problem as 0-based.
DEFINITION
Class:MagicWords
Method:count
Parameters:vector , int
Returns:int
Method signature:int count(vector S, int K)
CONSTRAINTS
-S will contain between 1 and 8 elements, inclusive.
-Each element of S will contain between 1 and 20 characters, inclusive.
-Each element of S will contain only uppercase letters ('A'-'Z').
-K will be between 1 and 200, inclusive.
EXAMPLES
0)
{"CAD","ABRA","ABRA"}
1
Returns: 6
Every permutation generates a magic word here.
1)
{"AB","RAAB","RA"}
2
Returns: 3
The magic words are "ABRAABRA" and "RAABRAAB". The first word is generated only by the permutation
(0, 1, 2), and the second word is generated by the two permutations (1, 2, 0) and (2, 0, 1).
2)
{"AA","AA","AAA","A"}
1
Returns: 0
All permutations generate the string "AAAAAAAA" and it clearly is not a magic word because all its
cyclic shifts are the same as the original string.
3)
{"AA","AA","AAA","A","AAA","AAAA"}
15
Returns: 720
4)
{"ABC","AB","ABC","CA"}
3
Returns: 0
5)
{"A","B","C","A","B","C"}
1
Returns: 672
6)
{"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAB"}
1
Returns: 40320
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)2010, TopCoder, Inc. All rights reserved.