Welcome back, dear reader. So, in this article, we will discuss a very interesting question called HIGHWAY BILLBOARDS. What does this question say?
Important Links : Problem Link, Solution Video
Prev Next
Highway Billboards Problem
Understanding the Problem:
Have a look at the sample input shown below:
The first input 20 denotes that there is a highway of 20 units length. The next integer 5 denotes the number of billboards that we can place on that road. The next 5 integers denote the positions at which we can place a billboard. For instance, we can place a billboard at the 6th mile or 7th mile and so on. The next 5 numbers show the revenues generated by the corresponding billboards. The last integer 5 denotes the minimum distance between 2 billboards that should be maintained. So, we have to tell the maximum revenue that can be generated. The situation is shown below:
You may refer to the HIGHWAY BILLBOARDS VIDEO to understand the question completely and clear your doubts regarding the question if any. We also suggest you try to solve these problems on your own first and then go to the solution to build your concepts.
Approach:
Explanation:
Let us take the example given below. In this example, the road is of length 20 units and there are 5 boards that can be kept on the following locations {6,8,12,14,16} and their corresponding revenues are {5,8,5,3,1}. Also, we have to maintain a distance of more than 3 units between 2 consecutive boards.
Let us start with our first approach.
Method-1:
Let us solve this problem following the 3 stages of Dynamic Programming.
- Storage and Meaning:
We will make a dp array of size equal to the size of the array of the billboards location. Here, we have 5 billboards given to us. So, let us make a dp array of size 5.So, the above image shows that we have made a dp array of size equal to that of the array x. The array x contains the locations where we can put a billboard.
What does each cell in the dp array represent?Did you understand the meaning from the image above? The meaning is very simple. Let us take index 3 for instance. What will be stored in dp[3]? The maximum revenue that can be generated till x[3]=14 units length of the road, if placing the current billboard i.e. the 3rd billboard (or billboard at 14 units length) is mandatory. - Direction of solving
The direction of solving is very clear in this case. The maximum revenue that can be generated by placing the 0th billboard is the revenue by 0th billboard only as there is no billboard before it. So, the smallest problem is on index 0. Hence, the direction of solving will be from 0 to n-1 where n is the number of billboards. - Traverse and solve:
Now let us start traversing from the index=1. At 9index 1, we want to find the maximum revenue till the length x[1]=8 units length of the rod, if this billboard (1st billboard at 8 units length) is mandatory to be selected.
So, if it is mandatory to select this billboard, the revenue will have at least its cost included. We have only one billboard before this billboard and we are given that we must have more than 3 units distance between two boards. The distance between the current board and the previous board is x[1]-x[0]=8-6=2. This is less than the required distance and hence we would not be able to select the 0th billboard and will only select this billboard. So, the max revenue=rev[1]=8.
Now, let us move to index 2. Again, it is mandatory to select the 2nd board now. So, the revenue will be at least 5 units.
Now, we will check whether we can put any billboards before this current billboard. So, the current billboard is at 12 units location and the revenue for it is 5. The 0th billboard can be selected as it is present at 6 units location and the difference between the current billboard location (12) and the 0th billboard location (6) is 12-6= 6 >3. So, if we put the 0th billboard and then the 2nd billboard, the revenue that can be generated is 5+5=10.
We can also select the 1st billboard in this case because the difference between their locations is 12-8=4>3. So, the revenue in this case will be rev[1] + rev[2]=8+5=13.
So, the maximum revenue that we can generate till this location when the current billboard is mandatory to be selected is 13.
Now, we are at index 3. So, it is mandatory to select this billboard i.e. x[3]=14 units location. Let us now see what the max revenue that can be generated. So, can we select the 0th billboard? Think!!!!
Ye, we can as the distance between them is greater than 3. The total revenue in this case will be 5+3=8.
If we select the 1st billboard, the revenue will be 8+3=11.
We can't select the 3rd billboard as the distance between them is less than 3. So, we have to select a maximum from 11 and 8 and the answer is 11.
So, dear reader, we hope that you have understood the process till here. We recommend you refer to the solution video to understand the concept and clear your doubts regarding it if any. We also request you fill the last element of this dp array yourself. The completely filled array is shown below:
So, the max revenue that we can generate following all the given conditions is 14 and that is when we select the 1st, 2nd and 4th billboard.
Note: It is not necessary that the answer will be dp[dp.length-1]. The answer will be maximum value stores in the dp array. You can easily conclude this by looking at the dp array above as it is not sorted.
Now that we have understood the complete procedure, let us write the code for the same.
import java.util.Scanner;
public class Main{
public static int solution(int m , int[] x, int[] rev, int t) {
int[] dp=new int[x.length];
int ans=0;
dp[0]=rev[0];
for(int i=1;i< x.length;i++)
{
int max=0;
for(int j=0;j< i;j++)
{
int dist=x[i]-x[j];
if(dist>t)
{
max=Math.max(max, dp[j]);
}
}
dp[i]=max+rev[i];
ans=Math.max(ans,dp[i]);
}
return ans;
}
public static void input(int []arr,Scanner scn){
for(int i = 0;i< arr.length;i++){
arr[i] = scn.nextInt();
}
}
public static void main(String []args){
Scanner scn = new Scanner(System.in);
int m = scn.nextInt();
int n = scn.nextInt();
int x[] = new int[n];
input(x, scn);
int revenue[] = new int[n];
input(revenue,scn);
int t = scn.nextInt();
System.out.println(solution(m, x, revenue, t));
scn.close();
}
}
java;
true";
The above code is written and explained in the solution video (). You may refer to it if you have any doubts about it.
Analysis
Time Complexity:
The time complexity of the above solution is O(n2) where n is the number of billboards as we have a nested loop and the inner loop runs for n(n+1)/2 times. Why? Think!!!
Space Complexity:
The space complexity of the above solution is O(n) as we have created an array of size n where n is the number of billboards.
Method 2:
In the previous method, the complexity of the code was dependent on the number of billboards. In this method, it will depend upon the length of the road. So, we were given a road of length 20. So, let's start the procedure.
- Storage and Meaning
We will make a dp array of size equal to length of the highway plus one and each element in dp will represent the maximum revenue that can be generated till that position. Here, there will be some positions where we can keep the billboard and many places where we can't. Even in the positions where we can keep a billboard, it is not mandatory for us to select the current billboard that we are at like the previous method.
- Direction of Solving:
The direction of solving will be from 0 to m-1 where m is the total length of the road. This is because the smallest problem is at index 0 and the largest problem is at index m. Why? Think!!! - Traverse and Solve:
Let us now traverse this matrix and try to fill it.
If we are at a position where the billboard cannot be placed then dp[i]=dp[i-1]. This is because we don't have a billboard to place here and the max revenue will be based only on the billboards placed earlier.
Also, in this case, dp[0]=0 as there is no billboard at index 0 and positions before it don't exist. In our example, the first billboard is at index 6. So, before that, every value will be 0.Now, at index 6, we have the first billboard. So, the max revenue that can be generated here is the revenue that we can generate from this particular billboard only.Now, the next billboard is at index 8. So, at index 7, we will copy the previous max value only.
At index 8, we have 2 choices, first is not to select this billboard and the other to select it. If we do not select this billboard, the revenue will remain the previous maximum i.e. 5. If we select it, its revenue 8 will be added to the max revenue generated of the previous billboards. But, those billboards should be more than T=3 distance away from index 8. So, we will add dp[i-k-1] to rev[i] and this will be the value that we will store at dp[i].Again till index 12, we have the previous max revenue copied.Let us now look at dp[12]. Here, we will store rev[12] + dp[8] (already discussed above). So, the answer will be 8+5=13.
So, we will continue this procedure and fill this array completely. We hope that you have understood this procedure. You may refer to the solution video to understand this procedure completely and clear your doubts regarding this procedure if any.Now that we have understood the procedure, let us write the code for the same.
import java.util.Scanner;
public class Main{
public static int solution(int m , int[] x, int[] rev, int t) {
int[] dp = new int[m + 1];
int j = 0;
for(int i = 1; i <= m; i++) {
// System.out.println(i+" "+j);
if( j < x.length && x[j] == i) {
dp[i] = Math.max(dp[i - 1],(i - t - 1 >= 0 ? dp[i - t - 1] : 0) + rev[j]);
j++;
}else {
dp[i] = dp[ i - 1];
}
}
return dp[m];
}
public static void input(int []arr,Scanner scn){
for(int i = 0;i< arr.length;i++){
arr[i] = scn.nextInt();
}
}
public static void main(String []args){
Scanner scn = new Scanner(System.in);
int m = scn.nextInt();
int n = scn.nextInt();
int x[] = new int[n];
input(x, scn);
int revenue[] = new int[n];
input(revenue,scn);
int t = scn.nextInt();
System.out.println(solution(m, x, revenue, t));
scn.close();
}
}
java;
true";
The above code is written and explained in the solution video (). You may refer to it to clear your doubts. Let us now discuss the time and space complexity of this solution.
Analysis
Time Complexity:
The time complexity of the above solution is O(m) where m is the length of the highway because we have just traversed an array of size m+1 once.
Space Complexity:
The space complexity of the above solution is also O(m) as we have created a dp array of size m+1.
So, dear reader, we hope that you have understood the complete solution. Still, if you have any doubts regarding anything, refer to the complete solution video to clear them. With this, we have completed the article.
