SOLDVAL - Editorial

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.

13 Likes

Here’s my solution:

#include <bits/stdc++.h>
#include
using namespace std;
#define ll long long int
#define lp(x,y) for(ll i=x;i<y;i++)
#define pb push_back
#define pi 3.14159265358979323846
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main()
{
fastio
ll t;
cin>>t;

lp(0,t)
{
    ll n;
    cin>>n;
    ll arr[n],a1[n],a2[n];
    lp(0,n) cin>>arr[i];
    a1[0]=arr[0];
    lp(1,n)
    {
        if(arr[i]==a1[i-1]) a1[i]=a1[i-1];
        else if(arr[i]<a1[i-1]) a1[i]=arr[i];
        else a1[i]=a1[i-1]+1;
     
    }
    
    a2[n-1]=arr[n-1];
    for(int i=n-2;i>=0;i--)
    {
        if(arr[i]==a2[i+1]) a2[i]=a2[i+1];
        else if(arr[i]<a2[i+1]) a2[i]=arr[i];
        else a2[i]=a2[i+1]+1;
    }
    
    lp(0,n)
    {
        cout<<min(a1[i],a2[i]) <<' ';
    }
    cout<<'\n';
}

}

Setters python solution is giving wrong ans. someone please explain

10 30 20 1 100 In this test case
possible values of
index 1 = 10 31 22 4 105 min(4)
index 2 = 11 30 21 3 104 min(3)
index 3 = 12 31 20 2 102 min(2)
index 4 = 14 33 22 1 101 min(1)
index 5 = 15 34 23 2 101 min(2)
min values are 4 3 2 1 2

according to Tester’s solution
min values would be
10 11 12 1 2

please help me out :slight_smile:

According to tester’s solution also answer will be 4 3 2 1 2.
In tester solution,
left_dp will be 10,11,12,1,2
right_dp will be 4,3,2,1,100
Now minimum of both values will be 4,3,2,1,2

It was not giving wrong answer, there is indentation problem which is giving compilation error and now it is solved.

Yeah I got it . Thank u so much

@aman1108
finding the min sold value for A1
let j=1 ; 1<=i<=N
so values of A1 can be (acc to the condition Aj +| i - j |)
for i = 1 > A1+ | 1-1| = A1
for i = 2 > A1+ | 2-1| = A1+1
for i = 3 > A1+ | 3-1| = A1+2
for i = 4 > A1+ | 4-1| = A1+3
: :
: :
for i = N > A1+ | N-1| = A1+(N-1)
so the minimum of { A1 , A1+1 , A1+2 , … , A1+(N-1)}
will always be A1
similarly with A2 , A3 , A4 , … , An
so the answer should be the input itself.

please tell me what am I thinking wrong ( I am an absolute beginner )

@vishwas_10 you have misread the question. For index i sold value is Aj+|i-j|. So for A1 possible values are:
A1+0,A2+1,A3+2,…,AN+N-1.
And now you have to find minimum of them.

ok I will try with this , thank you

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
for(int k=0;k<t;k++)
  {
    int n;
    cin>>n;
    int arr[n],a[n];
    int h= sizeof(a)/sizeof(a[0]);
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            a[j]=arr[j]+abs(i-j);
        }
        cout<<*min_element(a,a+h)<<" ";
    }
    cout<<endl;
  
    
  }

return 0;
}

it is showing time execution error but I checked the test cases are running fine

obviously its O(N^2) solution.

You have to optimize your solution. For hints you can check the editorial.

Hello @aman1108 it was a very nice question, thank you, and will you please give links to questions related to this kind of dp problems, and what kind of dp category does it falls under? i mean 0-1, merging intervals etc.

I don’t know where my code is failing. Can someone provide me some testcases?

Here's my approach
  1. I tried to find distance from minimum element to every element in the array and stored it in the “mini” array. I traversed the array two times to get this mini array. (to handle the case where there are multiple minimum elements)

  2. Secondly, to get the answer, I traversed the array the array again and answer array is: answer[i] = m if array[i] = m
    else: answer[i] = mini[i]+minimum_ele_of_array
    where mini[i] = smallest distance between minimum element and the current element

Here's the code
for _ in range(int(input())):
    n = int(input())
    *arr, = map(int,input().split())
    ans = []
    if arr==sorted(arr):
        print(*arr)
        continue
    small = arr.index(min(arr))
    j = 1
    i =1
    minimum_ele_of_array = min(arr)
    mini = []
    prev =s
    for i in range(n):
        if arr[i]==minimum_ele_of_array:
            mini.append(0)
            prev=i
        else:
            mini.append(abs(i-prev))
    sr = arr[::-1].index(minimum_ele_of_array)
    prev = sr
    for i in range(n)[::-1]:
        if arr[i]==minimum_ele_of_array:
            prev=i
        else:
            mini[i] = min(mini[i],abs(i-prev))
    i = 1
    while i<=n:
        if arr[i-1]==minimum_ele_of_array:
            ans.append(minimum_ele_of_array)
        else:
            ans.append(mini[i-1]+minimum_ele_of_array)
        i+=1
        j+=1

    for i in range(n):
        ans[i] = min(ans[i],arr[i])
    print(*ans)

You can easily find linear dynamic programming problems in various programming sites and also you can search them in the section ‘search problems by tags’ on codechef.

1 Like

Your code is giving runtime error because you didn’t define s in the line prev=s.
If it is equal to small then for the following TC just check your solution:
6
7
3 5 2 3 7 1 3
6
4 4 9 5 9 3
6
10 9 2 6 1 8
8
1 3 10 8 5 9 9 3
8
8 7 9 1 6 9 2 8
5
5 6 6 9 8

Thank you… I got it now!

Thank you

how can be this problem solve by dp there r no such repeating thing which we can store in table and latter we use the table @aman1108 ?
guys please explain me why this problem solve using dp