ZIO05004 - Editorial

[jiit_rishabh]

Problem Link: https://www.iarcs.org.in/inoi/2005/zio2005/zio2005-qpaper.pdf

Editorialist: Rishabh Kejariwal

Pre-requisites:

1. Basic Arithmetic
2. Greedy Thinking

Problem in Short:

A teacher assigns homework at the beginning of the first day of class. Each homework problem carries one mark, plus a bonus if submitted within a specified number of days. Each homework problem takes exactly one day to complete. The deadline for earning the bonus and the number of bonus marks are different for each homework problem.

Your task is to find a schedule to complete all homework problems so as to maximize bonus marks and also find the total bonus marks you get.

Example:

For instance, if a problem has a deadline of 6 days and carries bonus 10 marks, then it earns 10 bonus marks provided it is submitted before the end of the 6th day.

For example, suppose there are seven problems with deadlines and bonuses as follows:

Problem name: a b c d e f g
Deadline for bonus: 1 1 3 3 2 2 6
Bonus marks: 6 7 2 1 4 5 1

Then the maximum number of bonus marks one can obtain is 15, which can be achieved by completing the problems in the sequence b, f, c, a, g, e, d.

Note:
There can be many sequences possible for a particular marks so you can find any possible sequence that gives maximum marks.

Explanation:

1. While performing each step you must be thinking of maximising the score which will surely lead to the correct answer.

2. As we have to maximize the score so we must do the problem with highest bonus marks first and then proceed to the problem carrying less bonus marks.

3. Now think of an instance that suppose there are many problems but the one having the highest bonus marks has a deadline of 10 days so we must try to finish it at the 10th day so we can finish more problems in the days earlier than 10 and earn their bonus marks from them too but suppose that you have already assigned a problem for 10th day so in this case we will try to finish this problem on 9th day if not on 9th then on 8th day we will proceed like this until we are unable to find an empty slot.
   One possibility is that if we are unable to find an empty slot that put this problem for the last day as you can’t earn the bonus marks for it.

4. Also if there are many problems with same bonus marks try to finish the one with shortest deadline first and then move on to the next problem.

Conclusion:

1. Arrange all the problem in decreasing order of bonus marks and start from the first problem and try to finish it as late as possible but in it’s deadline . Also if two problems are having the same bonus marks then arrange them in increasing order of deadline.
   Why are we doing this?

   Think of an example like there are two problems
   Problem Name: a b
   Deadline: 1 2
   Bonus: 10 20

   We will try to first finish Problem “b” and earn extra 20 marks but the day decided for Problem “b” can give us different results.

   • Day Assigned for problem “b” is 1.
     In this case you will earn extra 20 for “b” but you don’t get the bonus for problem “a” So the total bonus marks will be : 20
   • Day Assigned for problem “b” is 2.
     In this case you can complete problem “a” on day 1 and can earn the bonus marks for “A” too. So the total bonus marks will be: 10 + 20 = 30

   I think it’s clear.

2. We will create a one dimensional table for marking the days with a given problem and after performing each step the table will be the sequence we want to print.

3. Also we will also have a variable named “score” initialized to zero. This variable will be describing the total bonus marks earned. Whenever we assign a slot for a problem in it’s deadline we will add its bonus marks in this variable.

Examples Given in Question Paper: