NPTEL Programming, Data Structures And Algorithms Using Python July 2024

 

NPTEL » Programming, Data Structures and Algorithms using Python

  Please scroll down for latest Programs 👇 

Week 2 Programming Assignment

Due on 2024-08-08, 23:59 IST

Write three Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.

• You may define additional auxiliary functions as needed.
• In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
• For each function, there are normally some public test cases and some (hidden) private test cases.
• "Compile and run" will evaluate your submission against the public test cases.
• "Submit" will evaluate your submission against the hidden private test cases. There are 10 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
• Ignore warnings about "Presentation errors".

---

1. Write a function intreverse(n) that takes as input a positive integer n and returns the integer obtained by reversing the digits in n.

   Here are some examples of how your function should work.

   >>> intreverse(783)
   387
   >>> intreverse(242789)
   987242
   >>> intreverse(3)
   3
   

2. Write a function matched(s) that takes as input a string s and checks if the brackets "(" and ")" in s are matched: that is, every "(" has a matching ")" after it and every ")" has a matching "(" before it. Your function should ignore all other symbols that appear in s. Your function should return True if s has matched brackets and False if it does not.

   Here are some examples to show how your function should work.

    
   >>> matched("zb%78")
   True
   >>> matched("(7)(a")
   False
   >>> matched("a)*(?")
   False
   >>> matched("((jkl)78(A)&l(8(dd(FJI:),):)?)")
   True
   

3. Write a function sumprimes(l) that takes as input a list of integers l and retuns the sum of all the prime numbers in l.

   Here are some examples to show how your function should work.

   >>> sumprimes([3,3,1,13])
   19
   >>> sumprimes([2,4,6,9,11])
   13
   >>> sumprimes([-3,1,6])
   0
   

Your last recorded submission was on 2024-07-31, 16:50 IST

Select the Language for this assignment.      --                     Python3               

1

def intreverse(n):

2

  r=0

3

  while(n != 0):

4

    r=r*10+n%10

5

    n=n//10

6

  return(r)

7

​

8

def matched(s):

9

  sum=0

10

  for i in range(len(s)):

11

    if(s[i]=='('):

12

      sum+=1

13

    elif(s[i]==')'):

14

      sum-=1

15

    if(sum<0):

16

      break

17

  if(sum==0):

18

    return True

19

  else:

20

    return False

21

22

23

def factors(n):

24

  factorlist = []

25

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

26

    if n%i == 0:

27

      factorlist.append(i)

28

  return(factorlist)

29

​

30

def isprime(n):

31

    return(factors(n) == [1,n])

32

33

def sumprimes(l):

34

  sum=0

35

  for i in range(len(l)):

36

    if(isprime(l[i])):

37

       sum+=l[i]

38

  return (sum)

0

~~~THERE IS SOME INVISIBLE CODE HERE~~~

You may submit any number of times before the due date. The final submission will be considered for grading.

This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.

   

Compilation : Passed
Public Test Cases: 9 / 9 Passed

Note: These tests may not be considered while scoring. Know more.

Public Test Cases	Input	Expected Output	Actual Output	Status
Test Case 1	intreverse(368)	863	863\n	Passed after ignoring Presentation Error
Test Case 2	intreverse(798798)	897897	897897\n	Passed after ignoring Presentation Error
Test Case 3	intreverse(7)	7	7\n	Passed after ignoring Presentation Error
Test Case 4	matched("(7)(a")	False	False\n	Passed after ignoring Presentation Error
Test Case 5	matched("a)*(?")	False	False\n	Passed after ignoring Presentation Error
Test Case 6	matched("((jkl)78(A)&l(8(dd(FJI:),):)?)")	True	True\n	Passed after ignoring Presentation Error
Test Case 7	sumprimes([17,51,29,39])	46	46\n	Passed after ignoring Presentation Error
Test Case 8	sumprimes([-3,-5,3,5])	8	8\n	Passed after ignoring Presentation Error
Test Case 9	sumprimes([4,6,15,27])	0	0\n	Passed after ignoring Presentation Error

Private Test cases used for Evaluation	Status
Test Case 1	Passed
Test Case 2	Passed
Test Case 3	Passed
Test Case 4	Passed
Test Case 5	Passed
Test Case 6	Passed
Test Case 7	Passed
Test Case 8	Passed
Test Case 9	Passed
Test Case 10	Passed

