SOLDVAL - Editorial

editorial
, , ,
2

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';
}

}

3

Setters python solution is giving wrong ans. someone please explain

4

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:

5

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

6

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

8

Yeah I got it . Thank u so much

9

@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 )

10

@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.

11

ok I will try with this , thank you

12 
#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

13

obviously its O(N^2) solution.

14

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

15

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.

16

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)
18

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
19

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

20

Thank you… I got it now!

21

Thank you

22

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

23

We are storing minimum prefix and suffix for every element right ? Later, we are just taking min of prefix and suffix.