TESSER - Finding the Tesserect

Dr. Bruce Banner had estimated a coarse location of Tesseract through gamma radiation emission tracing experiment. It was estimated that Tesseract was hidden somewhere within the Alps mountains. Captain America was given the assignment to look for the Tesseract and bring it back to S.H.I.E.L.D. While roaming through the mountains of Alps, Captain America looked at the height of hills and clicked a panoramic photograph of mountains. This gives an idea of the heights of mountains. Meanwhile Banner was able to determine a continuous pattern of mountains behind which the Tesseract lies and transmitted a message containing the pattern.

The message is a string consisting of characters 'G' , 'L' and 'E' where G means greater, L means less and E means equal. But this estimation is likely to go wrong due to not considering environmental disturbances that may have arisen in the medium during the experiment.

Pattern estimate is correct only if one can find a set of consecutive heights out of the given N heights satisfying the message pattern (if G is first character of the message string then second height should be greater than the first height of the selected set and so on) Captain America seeks your help to find out whether the estimation is correct or wrong so that Captain America could proceed his tasks.


The first line of the input contains an integer T denoting the number of test cases. Each test case consists of 3 lines. The first line of each test case contains a single integer N denoting the number of hills. Second line of each test case consists of N integers (a_1,a_2....a_n), the heights of hills. Third line contains the message pattern.

  • 1T105
  • 2N105
  • 1a_i109
  • 1Length of Message PatternN-1


For each test case print 'YES' if the pattern estimation is correct. Else print 'NO'.


1 2 3 4 1




Answer is "YES", because 2 3 4 1 satisfies GGL pattern, i.e. 3 is greater than 2, 4 is greater than 3, 1 is less than 4.

hide comments
sleepy_coder: 2020-06-19 01:43:54

KMP really rocks...!!!

amansahu112: 2020-04-19 20:15:52


mohityadav7: 2018-03-13 15:22:09

Last edit: 2018-03-13 15:22:27
rohit9934: 2018-01-17 10:21:12

if you are getting TLE with strings in c++, pick c++ 14 (6.3) as your language.

sagar_zhcet: 2017-06-28 11:37:44

KMP rocks ;)

steady_bunny: 2017-06-16 19:16:01

working with string causes TLE whereas array of char works perfectly

vengatesh15: 2017-02-10 09:28:23

Easy one AC in 1 go ☺️☺️

Deepak : 2016-05-19 21:45:22

AC in one go .. ;)

Dushyant Singh: 2015-05-29 11:12:58


Abhilash: 2015-04-02 20:23:55

one go AC :)

Last edit: 2015-04-02 20:26:46

Added by:BLANKRK
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013