Week 3 Programming Assignment

Due on 2024-08-15, 23:59 IST

Write three Python functions as specified below. Paste the text for all three functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.

• You may define additional auxiliary functions as needed.
• In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
• For each function, there are normally some public test cases and some (hidden) private test cases.
• "Compile and run" will evaluate your submission against the public test cases.
• "Submit" will evaluate your submission against the hidden private test cases. There are 15 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
• Ignore warnings about "Presentation errors".

---

1. Write a function contracting(l) that takes as input a list of integer l and returns True if the absolute difference between each adjacent pair of elements strictly decreases.

   Here are some examples of how your function should work.

     >>> contracting([9,2,7,3,1])
     True
   
     >>> contracting([-2,3,7,2,-1]) 
     False
   
     >>> contracting([10,7,4,1])
     False
   

2. In a list of integers l, the neighbours of l[i] are l[i-1] and l[i+1]. l[i] is a hill if it is strictly greater than its neighbours and a valley if it is strictly less than its neighbours.

   Write a function counthv(l) that takes as input a list of integers l and returns a list [hc,vc] where hc is the number of hills in l and vc is the number of valleys in l.

   Here are some examples to show how your function should work.

    
   >>> counthv([1,2,1,2,3,2,1])
   [2, 1]
   
   >>> counthv([1,2,3,1])
   [1, 0]
   
   >>> counthv([3,1,2,3])
   [0, 1]
   
   

