Minimum Loss

Problem Link:

https://www.hackerearth.com/challenges/college/knuth_cup_qualifier_2k19/algorithm/6599213fecb34fa8ad13d0740e75deaa/

Basically in this problem we are given an array
We have to find minimum A[i]-A[j]
Such that i>j and A[i]>A[j]

Pls help in this problem…
@karangreat234
@nuttela
@s5960r

I am using upper bound in sets but still wrong answer

Use some precomputation :wink:

Now think along it… I’ll tell you the full method in 10 mins if u are unable to figure out

Basically do binary search each time.

  1. When you traverse along the array and if you are at an current index i, then all the previous indices (1 -> i-1) are j’s indices. They are sorted [I will tell how as you go through below steps].
  2. Now take this i’th index value and insert it in a proper position using Binary search technique because 1 -> i-1 are sorted. Also, during binary search find the immediate smallest element that is smaller than the current i’th element.
    a) Now the [element which was in ith position] - [It’s immediate previous element after binary search insertion] will be minimum for this i’th element.
  1. Now as you see, based on step, 2 you have inserted the ith index element in a sorted position [That’s why I told 1 -> i - 1 will always be sorted].
  1. Repeat process 1 -> 3 and find the minimum difference.

Hope it helps. :slight_smile:

it takes O(n) time to insert element in between of vector or array.

O(log n) to use binary search
and use linked list to insert in between two elements in O(1).

binary search on linked list is never a good choice. your same logic with set is nice option.

Set neither “maintains order” nor holds “duplicates” unless you do some crazy things like using LinkedHashSet (or) Hacky-Comparator to allow duplicates [Still not better as you need to use TreeSet in that case]. Too much of desicion makings and no proper way of using them.

Linked list seems best here, afaik. DataStructures are fine. It is always a comparable desicions to use. Since inserting in the middle takes O(1) operation, I suggested LinkedList. Incase using Vector/ArrayList makes the insertion [elsewhere] O(n) in worstcase. Set, no way!

i want you to solve this question using linkedlist and multiorderset both , you will get to know a difference.

1 Like

Ohh! will try that :slight_smile:

code

Here’s the code using lower_bound and set from C++ STL.

It’s passing all test cases except 1, It’s giving TLE :frowning_face:

Might be some corner case I’m missing. Try and debug someone. I’ll do it later

2 Likes

i have solve it 90% one test case cross time limit
if you want i share you the logic

is this can be solved using bit and hashing like in case of inversion counting??

your code is failing on 2 test cases

1 wrong answer and 1 TLE

Now your code give wrong answer at one input.
By changing one line TLE is removed…
Instead of using lower_bound(s.begin(),s.end(),num[i])
USE
s.lower_bound(num[i])…
for explanation refer https://codeforces.com/blog/entry/20553
I hope it will help

thanks !! are you able to figure out corner case

Yes…
Link-https://ide.geeksforgeeks.org/q6wqxFuFRF

Seems a really easy question. Just use upper_bound on set.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, loss = INT_MAX;
    cin >> n;
    set<long long> st;
    
    for(int i = 0; i < n; ++i) {
        long long num;
        cin >> num;
        
        if(st.find(num) != st.end())
            loss = 0;
        
        else {
            auto ub = st.upper_bound(num);
            if(ub != st.end())
                loss = min(loss, *ub - num);
        }
        
        st.insert(num);
    }
    
    cout << loss << endl;
}

//You can check this successful solution done in C.

#include<stdio.h>
#include<stdlib.h>
void merge(long long* arr, int low,int mid,int high){
long long L[mid-low+2];
long long R[high-mid+1];
for(long i=0;i<mid-low+1;i++){
L[i]=arr[low+i];
}
for(long i=0;i<high-mid;i++){
R[i]=arr[mid+i+1];
}
L[mid-low+1]=100000000000000000;
R[high-mid]=100000000000000000;
long count1=0;
long count2=0;
for(long i=low;i<high+1;i++){
if(L[count1]<R[count2]){
arr[i]=L[count1];
count1++;
}else{
arr[i]=R[count2];
count2++;
}
}
}
void mergesort(long long* arr,int low,int high){
if(low==high){
return;
}else{
int mid=(low+high)/2;
mergesort(arr,low,mid);
mergesort(arr,mid+1,high);
merge(arr,low,mid,high);
}}
int search(long long* arr,long long a,int length){
for(int i=0;i<length;i++){
if(arr[i]==a){
return i;
}
}
}
int main(){
int length;
scanf("%d",&length);
long long* arr=(long long*)malloc(lengthsizeof(long long));
long long
array=(long long*)malloc(length*sizeof(long long));
for(int i=0;i<length;i++){
scanf("%lld",&arr[i]);
}
for(int i=0;i<length;i++){
array[i]=arr[i];
}
mergesort(arr,0,length-1);
long long min=100000000000000000;
for(int i=length-1;i>0;i–){
if(arr[i]-arr[i-1]<min){
if(search(array,arr[i],length)<search(array,arr[i-1],length)){
min=arr[i]-arr[i-1];
}
}
}
printf("%lld",min);
free(arr);
free(array);
return 0;
}