Problem Name: Empire Business
Setter: Aman Singhal
Tester: Nishit Sharma
Editorialist: Aman Singhal
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming
PROBLEM:
Given an array of size N. Find the minimum sold value for each index,
Sold value for index i(1<=i<=N) with any index j(1<=j<=N) is defined as : A_j+ |i-j|.
QUICK EXPLANATION:
We can divide the questions into two parts i.e. in the first part we will consider only left elements (j<=i) for calculating sold values and in the second part we will consider only right elements (j>=i) for sold values. We will maintain two dps for each part and then find the minimum of them.
-
For calculating left_dp iterate through 2 to N calculating minimum value as min(A[i],left_dp[i-1]+1).
-
For calculating right_dp, iterate through N-1 to 1 calculating minimum value as min(A[i],right_dp[i+1]+1).
And now minimum value of left_dp and right_dp will be the answer for each index.
EXPLANATION:
First subproblem (Considering only left elements)
For calculating sold value, we will consider the cases where j<=i. This means that we can only select values to the left of that index.
For any index i, let us consider A[i-1] to be the minimum sold value then the minimum sold value of index i will be minimum of (A[i-1]+1 ,A[i]).
So we can start with the 1st index because it does not have any left index and therefore it will be the minimum sold value of its index. Now, for the 2nd index the minimum sold value will be minimum of A[1]+1 and A[2] and so on.
Pseudo Code for his subproblem will be:
Left_dp (A){
for (int i=2; i<=A.size(); i++)
A[i]=min(A[i],A[i-1]+1)
return A
}
Time Complexity for this subproblem will be O(N).
Second subproblem (Considering only right elements)
For calculating sold value, we will consider the cases where j>=i. This means that we can only select values to the right of that index.
For any index i, let us consider A[i+1] to be the minimum sold value then the minimum sold value of index i will be minimum of (A[i+1]+1 ,A[i]).
So we can start with the Nth index because it does not have any right index and therefore it will be the minimum sold value of its index. Now, for the N-1th index the minimum sold value will be minimum of A[N]+1 and A[N-1] and so on.
Pseudo Code for his subproblem will be:
Right_dp (A){
for (int i=N; i>0; i--)
A[i]=min(A[i],A[i+1]+1)
return A
}
Time Complexity for this subproblem will be O(N).
Main Problem
Now in our question sold value for any index i is defined as A_j+|i-j| where 1<=j<=N. So if we know that minimum sold value of i-1th index is A[i-1] and i+1th index is A[i+1], then minimum sold value of ith index will be minimum of A[i-1]+1,A[i+1]+1,A[i]. It is basically a merge of both the above subproblems.
So we will first calculate left_dp considering only left elements and then right_dp considering only right elements. And then our final answer for any index i will be the minimum of left_dp[i] and right_dp[i].
Bonus:
- We can do this problem without creating any additional arrays.
TIME COMPLEXITY:
- Time complexity per test case is O(N).
SOLUTIONS
Setterās Solution (Python 3)
T=int(input())
for _ in range(T):
n=int(input())
A=list(map(int,input().split()))
for i in range(1,n):
A[i]=min(A[i],A[i-1]+1)
for i in range(n-2,-1,-1):
A[i]=min(A[i],A[i+1]+1)
print(*A)
Testerās Solution (C++)
#include<bits/stdc++.h>
#define fab(a,b,i) for(int i=a;i<b;i++)
#define endl "\n"
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{ quick;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
fab(0,n,i)
{
cin>>a[i];
}
vector<int> left_dp(n);
fab(0,n,i)
left_dp[i]=a[i];
vector<int> right_dp=left_dp;
fab(1,n,i)
{
left_dp[i]=min(left_dp[i],left_dp[i-1]+1);
}
for( int i=n-2;i>=0;i--)
right_dp[i]=min(right_dp[i],right_dp[i+1]+1);
fab(0,n,i)
{
cout<<min(left_dp[i],right_dp[i])<<" ";
}
cout<<endl;
}
return 0;
}
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed.
