RingLex
SRM 731 · 2018-03-16 · by subscriber
SRM 731 · 2018-03-16 · by subscriber · Brute Force, Simple Search, Iteration, String Manipulation
Problem Statement
Problem Statement
Hero has an infinite periodic string t.
You are given the String s that is the period of Hero's string.
For example, if s = "abc", Hero's actual string is t = "abcabcabcabc..."
Let n be the length of string s.
Hero is now going to use the infinite string t to generate a new n-character string by doing the following steps:
- He will choose an offset: a non-negative integer x.
- He will choose the length of a step: a prime number p that is less than n.
- The new string will consists of the first n characters we can read in the string t if we start at the index x and after each character we move p positions to the right.
Notes
- Given two distinct strings of the same length, the lexicographically smaller one is the one that has a smaller character at the first position where they differ.
- A positive integer p is a prime if it has exactly two distinct divisors: 1 and p. Note that the number 1 is not a prime.
Constraints
- s will contain between 3 and 50 characters, inclusive.
- Each character in s will be between 'a' and 'z', inclusive.
Examples
0)
"cba" Returns: "abc"
Hero should choose the offset x=2 and the step p=2. The resulting string is t[2]+t[4]+t[6] = 'a'+'b'+'c' = "abc".
1)
"acb" Returns: "abc"
Here, Hero should choose x=0 and p=2.
2)
"abacaba" Returns: "aaaabcb"
3)
"aaabb" Returns: "aabab"
4)
"azzzabbb" Returns: "abazabaz"
Note that Hero cannot choose x=0 and p=4, because 4 is not a prime number.
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RingLex with a public method string getmin(string s) · 51 test cases · 2 s / 256 MB per case