20. LETTER ROTATOR — TASK SOLUTION
In this task, every time a key is pressed, the first letter of every word is moved to the end of that word. We need to find the smallest positive number of key presses after which the whole text returns to its initial state. The key to the problem is to find the smallest period of every word, and then compute the least common multiple (LCM) of these periods.
The task is part of the preparation for the informatics competition. See also the page Preparation for the national informatics competition, where the task is given.
Task text
When a key on the keyboard is pressed, the first letter of every word in the text is moved to the last place of that word. Find how many times the key must be pressed for the sentence to return to its initial state.
Input:
One line of text consisting of lowercase letters of the English alphabet and spaces is read
from standard input. The text can have at most 106 characters. It is guaranteed that the
sentence returns to its original state after at most 1018 key presses.
Output:
Print the smallest number of key presses, greater than zero, needed for the sentence
to return to its original state.
Example 1
Input: (Serbian for "the little mermaid lives at the bottom of the sea")
mala sirena zivi na dnu mora
Output:
12
Explanation:
After every key press the first letter of every word moves to the end of that word. After 12 presses
every word gets its initial form again.
mala sirena zivi na dnu mora
alam irenas iviz an nud oram
lama renasi vizi na udn ramo
amal enasir iziv an dnu amor
mala nasire zivi na nud mora
alam asiren iviz an udn oram
lama sirena vizi na dnu ramo
amal irenas iziv an nud amor
mala renasi zivi na udn mora
alam enasir iviz an dnu oram
lama nasire vizi na nud ramo
amal asiren iziv an udn amor
mala sirena zivi na dnu mora
Example 2
Input: (Serbian for "sixth, seventh and eighth graders love informatics")
sestaci sedmaci i osmaci vole informatiku
Output:
924
Example 3
Input:
dada tata i mama
Output:
2
Note: In 50% of the test cases the words are not periodic. In 60% of the test cases all words are shorter than 100 characters.
Idea of the solution
One key press is a rotation of the word to the left by one place. If the word consists of repetitions of a shorter block, we do not have to move the letters as many times as the word has characters. It is enough to rotate by the length of that shortest block.
For example, the word damdam has six characters, but the block dam
is repeated twice. After three rotations the word returns to its initial state:
damdam
amdamd
mdamda
damdam
That is why the period of the word damdam is 3, not 6. For a word without a shorter repeating
block, for example mala, the period is the length of the whole word, that is 4.
Every word has its own smallest period. For the whole text to return to its initial state, the number of key presses must be divisible by the period of every word. That is why we look for the LCM of all smallest periods.
What is not good in the original implementation?
The basic idea of the original solution — finding the shortest repeating block and then
computing the LCM — is good. However, the implementation uses the type int for the LCM and the
intermediate products. Since according to the task the result can get close to
1018, such a type can overflow and produce a wrong result.
In addition, checking candidates by extracting substrings repeats comparisons unnecessarily.
This can be sped up using the prefix function: for every word it finds the
smallest period in linear time. Below is an optimized version that uses
long long to compute the LCM.
Optimized C++ solution
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
// Euclid's algorithm: returns the greatest common divisor of two numbers.
long long gcd(long long a, long long b) {
while (b != 0) {
long long remainder = a % b;
a = b;
b = remainder;
}
return a;
}
// Returns the smallest period of a word: the length of the shortest block
// which, repeated, gives the whole word.
int smallestPeriod(const string& word) {
int n = static_cast<int>(word.size());
vector<int> pi(n, 0);
// Prefix function (KMP): pi[i] is the length of the longest
// proper prefix of word[0..i] that is also its suffix.
for (int i = 1, j = 0; i < n; ++i) {
while (j > 0 && word[i] != word[j]) {
j = pi[j - 1];
}
if (word[i] == word[j]) {
++j;
}
pi[i] = j;
}
// The candidate period is n - length of the longest prefix-suffix.
int period = n - pi[n - 1];
// The candidate is the period of the whole word only if it divides its length.
if (n % period != 0) {
period = n;
}
return period;
}
int main() {
string text;
getline(cin, text); // Reads the whole sentence, including spaces.
istringstream input(text);
string word;
long long answer = 1;
// We extract the words; operator >> skips extra spaces.
while (input >> word) {
int period = smallestPeriod(word);
// LCM(a, b) = (a / GCD(a, b)) * b.
// We divide before multiplying and use long long because of the large result.
long long divisor = gcd(answer, period);
answer = (answer / divisor) * period;
}
cout << answer << '\n';
return 0;
}
Code explanation
1. Reading the text. The function getline reads the whole line,
so the spaces are not lost. Then istringstream extracts the words one by one.
2. Finding the period of a word. The function smallestPeriod computes
the prefix function. From the value of the last element we get the candidate
n - pi[n - 1]. If this number does not divide the length of the word, the word does not consist of
repetitions of that block, so its smallest period is the length of the whole word.
3. Combining the periods. The variable answer stores the LCM of the periods of all
words processed so far. For every new word, the LCM of the current answer and its
period is computed using the formula LCM(a, b) = (a / GCD(a, b)) * b.
4. Output. When all words have been processed, answer is the smallest positive
number of key presses that returns every word, and therefore the whole sentence, to its initial state at the same time.
Checking the examples
mala sirena zivi na dnu mora: the smallest periods are 4, 6, 4, 2, 3 and 4; their LCM is 12.sestaci sedmaci i osmaci vole informatiku: the LCM of the periods of all words is 924.dada tata i mama: the wordsdada,tataandmamahave period 2, and the wordihas period 1; the result is 2.
Complexity
The prefix function processes every character of a word a constant number of times. That is why the total
complexity of finding the periods is O(n), where n is the number of characters
in the text. The prefix function uses additional memory proportional to the length of the longest
word. The LCM is computed with Euclid's algorithm, and the result is stored in the type
long long, which can represent the required limit of 1018.
Conclusion: We do not have to simulate every key press. It is enough to find the smallest period of every word and compute the LCM of these periods. This avoids a potentially huge number of steps, and the solution remains efficient even for long texts.
Back
|<
Preparation for the national informatics competition
