Connection Status:
Competition Arena > MagicWords

MagicWords

SRM 433 · 2009-01-21 · by gojira_tc

SRM 433 · 2009-01-21 · by gojira_tc · Brute Force, String Manipulation
Class Name: MagicWords
Return Type: int
Method Name: count
Arg Types: (vector<string>, int)
Problem Statement

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 String[] 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.

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.

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

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)
{"BA","BC","BAC","C","BC"}
2
Returns: 10

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

Coding Area

Language: C++17 · define a public class MagicWords with a public method int count(vector<string> S, int K) · 190 test cases · 2 s / 256 MB per case

Submitting as anonymous