Showing posts with label 2020. Show all posts

Sunday, March 22, 2020

PDSA Week-8 Assignment Solution Jan-March 2020 NPTEL

Week-8 Assignment Solution (Last Date : 26/03/2020)

IOI Training Camp 20xx

(INOI 2011)

We are well into the 21st century and school children are taught dynamic programming in class 4. The IOI training camp has degenerated into an endless sequence of tests, with negative marking. At the end of the camp, each student is evaluated based on the sum of the best contiguous segment (i.e., no gaps) of marks in the overall sequence of tests.

Students, however, have not changed much over the years and they have asked for some relaxation in the evaluation procedure. As a concession, the camp coordinators have agreed that students are allowed to drop upto a certain number of tests when calculating their best segment.

For instance, suppose that Lavanya is a student at the training camp and there have been ten tests, in which her marks are as follows.

Test	1	2	3	4	5	6	7	8	9	10
Marks	6	-5	3	-7	6	-1	10	-8	-8	8

In this case, without being allowed to drop any tests, the best segment is tests 5–7, which yields a total of 15 marks. If Lavanya is allowed to drop upto 2 tests in a segment, the best segment is tests 1–7, which yields a total of 24 marks after dropping tests 2 and 4. If she is allowed to drop upto 6 tests in a segment, the best total is obtained by taking the entire list and dropping the 5 negative entries to get a total of 33.

You will be given a sequence of N test marks and a number K. You have to compute the sum of the best segment in the sequence when upto K marks may be dropped from the segment.

Solution hint

For 1 ≤ i ≤ N, 1 ≤ j ≤ K, let Best[i][j] denote the maximum segment ending at position i with at most j marks dropped. Best[i][0] is the classical maximum subsegment or maximum subarray problem. For j ≥ 1; inductively compute Best[i][j] from Best[i][j-1].

Input format

The first line of input contains two integers N and K, where N is the number of tests for which marks will be provided and K is the limit of how many entries may be dropped from a segment.

This is followed by N lines of input each containing a single integer. The marks for test i, i ∈ {1,2,…,N} are provided in line i+1.

Output format

The output is a single number, the maximum marks that can be obtained from a segment in which upto K values are dropped.

Constraints

You may assume that 1 ≤ N ≤ 104 and 0 ≤ K ≤ 102. The marks for each test lie in the range [-104 … 104]. In 40% of the cases you may assume N ≤ 250.

Example:

We now illustrate the input and output formats using the example described above.

Sample input:

Sample output:

Solution:

N,K = list(map(int,input().split()))

final = [0]

output = 0

for i in range(N):

final.append(int(input()))

score = [[0 for i in range(K+1)] for j in range(N+1)]

for i in range(1, N+1):

score[i][0] = max(score[i-1][0]+final[i], final[i])

for j in range(1, min(i+1, K+1)):

score[i][j] = max(score[i-1][j]+final[i], score[i-1][j-1])

for i in range(1, N+1):

output = max(output, score[i][K])

print(output)

Monday, March 9, 2020

Week-7 Quiz Solution PDSA Python Jan-March 2020 NPTEL

Week-7 Quiz Solution (Last Date : 18/03/2020)

Solution : 'fjadcgiheb'

Solution: D

Solution : B

Solution : D

Monday, March 2, 2020

Week-6 Quiz Solution PDSA Python Jan-March 2020 NPTEL

Week-6 Quiz Solution (Last Date : 11/03/2020)

1 Solution: D

2 Solution : A

3 Solution : D

4 Solution : B

Monday, February 17, 2020

Week-4 Assignment Solution Jan-March 2020 NPTEL

Week-4 Assignment Solution (Last Date : 27/02/2020)

We represent scores of batsmen across a sequence of matches in a two level dictionary as follows:
```
{'match1':{'player1':57, 'player2':38}, 'match2':{'player3':9, 'player1':42}, 'match3':{'player2':41, 'player4':63, 'player3':91}
```
Each match is identified by a string, as is each player. The scores are all integers. The names associated with the matches are not fixed (here they are 'match1', 'match2', 'match3'), nor are the names of the players. A player need not have a score recorded in all matches.

Define a Python function orangecap(d) that reads a dictionary d of this form and identifies the player with the highest total score. Your function should return a pair (playername,topscore) where playername is a string, the name of the player with the highest score, and topscore is an integer, the total score of playername.

The input will be such that there are never any ties for highest total score.

