ANARC05B - The Double HeLiX


Two finite, 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:

  1. You may start at the beginning of any of the two sequences. Now start moving forward.
  2. 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 finding 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 specified on two separate lines. Each line denotes a sequence and is specified 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
snor_lax13: 2018-01-02 18:43:42

EZ...how is this even DP?

Last edit: 2018-01-02 18:59:52
codhek_09: 2017-12-27 21:43:45

getting runtime error even though the given test cases work :/

devansh1497: 2017-12-18 17:24:34

Ah I was accessing the wrong array which led to 4-5 Runtime errors...I used Binary search and memoization.
It was a good problem overall.

sajal_tikariha: 2017-12-12 11:57:09

Solved in O(m+n) complexity.

Last edit: 2017-12-12 12:25:18
ishgen: 2017-09-27 08:35:27

I am getting NZEC if I solve this problem using java.Code is working fine in eclipse and ideone.Does anyone has any idea about it?

kholan: 2017-09-10 15:03:04

Damn indices did switch 1 i for an j and there it goes NZEC

mhz2: 2017-08-13 05:08:34

My 100th.
To all those who are starting out on their journey remember do not get disheartened by other people's comment, "easy", "ac in one go", "move to tutorial" this is all bullshit. Everyone is on a different level and you might not be there yet but that does not mean you can never reach there. Patience my friend, Patience :)

This very supposedly "easy" "simple" "not challenging" problem took me hours to finally get the logic despite me having already done 99 other problems. Coding isn't always a game of intelligence. Here the one who knows the intricacies of the language he/she is using has a much bigger advantage. So keep on expanding your knowledge base and enjoy what you are doing else all these questions are meaningless :)

k52: 2017-08-09 21:08:57

simple af!

anubhav1772: 2017-07-08 22:08:56

There is a problem with Java language.When compiled using c++ gets accepted but the same logic when compiled using Java giving NZEC.

code_aim: 2017-07-05 20:26:26

O(nlogn) with 0.00s.


Added by:psetter
Date:2009-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2005