Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bangladesh Has Got Talent

By kitorp · Limits 1s, 512 MB

In music, there are 12 notes. In sequence, they are A, A#, B, C, C#, D, D#, E, F, F#, G, G# . Every song is played in a scale and it consists of many notes. One song can be played in different scales. We can also tune the scale up or down of a particular song. After G#, again comes A and vice versa. Suppose , a song is written in G scale and The notes are G, F, A#, E, D, G.

Now, if we tune down the song one step we get: F#, E, A, D#, C#, F#.

If we tune down the song two step we get: F, D#, G#, D, C, F.

If we tune up the song one step we get: G#, F#, B, F, D#, G#.

Now two strings will be given. One is the original string and other one is the given string. Strings are composed of notes. You have to tell weather you can get the original string or a sub-string of the original string by tuning up or down the given string.


The first line will contain an integer T, the number of test cases.

Each case will start with two integers. The number of notes in the original string and the number of notes in the given string. Then there will be two strings. The first string is the original string and second string is the given string.



n denotes the length of the original string.
m denotes the length of the given string.


For each case, print "Case #: " and then "yes" , if we can get the original string or "no" if we can't, in a line. Here # represents the case number. See the sample input and output for details.


5 5
A A# B C C#
A A# B C C#
6 3
G A C C# D F
B D D#
7 4
A B C D# E F G 
G A G G#
Case 1: yes
Case 2: yes
Case 3: no



84% Solution Ratio

RezwanArefin01Earliest, Dec '18

ShadowMeFastest, 0.2s

ovis96Lightest, 393 kB

prishan076Shortest, 1357B


Login to submit


To solve this problem, we need to check for all the variations(scales) of the given string. There ar...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.