PROBLEM LINK:
Author: Vitalij Kozhukhivski
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basics like iterating loops in any programming language.
PROBLEM:
Given a piano keyboard which contains 12 * N keys, and a pattern to play. If you are currently at xth key, then if you encounter ‘S’ in the pattern you should move to x + 1th key, else if you encounter a ‘T’ in the pattern then you should move to x + 2th key. You can start playing from any of the 12 * N keys. In one play, you can repeat the pattern as many times as you want, but you cannot go outside the keyboard.
You are asked to calculate number of different plays that can be performed. Two plays differ if and only if they start at different keys or patterns are repeated different number of times.
EXPLANATION:
Direct brute-force would pass for this question, find out how many times you can repeat the pattern from each starting position and add it to the answer.
C++ Code
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
// we use 'cas' because 'case' is a keyword
int N;
string s;
cin >> s;
cin >> N;
int ans = 0;
for(int x, y, sp = 0; sp < 12 * N; sp++){
y = sp;
while(true){
x = y;
for(int i = 0; i < s.length(); i++){
x += s[i] - 'R';
}
if(x >= 12 * N){
break;
}
y = x;
ans++;
}
}
cout << ans << ’\n’;
}
}
Complexity : O( N * N * T * |S|)
We can have one optimization like this, rather than iterating through S every time we can do it only once in the beginning and store how much x is incremented in each complete play.
That brings the complexity down to O(N * N * T).
ALTERNATIVE SOLUTION:
We can iterate through number of times the pattern is repeated and find out how many starting positions can be possible for each respective number of repetitions.
One observation we can make here is, if we have the length of play, then number of starting positions will be 12 * N – L, where L is the length of the play. It is easy to prove it, reader is encouraged to prove it.
C++ Code
#include <iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
// we use 'cas' because 'case' is a keyword
int N, l = 0;
string s;
cin >> s;
cin >> N;
int ans = 0;
for(int i = 0; i < s.length(); i++){
l += s[i] - 'R';
}
for(int p = l; p < 12 * N; p += l){
ans += 12 * N - p;
}
Cout << ans << ’\n’ ;
}
}
Complexity : O(T * N / S)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution