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.
Input
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.
- 1 ≤ T ≤ 105
- 2 ≤ N ≤ 105
- 1 ≤ a_i ≤ 109
- 1 ≤ Length of Message Pattern ≤ N-1
Output
For each test case print 'YES' if the pattern estimation is correct. Else print 'NO'.
Example
Input: 1 5 1 2 3 4 1 GGL Output: YES
Explanation
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
vl4deee11:
2024-06-27 00:43:29
Z string also got AC |
|
lokesh_2052:
2021-06-20 09:56:38
I used string and got Ac there is no problem in using array of char or string but do not declare any array in loop otherwise you will get tle |
|
it_uchi:
2021-01-03 19:05:20
AC in 1 Go |
|
s_tank00_:
2020-12-28 07:59:42
use array of char otherwise it will give you tle
|
|
sleepy_coder:
2020-06-19 01:43:54
KMP really rocks...!!! |
|
amansahu112:
2020-04-19 20:15:52
AC IN 1 GO.
|
|
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 ☺️☺️ |
Added by: | BLANKRK |
Date: | 2013-11-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Code Weavers 2013 |