NINJA1 - Related or not

no tags 

You are given two DNA sequences A and B. It is said that these two DNA sequences are related if there exists a non-decreasing sequence C of the same length, such that Ci = Ai or Ci = Bi. Find if the given sequences are related.

Input format:

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

For each test case:

The first line contains an integer, N, the length of the DNA sequence.

The second line contains a sequence of space-separated integers describing species A.

The third line contains a sequence of space-separated integers describing species B.

Output Format

On a new line for each test case, print YES if a non-decreasing sequence of the same length can be found or NO if it cannot.

Constraints:

1 ≤ T ≤ 5

1 ≤ N ≤ 105

0 ≤ Ai, Bi ≤ 1010

Sample:

Input
3
3
1 2 3
4 4 4
3
3 2 1
6 5 4
2
1 0
10 2

Input
YES
NO
YES

hide comments
nadstratosfer: 2017-10-05 08:10:23

Statement doesn't make sense. If it's "Ci = Ai or Ci = Bi", then it's enough to find a sequence matching just one value on same index of either A or B. If on the other hand, "Ci = Ai *and* Cj = Bj for distinct i,j" then sequence (3,5,7) relates A and B in example case 2. Please clear this up.

Edit: For each i in range (0, n) choose either Ai or Bi such that a sequence constructed this way be non-decreasing.

Last edit: 2018-04-25 15:43:28
namitp: 2017-07-29 09:09:36

Equality Costed me 1 WA....

bsiddhartha: 2017-06-18 12:10:04

@pavan_kumar1
1. non decreasing seq C of the same length(n),
2. Ci = Ai or Ci = Bi

pavan_kumar1: 2017-06-17 15:04:08

not enough explanation.... :-(

prakash: 2016-12-30 16:43:07

simple one

vengatesh15: 2016-12-30 13:54:21

Silly mistake cost me 3WA

Mayank Garg: 2016-06-06 15:50:00

Easy one ... My 350th Green :-)

akshayvenkat: 2016-05-30 08:55:39

O(n) with a little attention to "non decreasing sequence" -> AC

Dushyant Singh: 2016-03-20 04:52:51

@tamaghna - Because C is 1, 2 ( 1 from first sequence and 2 from second sequence).

tamaghna: 2016-03-19 21:57:20

why ,it is yes in third case,can anyone explain please!


Added by:mombassa
Date:2016-02-17
Time limit:1s-1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY