ANARC05B  The Double HeLiX
Two ﬁnite, strictly increasing, integer sequences are given. Any common integer between the two sequences constitute an intersection point. Take for example the following two sequences where intersection points are
printed in bold:
 First= 3 5 7 9 20 25 30 40 55 56 57 60 62
 Second= 1 4 7 11 14 25 44 47 55 57 100
You can ‘walk” over these two sequences in the following way:
 You may start at the beginning of any of the two sequences. Now start moving forward.
 At each intersection point, you have the choice of either continuing with the same sequence you’re currently on, or switching to the other sequence.
The objective is ﬁnding a path that produces the maximum sum of data you walked over. In the above example, the largest possible sum is 450, which is the result of adding 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, and 62
Input
Your program will be tested on a number of test cases. Each test case will be speciﬁed on two separate lines. Each line denotes a sequence and is speciﬁed using the following format:
n v1 v2 ... vn
Where n is the length of the sequence and vi is the ith element in that sequence. Each sequence will have at least one element but no more than 10,000. All elements are between 10,000 and 10,000 (inclusive).
The last line of the input includes a single zero, which is not part of the test cases.
Output
For each test case, write on a separate line, the largest possible sum that can be produced.
Sample
Input: 13 3 5 7 9 20 25 30 40 55 56 57 60 62 11 1 4 7 11 14 25 44 47 55 57 100 4 5 100 1000 1005 3 12 1000 1001 0 Output: 450 2100
hide comments
sonali9696:
20161220 09:47:12
Damn! Don't overthink like me. It will cost you too much time. Think like a kid. Very direct 

pratyush2311:
20161212 08:59:38
No Dp. Just simple logic.Think for a while about how to proceed and just implement the logic :) 

surf_excel:
20161205 11:42:58
some testcases are separated by uneven number of spaces. Using split() in java landed me in NZEC couple of times .... changing it to split(" +") made it accepted :) 

jawad_cs:
20161129 10:34:06
guyz don't waste ur time on trying to figure out a DP solution it can be solved in O(n) with simple logic 

caphindsight:
20161025 09:24:14
Btw note to those who get WAs because of the boundary cases. Just append (intersection point) z = max(a.back(), b.back()) + 1 to the end of both sequences, then subtract z from your answer. This way no special code is required for dealing with boundary cases. Last edit: 20161025 09:24:45 

caphindsight:
20161025 09:17:08
I was looking for a DP problem to solve... Stumbled upon this. While it is an OK beginner problem, I hate the tags... No DP required! No binary search required! This problem can be solved by two pointers loop, with O(n) asymptotic complexity. Last edit: 20161025 09:18:21 

rraj001:
20161013 06:22:06
dp+binary serach ! :) 

siddharth_0196:
20161011 17:06:14
Simple logic will work! No DP! Last edit: 20161011 18:58:31 

davidgalehouse:
20161006 04:12:13
Note to C# solvers: input is formatted incorrectly, you should RemoveEmptyEntries if splitting. Last edit: 20161006 04:12:27 

Anonomous:
20161002 15:53:23
Be careful, some of the test cases are not strictly increasing. 
Added by:  ~!(*(@*!@^& 
Date:  20090705 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ANARC 2005 