This problem appeared in ZCO(Zonal Computing Olympiad) 2014.
Following is the problem:
In ICO School, all students have to participate regularly in SUPW. There is a different SUPW activity each day, and each activity has its own duration. The SUPW schedule for the next term has been announced, including information about the number of minutes taken by each activity.
Nikhil has been designated SUPW coordinator. His task is to assign SUPW duties to students, including himself. The school’s rules say that no student can go three days in a row without any SUPW duty.
Nikhil wants to find an assignment of SUPW duty for himself that minimizes the number of minutes he spends overall on SUPW.
Link to the problem:
Line 1: A single integer N, the number of days in the future for which SUPW data is available.
Line 2: N non-negative integers, where the integer in position i represents the number of minutes required for SUPW work on day i.
The output consists of a single non-negative integer, the minimum number of minutes that Nikhil needs to spend on SUPW duties this term
3 2 1 1 2 3 1 3 2 1
He skips the first 2 days a+nd does the 1-minute activity. Now, he can do the 1-minute activity on the next day. Next, he can do the 2-minute activity, but it would be better if he skips the next 2 days and does the 1-minute activity as this will cost less time. Finally, he skips another 2 days and does the last 1-minute activity. This path that he has taken is the one with minimum time spent on SUPW activities.
Try to think of a more efficient path. You will find that this is the most efficient path possible with this set of numbers.
When we think about it using our minds alone, it seems like a simple task. However, try to think of how you would solve thins using an algorithm.
Before you read the program and description given below, I urge you to think alone for a while. Try to come up with the solution on your own.
Have you thought enough? The solution is given below. Read it, if you got it right congrats! However, if you didn’t or weren’t able to think of a solution, that’s alright. A simple solution is given below and this is a part of learning.
To understand this solution, you will require a working understanding of something called “Dynamic Programming”. If you do not know much about this, I recommend that you go through my last post which gives an introduction to dynamic programming:
Once we think about it, the SUPW problem is simply a one-dimensional DP problem, in the fact that there is one dependant variable, i.e., the total time Nikhil spends doing SUPW activities, that changes according to the path we take and we must choose a path such that the total time is minimal.
To solve this problem, lets treat the list of numbers given which represents the time take by each SUPW activity as a pathway, and each timing is a step on the pathway with a certain weightage. We need to walk to the end of the pathway by stepping on these steps. Once we are on a step the weightage of the step gets added to our total “score”. We can skip over steps, however, the maximum number of steps we can skip over is 2. So, in effect, if we skip 2 steps, we would move a net of 3 steps forward. We need to find a path such that our total score is minimal. We have successfully visualised the SUPW problem in a simpler setting.
If we solve the above problem, we will essentially solve the SUPW problem. To solve this, let us make use of an array data-structure to represent the pathway, and each index of the array represents the minimum “score” acquired to reach that index. How will we do this?
To do this we can take the value of an index to be the minimum of the previous 3 indices added to the weight of that “step” of the pathway. However, a problem arises. What will happen to the first 3 indices? Since it won’t be the most efficient way to reach the third step after going over either of the first 2, as you can just skip these. (According to the question we can “jump” over few steps). Therefore, to solve this, we merely assign the step weight to their respective indices in the array, ONLY FOR THE FIRST THREE INDICES. For the rest, we do the other process.
But how do we find the final answer?
To find this, all we need to do is to take the minimum of the last three indices, as one of these has to be the last step. Hence, we take the minimum of these as the answer.
The minimum “score” of the pathway is, in effect, the least amount of time needed to do SUPW activities without breaking the rules.
Consider the following:
2 4 1 3 1 2
We make an array with length = 6 for the above-mentioned reason. Let’s call it “arr”.
We first assign the first 3 indices to the respective times taken for the first 3 SUPW activities. The array becomes:
arr = [2 , 4 , 1 , 0 , 0 , 0]
Next, we look for the minimum “time” path for the 4th index by adding the respective value of time taken by the fourth activity and thee minimum of the previous 3 indices, i.e., [2 , 4 , 1]. The array becomes:
arr = [2 , 4 , 1 , 4 , 0 , 0]
We follow the same process for the 5th and 6th index. Hence the array becomes:
arr = [2 , 4 , 1 , 4 , 2 , 3].
Finally, all that’s left to do to find the final answer is to find the minimum of the values in the last three indices of the array, i.e., [4 , 2 , 3].
We find that this is 2. Hence we conclude that the answer to our problem is 2. Confirm this with normal intuition.
Following is the program-solution for the above question:
import math n = int(input()) a = [int(i) for i in input().split()] dp = [0 for i in range(n)] dp = a dp = a dp = a for i in range(3,n): dp[i] = a[i] + min(dp[i-1],dp[i-2],dp[i-3]) ans = min(dp[-3:]) print("the answer is",ans)
The output of the above program:
Time Complexity: O(n) where n represents the number of days for which the SUPW activity data is available.
The github link for the above program is:
You can check this program by submitting it on the codechef website (Link given in question). However, you must remove “the answer is” from the last print statement for their compiler to recognize your answer properly. This was just added for better readability in the blog.
Hence it will become:
Picture from:Business vector created by freepik – www.freepik.com