ASHMHF - Meet Her Fast! Editorial or Solution Latest Problem SPOJ - Unleash-Coding-Skills

Wednesday, 8 August 2018

ASHMHF - Meet Her Fast! Editorial or Solution Latest Problem SPOJ


ASHMHF - Meet Her Fast!


This is editorial for ASHMHF - Meet Her Fast 

Points to noted:
We need to sort the array to apply the logic and you must keep trace of the original array for printing the result in the end.

See the small example this is only we implemented in the solution.
Suppose the distance array be after sorting:

a0 a1 a2 a3 a4

a0 > a1> a2 > a3> a4
It is also given in question the positions are distinct so there will not be "Equal to" case.
Suppose we have to find the distance of a1 from the remaining position the logic is here.

(a1-a0)+(a2-a1)+(a3-a1)+(a4-a1)

. . . .


By simplifying this we get a formula Suppose we consider our array as zero-based indexing.

total distance for a1 to others =  ((left-right)*arr1[i])-farwardsum[i-1]+backwardsum[i+1];

simple (left - right) here means (number of elements on the left side of a1 - the number of elements on the right side of a1).
Here forwardsum means sum of all elements before a1 and backwardsum means the sum of all elements after a1.

Similarly like 'a1' we apply the logic to find the distance's for other elements in the array and we will find the minimum distance among all and later we will find the corresponding element associated with it in the distance(here it is ans array) and we will print the index.

Corner Case:
If the minimum distance is applied for  multiple  elements (i.e minimum distance is there for more than 1 element in array) In such a case we will identify the least index in original array and print as the output.

The CPP solution for the problem ASHMHF - Meet Her Fast :

#include <cmath>
#include <cstdio>
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
   int t;
    long long int n,i,j,k,ii,sum;
    cin>>t;
    vector<long long>farwardsum(100002),backwardsum(100002),arr1(100002),arr2(100002),ans(100002);
    vector<long long>br;
    for(ii=0;ii<t;ii++)
    {
        cin>>n;
        sum=0;
    farwardsum.clear();
        backwardsum.clear();
        arr1.clear();
        arr2.clear();
        ans.clear();
        long long int sum=0,p;
        for(i=0;i<n;i++)
        {
            cin>>p;
            arr1.push_back(p);
            arr2.push_back(p);
            farwardsum.push_back(0);
            backwardsum.push_back(0);
            sum+=arr1[i];
        }
      sort(arr1.begin(),arr1.end());
        for(i=0;i<n;i++){
            farwardsum[i]=arr1[i];
            backwardsum[i]=arr1[i];
        }
      for(i=1;i<n;i++)
      {
          farwardsum[i]=farwardsum[i]+farwardsum[i-1];
      }
        for(i=n-2;i>=0;i--)
        {
            backwardsum[i]=backwardsum[i]+backwardsum[i+1];
        }
        long long t1,t2;
        ans[0]=abs((sum-arr1[0])-(n-1)*arr1[0]);
        ans[n-1]=abs(((n-1)*arr1[n-1])-(sum-arr1[n-1]));
        long long left,right;
        for(i=1;i<n-1;i++)
        {
            left = i+1;
            right = n-i;
            ans[i] = ((left-right)*arr1[i])-farwardsum[i-1]+backwardsum[i+1];
        }
        long long mini = ans[0],index=0;
        for(i=0;i<n;i++)
        {
    
            if(mini>ans[i]){
                
                mini=ans[i];
                index=i;
            }
        }
        br.clear();
        for(i=0;i<n;i++)
        {

            if(ans[i]==mini)
            {
                br.push_back(arr1[i]);
            }
        }
        long long ind = n;
      for(i=0;i<br.size();i++)
      {
          long long ci = br[i];
          for(j=0;j<n;j++)
          {
              if(ci==arr2[j]&&ind>j)
              {
                  ind = j;
              }
          }
      }
       cout<<"Case "<<ii+1<<": "<<ind+1<<endl;
    }
    return 0;
}




The C solution  for the problem with another approach with same logic for ASHMHF - Meet Her Fast :


#include <stdio.h>

#include <string.h>

#include <math.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b)
{
    if( *(long long int*)a - *(long long int*)b < 0 )
        return -1;
    if( *(long long int*)a - *(long long int*)b > 0 )
        return 1;
    return 0;
}
int main() {
    int t,ii;
    scanf("%d",&t);
    for(ii=0;ii<t;ii++)
    {
        int n,i;
        scanf("%d",&n);
        long long int s1=0,s2=0,s=0,j,a[n],c[n],b[n],max;
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            s=s+a[i];
            c[i]=a[i];
        }
        qsort(a+1,n,sizeof(long long int),cmpfunc);
        for(i=1;i<=n;i++)
        {
            b[i]=s1;
            s1=s1+a[i];
        }
        for(i=1;i<=n;i++)
        {
            b[i]=((i-1)*a[i]-b[i])+((s-b[i]-a[i])-a[i]*(n-i));
        }
        max=b[1];
        for(i=1;i<=n;i++)
        {
            if(max>b[i])
            {
                s2=i;
                max=b[i];
            }
        }
        s2=n+1;
        for(i=1;i<=n;i++)
        {
            if(max==b[i])
            {
                for(j=1;j<=n;j++)
                {
                    if(c[j]==a[i])
                    {
                        if(s2>j)
                          s2=j;
                    }
                }
            }
        }     
        printf("Case %lld: %lld\n",ii+1,s2);
    }
    return 0;
}

Happy Coding........

Tags:

ASHMHF,ashmhf,ASHMHF - Meet Her Fast!,ASHMHF - Meet Her Fast! Editorial or Solution Latest Problem SPOJ,ASHMHF - Meet Her Fast! Editorial ,ASHMHF - Meet Her Fast! Solution Latest Problem SPOJ,ASHMHF - Meet Her Fast!  SPOJ , ASHMHF - Meet Her Fast! Editorial or Solution Latest Problem SPOJ

No comments:

Post a comment