The Gateway to Computer Science Excellence

0 votes

A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated based on the sum of the best contiguous segment (i.e., no gaps) of marks in the overall sequence of quizzes. However, the student is allowed to drop upto $K$ quizzes before calculating this sum.

Suppose a student has scored the following marks in $10$ quizzes during the semester.

$$\begin{array}{|c|c|c|c|c|}\hline \text{Quiz} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline \text{Marks } & 6 & -5 & 3 & -7 & 6 & -1 & 10 & -8 & -8 & 8 \\ \hline \end{array}$$

Without dropping any quizzes, the best segment is quiz $5-7$, which yields a total of $15$ marks. If the student is allowed to drop upto $2$ quizzes in a segment, the best segment is quiz $1-7$, which yields a total of $24$ marks after dropping quizzes $2$ and $4$. If the student is allowed to drop upto $6$ quizzes in a segment, the best total is obtained by taking the entire list and dropping all $5$ negative entries, yielding $33$ marks.

For $1\leq i<N, 0\leq j\leq K,$ let $B[i][j]$ denote the maximum sum segment ending at position $i$ with at most $j$ marks dropped.

- Write a recursive formula for $B[i][j].$
- Explain how to calculate, using dynamic programming, the score the professor needs to award each student.
- Describe the space and time complexity of your dynamic programming algorithm.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,439 comments

100,695 users