For instance:
```
>>> orangecap({'match1':{'player1':57, 'player2':38}, 'match2':{'player3':9, 'player1':42}, 'match3':{'player2':41, 'player4':63, 'player3':91}})
('player3', 100)

>>> orangecap({'test1':{'Ashwin':84, 'Kohli':120}, 'test2':{'Ashwin':59, 'Pujara':42}})
('Ashwin', 143)
```
Let us consider polynomials in a single variable x with integer coefficients. For instance:
```
3x4 - 17x2 - 3x + 5
```
Each term of the polynomial can be represented as a pair of integers (coefficient,exponent). The polynomial itself is then a list of such pairs.

We have the following constraints to guarantee that each polynomial has a unique representation:
- Terms are sorted in descending order of exponent
- No term has a zero cofficient
- No two terms have the same exponent
- Exponents are always nonnegative
For example, the polynomial introduced earlier is represented as:
```
[(3,4),(-17,2),(-3,1),(5,0)]
```
The zero polynomial, 0, is represented as the empty list [], since it has no terms with nonzero coefficients.

Write Python functions for the following operations:
```
addpoly(p1,p2)
multpoly(p1,p2)
```
that add and multiply two polynomials, respectively.

You may assume that the inputs to these functions follow the representation given above. Correspondingly, the outputs from these functions should also obey the same constraints.

You can write auxiliary functions to "clean up" polynomials – e.g., remove zero coefficient terms, combine like terms, sort by exponent etc. Build a library of functions that can be combined to achieve the desired format.

You may also want to convert the list representation to a dictionary representation and manipulate the dictionary representation, and then convert back.

Some examples:
```
  
   >>> addpoly([(4,3),(3,0)],[(-4,3),(2,1)])
   [(2, 1),(3, 0)]

   Explanation: (4x^3 + 3) + (-4x^3 + 2x) = 2x + 3

   >>> addpoly([(2,1)],[(-2,1)])
   []

   Explanation: 2x + (-2x) = 0

   >>> multpoly([(1,1),(-1,0)],[(1,2),(1,1),(1,0)])
   [(1, 3),(-1, 0)]

   Explanation: (x - 1) * (x^2 + x + 1) = x^3 - 1                    
```

Solution:

def orangecap(d):
total = {}
for k in d.keys():
for n in d[k].keys():
if n in total.keys():
total[n] = total[n] + d[k][n]
else:
total[n] = d[k][n]

maxtotal = -1
for n in total.keys():
if total[n] > maxtotal:
maxname = n
maxtotal = total[n]

return(maxname,maxtotal)

def listtodict(poly):
dpoly = {}
for term in poly:
coeff = term[0]
exp = term[1]
dpoly[exp] = coeff
return(dpoly)

def dicttolist(dpoly):
lpoly = []
for exp in sorted(dpoly.keys()):
lpoly.append((dpoly[exp],exp))
lpoly.reverse()
return(lpoly)

def dpolyadd (dpoly1,dpoly2):
sumpoly = {}
for exp in dpoly1.keys():
sumpoly[exp] = dpoly1[exp]

for exp in dpoly2.keys():
if exp in sumpoly.keys():
sumpoly[exp] = sumpoly[exp] + dpoly2[exp]
else:
sumpoly[exp] = dpoly2[exp]

return(sumpoly)

def dpolymult (dpoly1,dpoly2):
multpoly = {}
for exp1 in dpoly1.keys():
for exp2 in dpoly2.keys():
newexp = exp1 + exp2
newcoeff = dpoly1[exp1] * dpoly2[exp2]
if newexp in multpoly.keys():
multpoly[newexp] = multpoly[newexp] + newcoeff
else:
multpoly[newexp] = newcoeff
return(multpoly)

def addpoly(p1,p2):
d1 = listtodict(p1)
d2 = listtodict(p2)
res = dpolyadd(d1,d2)
return(dicttolist(cleanup(res)))

def multpoly(p1,p2):
d1 = listtodict(p1)
d2 = listtodict(p2)
res = dpolymult(d1,d2)
return(dicttolist(cleanup(res)))

def cleanup(dpoly):
dpolyclean = {}
for exp in dpoly.keys():
if dpoly[exp] != 0:
dpolyclean[exp] = dpoly[exp]

return(dpolyclean)

Programming, Data Structure and Algorithms Using Python NPTEL 2020 Jan-March Solution