| Submit | All submissions | Best solutions | Back to list |
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:
- 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 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
|
||||||||||||||
|
2024-12-12 15:53:30
two pointers |
||||||||||||||
|
2023-07-01 16:45:29
Hint 1: <snip> [Simes]: Let people experience the pleasure of figuring it out for themselves. Last edit: 2023-07-01 22:00:27 |
||||||||||||||
|
2023-07-01 16:42:17
This could be solved in linear time , without using any algorithms , no dp , no bs. a simple logic will work. |
||||||||||||||
|
2023-06-16 11:53:15
no dp, no binary search required, simple O(N) solution |
||||||||||||||
|
2023-06-04 23:28:09
It can be solved in Linear time i.e. O(max(n,m)) using 2 pointer approach: Link to Logic: <snip> Last edit: 2023-06-05 08:16:21 |
||||||||||||||
|
2022-07-21 22:32:14
4 -4 -3 -2 -1 3 -4 -3 -2 0 check on this : ans=-9 |
||||||||||||||
|
2022-01-18 17:47:54
EZPZ |
||||||||||||||
|
2022-01-12 12:29:51
Some of you might be getting NZEC because of multiple spaces present in some of the test cases like: 4 -5 100 1000 1005 3 -12 1000 1001 |
||||||||||||||
|
2021-09-26 09:00:39
Don't see the Tag , Just Normally think How it can be possible to solve, Forget the tag Input may make confused , Input is like n,s1 ---- (13 s1i , s1 i+1 ..............s1i+n) similarly m, s2 .. about test cases -- if n == 0 then it will break Last edit: 2021-09-26 09:05:14 |
||||||||||||||
|
2021-09-24 20:39:40
All the test cases in the comments is giving correct output still getting WA using DP :( edit: using lower_bound instead of map to find the intersections gave ac with dp :) Last edit: 2021-09-27 20:05:16 |
||||||||||||||
RSS