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

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

hide comments
2021-05-18 22:46:59
AC in one go.. you can do it without binary search and dp.. it is just prefix sum problem with two pointer technique
2021-05-13 09:55:17
How can we do it via binary search if we can
2021-05-03 12:18:58
O(mn) also works in java
2021-04-24 16:53:07
It is an easy problem,
AC in one GO
Time Complexity: max(n, m);
2021-03-19 20:06:42
Easy Problem!!! Don't get afraid by seeing the tags. You don't need to use them. AC in one go.
2021-03-18 20:44:06
Hi, I keep getting NZEC in Python 3, even though in my IDLE (3.7) runns literally all right cases from this discussion correctly and terminates just after the single 0. It also works on ideone.
Program solves the cases with 1 1 lines. I even answer the case where no intersection occurs.
Multiple spaces do not make problem in Python, but I also tried skipping blank lines and ending if no zero comes but EOF.
Still NZEC.
Did anybody experience something similar? Please tell me if i missed something really simple :D

[NG]: Input is correctly formatted (no blanklines). Perhaps you're trying to access elements outside the array? Sentinel might be your friend here. Also, what coolboy7 said below.

Last edit: 2021-03-19 01:35:57
2021-03-01 08:24:12
Why it is giving NZEC in java ??
2020-12-20 17:28:38
is there any concept in solving using dp and binarysearch?
I solved it simply using two pointers in O(n+m)

Last edit: 2020-12-20 17:29:13
2020-11-03 13:01:00
If u don't wan't to use dp+binarysearch then it's simple using prefix sum
2020-09-25 17:13:53
While switching to another array make sure to get the index of that common element in the 2nd array...if you are using dp+binary search
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.