PIANO1 - Editorial

PROBLEM LINK:

Practice
Contest

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

RELATED PROBLEMS:

If we go by the alternative solution and take a case say : “S”
We get length of the pattern as “1” but since we need to press 2 keys: x(letter ‘S’)-> x + 1.
So length of pattern will be and has to be 2.
Please correct me If I am wrong?

@thakursc1
u didnt get the question correct.

#thakursc1
this would help…

while(t–)
{
int n;
long long int ans=0,count=0;
string s;
cin>>s;
cin>>n;
for(int i=0;i<s.size();i++)
if(s[i]==‘T’)
count=count+2;
else
count++;

int mx=n*12;

        while(mx-count>0)
        {
        mx=mx-count;
        ans=ans+mx;
        }

Can anyone help me with this solution. Getting WA and couldn’t differentiate between the logic used here.

@drgn_hart

You are doubling your pattern_value on each iteration. You need to increment it.

1 Like

So, the problem description says:

  1. 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.

  2. that two plays differ if and only if they start at different keys or patterns are repeated different number of times…

Looking at a single octave, as in the first sample case:

case 0: tune TTTT, 1 octave scale: c C# d D# e f F# g G# a A# b
Possible melodies starting at different keys in the same octave using "TTTT":
 c d e F#   (1)
 C# D# f g  (2)
 d e F# G#  (3)
 D# f g a   (4)
 e F# G# A# (5)
 f g a b    (6)
Ways: 6

So, how does the sample output show that there will only be 4 ways for this case? Each play above starts on a different key on the keyboard and has no repeats – in fact, all 6 plays are 100% valid based on the problem definition as written. Either your the definition is incomplete, or the sample ‘correct’ solution has issues.

Your explanation:

“Example case 1. In the first case there is only one octave and Chef can play scale (not in cycle each time) starting with notes C, C#, D, D# - four together.”

misses the last two cases in the octave.

4 Likes

Terima kasih dan salam kenal.
codechef Link

code Link

linear time solutiuon

import java.util.Scanner;

class Piano {

/**
 * @param args
 */
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	for (int i = 0; i < t; i++) {

		int S = 0;
		int T = 0;
		String s = sc.next();
		int n = sc.nextInt();
		for (int j = 0; j < s.length(); j++) {
			if (s.charAt(j) == 'T')
				T = T + 2;

			else
				S++;

		}
		int l= T + S;
		int sum = l;
		
		//System.out.println("SUM " + sum);
		int r = 0;
		int keys = n * 12;
		r=keys%sum;
		//System.out.println("keys " + keys);
		int ans = 0;
		
		int q=keys/sum;
		if(r==0)q--;
		//System.out.println(q);
		for (int j = 1; j <= q; j++) {
			if(sum<=keys){
			ans+=keys-sum;
			//System.out.println(ans);
			}
			sum+=l;
			//System.out.println("s"+sum);
			
		}

System.out.println(ans);

	}

}

}

1 Like

why <12N when the ques says <=12N why ? why ?

ohh! Didn’t realize that. Thank you

Why do you even need loops for this? This can be solved by simple formula.

k = number of keys needed (TTSTTTS needs 13)
o = total number of keys we are given (12*n)
r = number of times our pattern can be repeated

For the first time, we will need k keys. But, for each repetition, we will need k-1 keys (as we can start the first repetition from kth key now).
This way we can calculate r.

Now, for each value of our scale repetition (r=1 means that it is not repeated), we can calculate number of plays as:
r==1 => o - (1*k - 0) + 1
r==2 => o - (2*k - 1) + 1
r==3 => o - (3*k - 2) + 1

Sum: r*o - (r(r+1)/2*k - (r-1)r/2) + r

My solution: CodeChef: Practical coding for everyone

Correct me if I am wrong.

i literally didn’t understand the Question

1 Like