CHFM-Editorial

PROBLEM LINKS :

Contest : Division 1

Contest : Division 2

Practice

Setter : Tanay Mishra

Tester : Alipasha Montaseri / Kasra Mazaheri

Editorialist : Anand Jaisingh

DIFFICULTY :

Cakewalk

PREREQUISITES :

Programming language basics

PROBLEM :

Given an array A of size N \ge 2 , you need to find if it is possible to delete an element from the array without affecting the original mean of the array.

QUICK EXPLANATION :

It can be proved that we just need to check if the mean of the originally given array exists in the array. If yes, we need to find the lowest index having such an element.

EXPLANATION :

Let’s loop over each element of the array, and check if it is possible to delete this element, such that the mean of the array before and after deleting this element is the same.

Let the sum of the originally given array be sum. So, the mean of the initially given array is the number \frac{sum}{N}. ( this may not necessarily be an integer ). Now, on deleting the element present at index i, the mean transforms to \frac{sum-A[i]}{N-1}

In an ideal world, just checking if these numbers are equal for each i using long doubles would be enough. However, the world is hardly ideal, and to prevent precision issues of any kind, we need :

\frac{sum}{N}=\frac{sum-A[i]}{N-1}. This condition equals :

sum \cdot (N-1) =N \cdot (sum-A[i]) .

Since each of the individual terms we use above are integers, their products are also integers. So, using this condition, we avoid precision issues of all kinds and deal only with integers. We just need to find the lowest i for which this condition holds.

Additionally :

On simplifying the expression above, we get :

N \cdot sum - sum = N \cdot sum - N \cdot A[i] ,

-sum = - N \cdot A[i] ,

\frac{sum}{N} = A[i] .

This condition shows that the element we needed to remove must actually be the mean of the original array. So, we must just find the smallest element i, such that A[i]=\frac{sum}{N}, or print -1 if such an element does not exist.

COMPLEXITY ANALYSIS :

Time Complexity : O(N)

Space complexity : O(N)

SOLUTION LINKS :

Setter
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll arr[n];
        ll sum=0;
        map <ll , int > m;
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            sum+=arr[i];
            if(m[arr[i]]==0)
            {
                m[arr[i]]=i+1;
            }
        }
        if(sum%n==0)
        {
            ll mean=sum/n;
            if(m[mean]!=0)
            {
                cout<<m[mean];
            }
            else{
                cout<<"Impossible";
            }
        }
        else{
            cout<<"Impossible";
        }
        cout<<'\n';
    }
}
Tester

// KALAM
include<bits/stdc++.h>

using namespace std;
 
const int N = 100000 + 77;
int n , T;
int a[N];
inline void Test() {
   unsigned long long tot = 0;
   scanf("%d" , & n);
   for(int i = 1;i <= n;++ i)
      scanf("%d" , a + i) , tot += a[i];
   for(int i = 1;i <= n;++ i)
      if(tot * (n - 1) == (tot - a[i]) * n) {
         printf("%d\n" , i);
         return ;
      }
   printf("Impossible\n");
}
int main() {
   scanf("%d" , & T);
   while(T --)
      Test();
   return 0;
}
Editorialist
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
// Anand Jaisingh
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef complex<double> base;
typedef long double ld;
typedef long long ll;
 
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi >
 
const int maxn=(int)(2e5+5);
const ll mod=(ll)(1e9+7);
int a[maxn];
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
 
    int t;cin>>t;
 
    while(t>0)
    {
        int n;cin>>n;
 
        ll sum=0;
 
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
 
            sum+=a[i];
        }
 
        int res=-1;
 
        for(int i=0;i<n;i++)
        {
            ll y=sum-a[i];
 
            ll val1=sum*1ll*(n-1),val2=y*n;
 
            if(val1==val2)
            {
                res=i;break;
            }
        }
 
        if(res==-1)
        {
            cout<<"Impossible"<<endl;
        }
 
        else
        {
            cout<<(res+1)<<endl;
        }
 
        t--;
    }
 
    return 0;
}

Comments are welcome !

11 Likes

We should print impossible not -1
though it doesnt matter

1 Like

That further simplification was good .:+1:

1 Like

Damn, I knew my solutions were failing because of precision issues but just didn’t know how to fix it.

Anyway, shouldn’t it be A[i] * N that we need to find instead of sum/N? Because the latter will still have the same precision issue?

3 Likes

Why the space complexity mentioned here is O(N)? Shouldn’t it be O(1) ?

We’ll have to store the initial array.
After storing it, we’ll apply a loop to check for the condition.
Space required will be O(N) for the array of size N

2 Likes

Because if the array size is twice as big then in the worst case the program will take twice the time.
Therefore the complexity is Linear.

What’s the memory used in this code?
It should be less than the 50000 bytes limit right

Best Explanation and nice derivation of the result . I was highly motivated to see this approach. It reminded me of my school days when we used to simplify these kinds of long linear algebraic expressions to condensed form and we are using same concept to solve the problem.
Thanks a lot for such an innovative explanation :slight_smile:

#include
using namespace std;
int main()
{
int T;
cin>>T;
while(T>0)
{
int N;
cin>>N;
long A[N];
long sum=0;
for(int i=0;i<N;i++)
{
cin>>A[i];
sum=sum+A[i];
}
float avg=sum/N;
int i=0;
long k;
while(i<N)
{
if(A[i]==avg)
{
k=A[i];
break;
}
i++;
}
if(k==avg)
{
cout<<k<<endl;
}
else
{
cout<<“Impossible”<<endl;
}
T = T-1;
}
return 0;
}

Can anyone help me with this code? I don’t know where I am doing wrong but I am getting wrong answer for some testcases.

#include

using namespace std;

int main()
{
long int t;
cin >> t;

for(long int i =0 ;i<t;i++)
{

    long int n;
    cin >> n;
    long int a[n];
    for(long int i = 0;i<n;i++)
    {
        cin >> a[i];
    }
    long double c = 0;
    for(long int i = 0;i<n;i++)
    {
        c += a[i];
    }
    c/=n;
    int y = 0;
    for(long int i =0;i<n;i++)
    {
        long int p = a[i];
        a[i] = 0;
        long double x=0;
        for(long int j = 0;j<n;j++)
        {
            x+=a[j];
        }
        x = x/(n-1);
        if(x==c)
        {
            cout<<i+1;
            y++;
            break;
        }

        a[i] = p;
    }
    if(y==0)
    {
        cout<<"impossible";
    }



}

}

i got a SIGEMT error
please help