Description
Problem Description: Team Building
An instructor teaches two CS2 sections (section 1 and section 2). He is thinking to short list a group of
students for an upcoming contest. As part of the process, n number of candidates from each section has solved
several programming problems.
On the day of the selection, 2n candidates have come to the venue for short listing. He asked the students to
stand in 2 rows of same size. Exactly n students from each section. The candidates are numbered from 1 to n on
each row from left to right.
1 2 3
…..
n
1 2 3
…..
n
Now the instructor will choose the candidates from the rows with the following rules:
1. Candidates should be chosen from left to right.
2. Index of each chosen candidate (excluding the first one taken) will be greater than the index of the
previously chosen candidate.
3. In order to avoid giving preference of a specific section, he will choose the candidates in such a way that
no consecutive chosen candidates belong to the same section (aka row).
4. The first student can be chosen from all 2n students without any constraints.
5. The final resulting group can have any number of candidates.
6. In order to make a perfect group of students, he will choose the students in such a way, that the total
number of problems solved by the students will be the maximum.
So, solve this problem to find the group of students that will maximize the problems solved with all the given
constraints.
Input specification (Must be read from standard input (no file i/o))
The first line of the input contains a single integer n (1≤n≤100000) that represents the number of students in each
row.
The second line of the input contains n integers p1,1,p1,2,…,p1,n,(1≤p1,i≤109), where p1,i is the number of problems
solved by the ith student in the first row.
The third line of the input contains n integers p2,1,p2,2,…,p2,n,(1≤p2,i≤109), where p2,i is the number of problems
solved by the ith student in the second row.
The Output (standard console output):
Print one number — the maximum possible total problem solved by the selected group of students.
Sample Input Sample Output Explanation
5
9 3 5 7 3
5 8 1 4 5
29 The chosen candidates can be these:
3
1 2 9
10 1 1
19
1
7
4
7
Some Restrictions:
– You must have to use Dynamic Programming with bottom up tabulation approach to solve this problem
– The run-time has to be linear O(n)
Hints:
– The code will be very small but require some good understanding of bottom-up tabulation approach of dynamic
programming. So far, we have seen Fibonacci, 0/1 knapsack, LCS, MCM, and some other examples. These all
should give you some ideas on dynamic programming approaches.
– As you now know dynamic programming, don’t start thinking on brute force approach.
o Have a 2D table based on n and number of rows
o Initialize the first index of row 0 and row 1
o Start updating index 1, row 0 and then then update index 1 or row 1, keep reading the hints to understand how
to decide the numbers for the update.
o Remember, your target is to maximize the total.
o So, while updating an index of row 0 of the table, it should be based on some max of last calculations, and new
calculations. Also note that, an update of row 0 in the table might need information from row 1. Same for row 1.
o You will generally no need to access information other than the previous index and the candiate list’s current
index
o Finally, your final answer will be located in the last index of row 0 or row 1 of the table.
What To Submit
See the first page of the assignment about what to submit.
Good Luck!
