| Submit | All submissions | Best solutions | Back to list |
NINJA1 - Related or not |
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 Output: YES NO YES
| 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 |
hide comments
|
|||||
|
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 |
|||||
|
2017-07-29 09:09:36
Equality Costed me 1 WA.... |
|||||
|
2017-06-18 12:10:04
@pavan_kumar1 1. non decreasing seq C of the same length(n), 2. Ci = Ai or Ci = Bi |
|||||
|
2017-06-17 15:04:08
not enough explanation.... :-( |
|||||
|
2016-12-30 16:43:07 prakash
simple one |
|||||
|
2016-12-30 13:54:21
Silly mistake cost me 3WA |
|||||
|
2016-06-06 15:50:00 Mayank Garg
Easy one ... My 350th Green :-) |
|||||
|
2016-05-30 08:55:39
O(n) with a little attention to "non decreasing sequence" -> AC |
|||||
|
2016-03-20 04:52:51 Dushyant Singh
@tamaghna - Because C is 1, 2 ( 1 from first sequence and 2 from second sequence). |
|||||
|
2016-03-19 21:57:20
why ,it is yes in third case,can anyone explain please! |
|||||
RSS