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.
- 1 ≤ T ≤ 105
- 2 ≤ N ≤ 105
- 1 ≤ a_i ≤ 109
- 1 ≤ Length of Message Pattern ≤ N-1
For each test case print 'YES' if the pattern estimation is correct. Else print 'NO'.
Input: 1 5 1 2 3 4 1 GGL Output: YES
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.
KMP really rocks...!!!
AC IN 1 GO.
Last edit: 2018-03-13 15:22:27
if you are getting TLE with strings in c++, pick c++ 14 (6.3) as your language.
KMP rocks ;)
working with string causes TLE whereas array of char works perfectly
Easy one AC in 1 go ☺️☺️
AC in one go .. ;)
one go AC :)Last edit: 2015-04-02 20:26:46