3. A square n×n matrix of integers can be written in Python as a list with n elements, where each element is in turn a list of n integers, representing a row of the matrix. For instance, the matrix

     1  2  3
     4  5  6
     7  8  9
   

   would be represented as [[1,2,3], [4,5,6], [7,8,9]].

   Write a function leftrotate(m) that takes a list representation m of a square matrix as input, and returns the matrix obtained by rotating the original matrix counterclockwize by 90 degrees. For instance, if we rotate the matrix above, we get

     3  6  9
     2  5  8    
     1  4  7
   

   Your function should not modify the argument m provided to the function rotate().

   Here are some examples of how your function should work.

    
     >>> leftrotate([[1,2],[3,4]])
     [[2, 4], [1, 3]]
   
     >>> leftrotate([[1,2,3],[4,5,6],[7,8,9]])
     [[3, 6, 9], [2, 5, 8], [1, 4, 7]]
   
     >>> leftrotate([[1,1,1],[2,2,2],[3,3,3]])
     [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
   

Your last recorded submission was on 2024-08-06, 21:05 IST

Select the Language for this assignment.      --                     Python3               

1

def contracting(l):

2

    if len(l) < 3:

3

        return(True)

4

    return((abs(l[1]-l[0]) > abs(l[2]-l[1])) and contracting(l[1:]))

5

6

def counthv(l):

7

    hills = 0

8

    valleys = 0

9

    for i in range(1,len(l)-1):

10

        if l[i] > l[i-1] and l[i] > l[i+1]:

11

            hills = hills + 1

12

        if l[i] < l[i-1] and l[i] < l[i+1]:

13

            valleys = valleys + 1

14

    return([hills,valleys])

15

16

def leftrotate(m):

17

    size = len(m)

18

    rotated_m = []

19

    for i in range(size):

20

        rotated_m.append([])

21

    for c in range(size-1,-1,-1):

22

        for r in range(size):

23

            rotated_m[size-(c+1)].append(m[r][c])

24

    return(rotated_m)

25

0

~~~THERE IS SOME INVISIBLE CODE HERE~~~

You may submit any number of times before the due date. The final submission will be considered for grading.

This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.

   

Compilation : Passed
Public Test Cases: 9 / 9 Passed

Note: These tests may not be considered while scoring. Know more.

Public Test Cases	Input	Expected Output	Actual Output	Status
Test Case 1	contracting([9,2,7,3,1])	True	True\n	Passed after ignoring Presentation Error
Test Case 2	contracting([-2,3,7,2,-1])	False	False\n	Passed after ignoring Presentation Error
Test Case 3	contracting([10,7,4,1])	False	False\n	Passed after ignoring Presentation Error
Test Case 4	counthv([1,2,1,2,3,2,1])	[2, 1]	[2, 1]\n	Passed after ignoring Presentation Error
Test Case 5	counthv([1,2,3,1])	[1, 0]	[1, 0]\n	Passed after ignoring Presentation Error
Test Case 6	counthv([3,1,2,3])	[0, 1]	[0, 1]\n	Passed after ignoring Presentation Error
Test Case 7	leftrotate([[1,2],[3,4]])	[[2, 4], [1, 3]]	[[2, 4], [1, 3]]\n	Passed after ignoring Presentation Error
Test Case 8	leftrotate([[1,2,3],[4,5,6],[7,8,9]])	[[3, 6, 9], [2, 5, 8], [1, 4, 7]]	[[3, 6, 9], [2, 5, 8], [1, 4, 7]]\n	Passed after ignoring Presentation Error
Test Case 9	leftrotate([[1,1,1],[2,2,2],[3,3,3]])	[[1, 2, 3], [1, 2, 3], [1, 2, 3]]	[[1, 2, 3], [1, 2, 3], [1, 2, 3]]\n	Passed after ignoring Presentation Error

Private Test cases used for Evaluation	Status
Test Case 1	Passed
Test Case 2	Passed
Test Case 3	Passed
Test Case 4	Passed
Test Case 5	Passed
Test Case 6	Passed
Test Case 7	Passed
Test Case 8	Passed
Test Case 9	Passed
Test Case 10	Passed
Test Case 11	Passed
Test Case 12	Passed
Test Case 13	Passed
Test Case 14	Passed
Test Case 15	Passed

Week 4 Programming Assignment

Due on 2024-08-22, 23:59 IST

Write two Python functions as specified below. Paste the text for both functions together into the submission window. Your function will be called automatically with various inputs and should return values as specified. Do not write commands to read any input or print any output.

• You may define additional auxiliary functions as needed.
• In all cases you may assume that the value passed to the function is of the expected type, so your function does not have to check for malformed inputs.
• For each function, there are normally some public test cases and some (hidden) private test cases.
• "Compile and run" will evaluate your submission against the public test cases.
• "Submit" will evaluate your submission against the hidden private test cases. There are 11 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
• Ignore warnings about "Presentation errors".

---

1. Write a Python function frequency(l) that takes as input a list of integers and returns a pair of the form (minfreqlist,maxfreqlist) where

   • minfreqlist is a list of numbers with minimum frequency in l, sorted in ascending order
   • maxfreqlist is a list of numbers with maximum frequency in l, sorted in ascending order

   Here are some examples of how your function should work.

   >>> frequency([13,12,11,13,14,13,7,11,13,14,12])
   ([7], [13])
   
   >>> frequency([13,12,11,13,14,13,7,11,13,14,12,14,14])
   ([7], [13, 14])
   
   >>> frequency([13,12,11,13,14,13,7,11,13,14,12,14,14,7])
   ([7, 11, 12], [13, 14])
   

2. An airline has assigned each city that it serves a unique numeric code. It has collected information about all the direct flights it operates, represented as a list of pairs of the form (i,j), where i is the code of the starting city and j is the code of the destination.

   It now wants to compute all pairs of cities connected by one intermediate hope — city i is connected to city j by one intermediate hop if there are direct flights of the form (i,k) and (k,j) for some other city k. The airline is only interested in one hop flights between different cities — pairs of the form (i,i) are not useful.

   Write a Python function onehop(l) that takes as input a list of pairs representing direct flights, as described above, and returns a list of all pairs (i,j), where i != j, such that i and j are connected by one hop. Note that it may already be the case that there is a direct flight from i to j. So long as there is an intermediate k with a flight from i to k and from k to j, the list returned by the function should include (i,j). The input list may be in any order. The pairs in the output list should be in lexicographic (dictionary) order. Each pair should be listed exactly once.

   Here are some examples of how your function should work.

    
   >>> onehop([(2,3),(1,2)])
   [(1, 3)]
   
   >>> onehop([(2,3),(1,2),(3,1),(1,3),(3,2),(2,4),(4,1)])
   [(1, 2), (1, 3), (1, 4), (2, 1), (3, 2), (3, 4), (4, 2), (4, 3)]
   
   >>> onehop([(1,2),(3,4),(5,6)])
   []
   

Select the Language for this assignment.      --                     Python3               

1

def frequency(l):

2

    count = {}

3

    for n in l:

4

        if n in count.keys():

5

            count[n] = count[n]+1

6

        else:

7

            count[n] = 1

8

    minlist = findmin(count)

9

    maxlist = findmax(count)

10

    return((minlist,maxlist))

11

12

def findmin(d):

13

    upperbound = 0

14

    for n in d.keys():

15

        if d[n] > upperbound:

16

            upperbound = d[n]

17

    minlist = []

18

    mincount = upperbound

19

    for n in d.keys():

20

        if d[n] < mincount:

21

            minlist = [n]

22

            mincount = d[n]

23

        elif d[n] == mincount:

24

            minlist.append(n)

25

    return(sorted(minlist))

26

27

28

def findmax(d):

29

    maxlist = []

30

    maxcount = 0

31

    for n in d.keys():

32

        if d[n] > maxcount:

33

            maxlist = [n]

34

            maxcount = d[n]

35

        elif d[n] == maxcount:

36

            maxlist.append(n)

37

    return(sorted(maxlist))

38

###################

39

def onehop(l):

40

    direct = {}

41

    for (i,j) in l:

42

        if i in direct.keys():

43

            direct[i].append(j)

44

        else:

45

            direct[i] = [j]

46

    hopping = []

47

    for src in direct.keys():

48

        for dest in direct[src]:

49

            if dest in direct.keys():

50

                for remote in direct[dest]:

51

                    if src != remote:

52

                        hopping.append((src,remote))

53

    return(remdup(sorted(hopping)))

54

55

def remdup(l):

56

    if len(l) < 2:

57

        return(l)

58

    if l[0] != l[1]:

59

        return(l[0:1]+remdup(l[1:]))

60

    else:

61

        return(remdup(l[1:]))

62

63

###################

0

~~~THERE IS SOME INVISIBLE CODE HERE~~~

You may submit any number of times before the due date. The final submission will be considered for grading.

This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.

   

Compilation : Passed
Public Test Cases: 6 / 6 Passed

Note: These tests may not be considered while scoring. Know more.

Public Test Cases	Input	Expected Output	Actual Output	Status
Test Case 1	frequency([1,2,3,4,5,5,4,3,2,3,4,5,5,4,5])	([1], [5])	([1], [5])\n	Passed after ignoring Presentation Error
Test Case 2	frequency([4,4,4,1,1,2,2,2,3,3])	([1, 3], [2, 4])	([1, 3], [2, 4])\n	Passed after ignoring Presentation Error
Test Case 3	frequency([1,1,1,1,1])	([1], [1])	([1], [1])\n	Passed after ignoring Presentation Error
Test Case 4	onehop([(1,2),(2,1)])	[]	[]\n	Passed after ignoring Presentation Error
Test Case 5	onehop([(1,2)])	[]	[]\n	Passed after ignoring Presentation Error
Test Case 6	onehop([(1,3),(1,2),(2,3),(2,1),(3,2),(3,1)])	[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]	[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]\n	Passed after ignoring Presentation Error

Private Test cases used for Evaluation	Status
Test Case 1	Passed
Test Case 2	Passed
Test Case 3	Passed
Test Case 4	Passed
Test Case 5	Passed
Test Case 6	Passed
Test Case 7	Passed
Test Case 8	Passed
Test Case 9	Passed
Test Case 10	Passed
Test Case 11	Passed

Week 5 Programming Assignment

Due on 2024-08-29, 23:59 IST

For this assignment, you have to write a complete Python program. Paste your code in the window below.

• You may define additional auxiliary functions as needed.
• In all cases you may assume that the input to your program has the expected format, so your program does not have to check for malformed inputs.
• There are some public test cases and some (hidden) private test cases.
• "Compile and run" will evaluate your submission against the public test cases.
• "Submit" will evaluate your submission against the hidden private test cases. There are 6 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
• Ignore warnings about "Presentation errors".

---

---

The library at the Hogwarts School of Witchcraft and Wizardry has computerized its book issuing process. The relevant information is provided as text from standard input in three parts: information about books, information about borrowers and information about checkouts. Each part has a specific line format, described below.

1. Information about books
   Line format: Accession Number~Title

2. Information about borrowers
   Line format: Username~Full Name

3. Information about checkouts
   Line format: Username~Accession Number~Due Date
   Note: Due Date is in YYYY-MM-DD format.

You may assume that the data is internally consistent. For every checkout, there is a corresponding username and accession number in the input data, and no book is simultaneously checked out by two people.

Each section of the input starts with a line containing a single keyword. The first section begins with a line containing Books. The second section begins with a line containing Borrowers. The third section begins with a line containing Checkouts. The end of the input is marked by a line containing EndOfInput.

Write a Python program to read the data as described above and print out details about books that have been checked out. Each line should describe to one currently issued book in the following format:

Due Date~Full Name~Accession Number~Title

Your output should be sorted in increasing order of due date. For books due on the same date, sort in increasing order of full name.

Here is a sample input and its corresponding output.

Sample Input

Books
APM-001~Advanced Potion-Making
GWG-001~Gadding With Ghouls
APM-002~Advanced Potion-Making
DMT-001~Defensive Magical Theory
DMT-003~Defensive Magical Theory
GWG-002~Gadding With Ghouls
DMT-002~Defensive Magical Theory
Borrowers
SLY2301~Hannah Abbott
SLY2302~Euan Abercrombie
SLY2303~Stewart Ackerley
SLY2304~Bertram Aubrey
SLY2305~Avery
SLY2306~Malcolm Baddock
SLY2307~Marcus Belby
SLY2308~Katie Bell
SLY2309~Sirius Orion Black
Checkouts
SLY2304~DMT-002~2019-03-27
SLY2301~GWG-001~2019-03-27
SLY2308~APM-002~2019-03-14
SLY2303~DMT-001~2019-04-03
SLY2301~GWG-002~2019-04-03
EndOfInput

Sample Output

2019-03-14~Katie Bell~APM-002~Advanced Potion-Making
2019-03-27~Bertram Aubrey~DMT-002~Defensive Magical Theory
2019-03-27~Hannah Abbott~GWG-001~Gadding With Ghouls
2019-04-03~Hannah Abbott~GWG-002~Gadding With Ghouls
2019-04-03~Stewart Ackerley~DMT-001~Defensive Magical Theory

Your last recorded submission was on 2024-08-19, 11:15 IST

Select the Language for this assignment.      --                     Python3               

1

# Dictionary to map accession number to title

2

books = {}

3

# Dictionary to map username to fullname

4

borrowers = {}

5

# List to store checkout data: accumulate, sort and print

6

checkouts = []

7

# Find the start of Books data

8

nextline = input().strip()

9

while nextline.find("Books") < 0:

10

    nextline = input().strip()

11

# Read upto start of Borrowers data

12

# Skip the line with "Books"

13

nextline = input().strip()

14

while nextline.find("Borrowers") < 0:

15

    (accession_number,title) = nextline.split('~')

16

    books[accession_number] = title

17

    nextline = input().strip()

18

# Read upto Checkout data

19

# Skip the line with "Borrowers"

20

nextline = input().strip()

21

while nextline.find("Checkouts") < 0:

22

    (username,fullname) = nextline.split('~')

23

    borrowers[username] = fullname

24

    nextline = input().strip()

25

# Process Checkouts

26

# Skip the line with "Checkouts"

27

nextline = input().strip()

28

while nextline.find("EndOfInput") < 0:

29

    (username,accession_number,due_date) = nextline.split('~')

30

    checkoutline = due_date+"~"+borrowers[username]+"~"+accession_number+"~"+books[accession_number]

31

    checkouts.append(checkoutline)

32

    nextline = input().strip()

33

# Print the output from checkouts

34

for checkoutline in sorted(checkouts):

35

    print(checkoutline)

You may submit any number of times before the due date. The final submission will be considered for grading.

This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.

   

Compilation : Passed
Public Test Cases: 2 / 2 Passed

Note: These tests may not be considered while scoring. Know more.

Public Test Cases	Input	Expected Output	Actual Output	Status
Test Case 1	Books APM-001~Advanced Potion-Making GWG-001~Gadding With Ghouls APM-002~Advanced Potion-Making DMT-001~Defensive Magical Theory DMT-003~Defensive Magical Theory GWG-002~Gadding With Ghouls DMT-002~Defensive Magical Theory Borrowers SLY2301~Hannah Abbott SLY2302~Euan Abercrombie SLY2303~Stewart Ackerley SLY2304~Bertram Aubrey SLY2305~Avery SLY2306~Malcolm Baddock SLY2307~Marcus Belby SLY2308~Katie Bell SLY2309~Sirius Orion Black Checkouts SLY2304~DMT-002~2019-03-27 SLY2301~GWG-001~2019-03-27 SLY2308~APM-002~2019-03-14 SLY2303~DMT-001~2019-04-03 SLY2301~GWG-002~2019-04-03 EndOfInput	2019-03-14~Katie Bell~APM-002~Advanced Potion-Making\n 2019-03-27~Bertram Aubrey~DMT-002~Defensive Magical Theory\n 2019-03-27~Hannah Abbott~GWG-001~Gadding With Ghouls\n 2019-04-03~Hannah Abbott~GWG-002~Gadding With Ghouls\n 2019-04-03~Stewart Ackerley~DMT-001~Defensive Magical Theory	2019-03-14~Katie Bell~APM-002~Advanced Potion-Making\n 2019-03-27~Bertram Aubrey~DMT-002~Defensive Magical Theory\n 2019-03-27~Hannah Abbott~GWG-001~Gadding With Ghouls\n 2019-04-03~Hannah Abbott~GWG-002~Gadding With Ghouls\n 2019-04-03~Stewart Ackerley~DMT-001~Defensive Magical Theory\n	Passed after ignoring Presentation Error
Test Case 2	Books GTF-001~A Beginner's Guide to Transfiguration GTF-002~A Beginner's Guide to Transfiguration GTF-003~A Beginner's Guide to Transfiguration WET-001~Great Wizarding Events of the Twentieth Century WET-002~Great Wizarding Events of the Twentieth Century WTC-001~Great Wizards of the Twentieth Century WTC-002~Great Wizards of the Twentieth Century WTC-003~Great Wizards of the Twentieth Century WTC-004~Great Wizards of the Twentieth Century IBI-001~Invisible Book of Invisibility IBI-002~Invisible Book of Invisibility JFJ-001~Jinxes for the Jinxed JFJ-002~Jinxes for the Jinxed LDM-001~Men Who Love Dragons Too Much LDM-002~Men Who Love Dragons Too Much LDM-003~Men Who Love Dragons Too Much NTN-001~New Theory of Numerology MFM-001~One Minute Feasts - It's Magic! PYN-001~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up PYN-002~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up PYN-003~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up PDM-001~Practical Defensive Magic and Its Use Against the Dark Arts PDM-002~Practical Defensive Magic and Its Use Against the Dark Arts PDM-003~Practical Defensive Magic and Its Use Against the Dark Arts PDM-004~Practical Defensive Magic and Its Use Against the Dark Arts QAQ-001~Quintessence: A Quest QAQ-002~Quintessence: A Quest STS-001~Saucy Tricks for Tricky Sorts STS-002~Saucy Tricks for Tricky Sorts STS-003~Saucy Tricks for Tricky Sorts STS-004~Saucy Tricks for Tricky Sorts Borrowers SLY2301~Hannah Abbott SLY2307~Marcus Belby SLY2311~Susan Bones SLY2313~Eleanor Branstone SLY2319~Eddie Carmichael GRF3703~Dennis Creevey GRF3708~J. Dorny GRF3715~Basil Fronsac RAV4308~Olive Hornby RAV4309~Angelina Johnson RAV5902~Isobel MacDougal RAV5905~Laura Madley RAV5906~Draco Malfoy RAV5907~Natalie McDonald GRF9104~Lily Moon GRF9107~Garrick Ollivander Checkouts RAV5906~GTF-001~2019-03-22 GRF3708~GTF-002~2019-03-26 SLY2307~GTF-003~2019-03-01 GRF3708~WET-001~2019-03-06 SLY2301~WET-002~2019-03-23 SLY2307~WTC-001~2019-02-26 SLY2311~WTC-002~2019-03-12 SLY2313~WTC-003~2019-03-06 SLY2301~WTC-004~2019-03-12 RAV5906~IBI-001~2019-03-12 SLY2307~IBI-002~2019-03-23 GRF3715~JFJ-001~2019-03-23 RAV5905~JFJ-002~2019-03-16 SLY2311~LDM-001~2019-02-26 RAV4308~LDM-002~2019-03-20 SLY2307~LDM-003~2019-03-22 GRF3703~NTN-001~2019-03-09 RAV4308~MFM-001~2019-03-07 SLY2311~PYN-001~2019-03-03 RAV5902~PYN-002~2019-03-02 GRF9104~PYN-003~2019-03-16 GRF3708~PDM-001~2019-03-13 RAV5907~PDM-002~2019-03-26 SLY2307~PDM-003~2019-02-26 SLY2313~PDM-004~2019-03-01 RAV4309~QAQ-001~2019-03-14 RAV5907~QAQ-002~2019-03-17 RAV5905~STS-001~2019-03-12 SLY2319~STS-002~2019-03-11 GRF3703~STS-003~2019-03-19 RAV5907~STS-004~2019-03-17 EndOfInput	2019-02-26~Marcus Belby~PDM-003~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-02-26~Marcus Belby~WTC-001~Great Wizards of the Twentieth Century\n 2019-02-26~Susan Bones~LDM-001~Men Who Love Dragons Too Much\n 2019-03-01~Eleanor Branstone~PDM-004~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-03-01~Marcus Belby~GTF-003~A Beginner's Guide to Transfiguration\n 2019-03-02~Isobel MacDougal~PYN-002~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-03~Susan Bones~PYN-001~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-06~Eleanor Branstone~WTC-003~Great Wizards of the Twentieth Century\n 2019-03-06~J. Dorny~WET-001~Great Wizarding Events of the Twentieth Century\n 2019-03-07~Olive Hornby~MFM-001~One Minute Feasts - It's Magic!\n 2019-03-09~Dennis Creevey~NTN-001~New Theory of Numerology\n 2019-03-11~Eddie Carmichael~STS-002~Saucy Tricks for Tricky Sorts\n 2019-03-12~Draco Malfoy~IBI-001~Invisible Book of Invisibility\n 2019-03-12~Hannah Abbott~WTC-004~Great Wizards of the Twentieth Century\n 2019-03-12~Laura Madley~STS-001~Saucy Tricks for Tricky Sorts\n 2019-03-12~Susan Bones~WTC-002~Great Wizards of the Twentieth Century\n 2019-03-13~J. Dorny~PDM-001~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-03-14~Angelina Johnson~QAQ-001~Quintessence: A Quest\n 2019-03-16~Laura Madley~JFJ-002~Jinxes for the Jinxed\n 2019-03-16~Lily Moon~PYN-003~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-17~Natalie McDonald~QAQ-002~Quintessence: A Quest\n 2019-03-17~Natalie McDonald~STS-004~Saucy Tricks for Tricky Sorts\n 2019-03-19~Dennis Creevey~STS-003~Saucy Tricks for Tricky Sorts\n 2019-03-20~Olive Hornby~LDM-002~Men Who Love Dragons Too Much\n 2019-03-22~Draco Malfoy~GTF-001~A Beginner's Guide to Transfiguration\n 2019-03-22~Marcus Belby~LDM-003~Men Who Love Dragons Too Much\n 2019-03-23~Basil Fronsac~JFJ-001~Jinxes for the Jinxed\n 2019-03-23~Hannah Abbott~WET-002~Great Wizarding Events of the Twentieth Century\n 2019-03-23~Marcus Belby~IBI-002~Invisible Book of Invisibility\n 2019-03-26~J. Dorny~GTF-002~A Beginner's Guide to Transfiguration\n 2019-03-26~Natalie McDonald~PDM-002~Practical Defensive Magic and Its Use Against the Dark Arts	2019-02-26~Marcus Belby~PDM-003~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-02-26~Marcus Belby~WTC-001~Great Wizards of the Twentieth Century\n 2019-02-26~Susan Bones~LDM-001~Men Who Love Dragons Too Much\n 2019-03-01~Eleanor Branstone~PDM-004~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-03-01~Marcus Belby~GTF-003~A Beginner's Guide to Transfiguration\n 2019-03-02~Isobel MacDougal~PYN-002~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-03~Susan Bones~PYN-001~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-06~Eleanor Branstone~WTC-003~Great Wizards of the Twentieth Century\n 2019-03-06~J. Dorny~WET-001~Great Wizarding Events of the Twentieth Century\n 2019-03-07~Olive Hornby~MFM-001~One Minute Feasts - It's Magic!\n 2019-03-09~Dennis Creevey~NTN-001~New Theory of Numerology\n 2019-03-11~Eddie Carmichael~STS-002~Saucy Tricks for Tricky Sorts\n 2019-03-12~Draco Malfoy~IBI-001~Invisible Book of Invisibility\n 2019-03-12~Hannah Abbott~WTC-004~Great Wizards of the Twentieth Century\n 2019-03-12~Laura Madley~STS-001~Saucy Tricks for Tricky Sorts\n 2019-03-12~Susan Bones~WTC-002~Great Wizards of the Twentieth Century\n 2019-03-13~J. Dorny~PDM-001~Practical Defensive Magic and Its Use Against the Dark Arts\n 2019-03-14~Angelina Johnson~QAQ-001~Quintessence: A Quest\n 2019-03-16~Laura Madley~JFJ-002~Jinxes for the Jinxed\n 2019-03-16~Lily Moon~PYN-003~Powers You Never Knew You Had and What To Do With Them Now You've Wised Up\n 2019-03-17~Natalie McDonald~QAQ-002~Quintessence: A Quest\n 2019-03-17~Natalie McDonald~STS-004~Saucy Tricks for Tricky Sorts\n 2019-03-19~Dennis Creevey~STS-003~Saucy Tricks for Tricky Sorts\n 2019-03-20~Olive Hornby~LDM-002~Men Who Love Dragons Too Much\n 2019-03-22~Draco Malfoy~GTF-001~A Beginner's Guide to Transfiguration\n 2019-03-22~Marcus Belby~LDM-003~Men Who Love Dragons Too Much\n 2019-03-23~Basil Fronsac~JFJ-001~Jinxes for the Jinxed\n 2019-03-23~Hannah Abbott~WET-002~Great Wizarding Events of the Twentieth Century\n 2019-03-23~Marcus Belby~IBI-002~Invisible Book of Invisibility\n 2019-03-26~J. Dorny~GTF-002~A Beginner's Guide to Transfiguration\n 2019-03-26~Natalie McDonald~PDM-002~Practical Defensive Magic and Its Use Against the Dark Arts\n	Passed after ignoring Presentation Error

Week Programming Assignment - IOI Training Camp 20xx

Due on 2024-09-19, 23:59 IST

For this assignment, you have to write a complete Python program. Paste your code in the window below.

• You may define additional auxiliary functions as needed.
• There are some public test cases and some (hidden) private test cases.
• "Compile and run" will evaluate your submission against the public test cases
• "Submit" will evaluate your submission against the hidden private test cases. There are 10 private test cases, with equal weightage. You will get feedback about which private test cases pass or fail, though you cannot see the actual test cases.
• Ignore warnings about "Presentation errors".

---

---

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:

10 2
6
-5
3
-7
6
-1
10
-8
-8
8

Sample output:

24

Your last recorded submission was on 2024-09-10, 08:26 IST

Select the Language for this assignment.      --                     Python3               

1

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

2

f = [0]

3

output = 0

4

for a in range(N):

5

    f.append(int(input()))

6

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

7

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

8

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

9

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

10

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

11

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

12

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

13

print(output, end='')

You may submit any number of times before the due date. The final submission will be considered for grading.

This assignment has Public Test cases. Please click on "Compile & Run" button to see the status of Public test cases. Assignment will be evaluated only after submitting using Submit button below. If you only save as or compile and run the Program , your assignment will not be graded and you will not see your score after the deadline.

   

Compilation : Passed
Public Test Cases: 4 / 4 Passed

Note: These tests may not be considered while scoring. Know more.

Public Test Cases	Input	Expected Output	Actual Output	Status
Test Case 1	10 2 6 -5 3 -7 6 -1 10 -8 -8 8	24	24	Passed
Test Case 2	10 3 6 -5 3 -7 6 -1 10 -8 -8 8	27	27	Passed
Test Case 3	10 4 6 -5 3 -7 6 -1 10 -8 -8 8	32	32	Passed
Test Case 4	10 6 6 -5 3 -7 6 -1 10 -8 -8 8	33	33	Passed

Private Test cases used for Evaluation	Status
Test Case 1	Passed
Test Case 2	Passed
Test Case 3	Passed
Test Case 4	Passed
Test Case 5	Passed
Test Case 6	Passed
Test Case 7	Passed
Test Case 8	Passed
Test Case 9	Passed
Test Case 10	Passed