REMONE - Editorial

editorial
, , ,
30

thanks, bro

31

Sum approach people:
Here is a test case
4
3 6 9 30
13 16 19
Ans is 10

2 Likes
32

ur welcome

33

1 2 5 7 13
6 7 10 12
you can try this test case where X must be 5
but the algorithm gives 2.

1 Like
34

yeah bro I gave the proof :sweat_smile:

35

i am getting for your test case

36

I also have the same problem. Applied the same approach but still WA in every time.

37

Can any one help what is wrong in my code. I am getting Wrong Answer.

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

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--)
{
    int n;
    cin>>n;
    long int a[n],b[n-1];
    long double sa=0,sb=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sa=sa+a[i];
    }
    for(int i=0;i<n-1;i++)
    {
        cin>>b[i];
        sb=sb+b[i];
    }
    unsigned long long int min=ULLONG_MAX;
    unsigned long long int y;
    for(int i=0;i<n;i++)
    {
        long double g = (sb-(sa-a[i]))/(n-1);
       // cout<<"g="<<g<<" ";
        y=g;
        if(g-y==0)
        {
            if(y<min && y>0)
            {
               // cout<<"y="<<y<<" ";
                min=y;
            }
        }
    }
   // cout<<"\n";
    cout<<min<<"\n";
}

return 0;

}

38

I used the same approach as well. Wrong answer in part 1, but correct in part 2.

@ankur_10 Isn’t it guaranteed that an X would always exist?

39

Another approach that is used:
Say the elements of first array are : A1, A2, … An
and the elements of the removed array are: B1, B2,… Bn-1 .

We calculate the frequency of difference between A1, A2, … An-1 and B1, B2,… Bn-1; and between A2, A3, … An and B1, B2,… Bn-1.

The frequency of X must be >= (n-1) as we have added X to n-1 elements. Out of all such values, we take the minimum such X.

One implementation can be:

        map<int, int> diff;
        for(int i=0; i<n-1; i++){
            diff[b[i]-a[i]]++;
        }
        for(int i=0; i<n-1; i++){
            diff[b[i]-a[i+1]]++;
        }
        int m = 0;
        int me = 1e9;
        for(auto &i: diff){
            if(i.second >= (n-1) && i.first>0){
                me = min(me, i.first);
            }
        }
        cout << me << "\n";
40

My solution

Can someone please tell me where i am making the mistake?

My concept is to find sum of array A(sumA) and array B(sumB) then
x will be this

sum=sumA-A[i];
x=(sumB-sum)/(N-1);

then I take the minimum of all the “possible” values of x

41

I have the same problem

43

Same here. I think @ankur_10 was just trying to make point with example. There will be cases where even after changing values in B it will hold valid status.

44

X can do =<0 in your solution, but the problem say it cannot :slight_smile:

45

The problem can be solved without extra space as well. My Solution

46

Thanks for the reply but
Sorry, I couldn’t understand what are you saying.
if x can do negative numbers then the test case which is given in the problem itself is wrong

3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3

the last one output will be -1 because it is minimum according to you

Please correct me if I am wrong

47

Yes please some one tell what is the problem in this approach or tell what is the test case 2 for which it is showing WA so i can figure out my mistake.
This is making me crazy, if anyone can help then please.

1 Like
48

1 2 5 7 13
6 7 10 12
you can try this test case where X must be 5
but the algorithm gives 2.

2 Likes
49

I get it. yes for this test case my approach is giving the wrong answer but can u explain why? Continuing the discussion from My solution

50

Please tell me why my code is giving the wrong output.
I have used the algorithm that - if we have taken only n-1 elements from A and left kth element of A (Ak) and added X to each then -
Sum of elements (B) = (Sum of elements (A) - Ak) + X * (n-1)

#include

using namespace std;

int main() {

long long int T,N,temp,sumB=0,sumA=0;
cin>>T;
while(T--){
    sumA=0;sumB=0;

    cin>>N;
    
    long long int A[N],B[N-1];
    
    for(long long int i=0;i<N;i++){
        cin>>A[i];
        sumA+=A[i];
    }
    
    for(long long int i=0;i<N-1;i++){
        cin>>B[i]; 
        sumB+=B[i];
    }
    
    long long int X=sumB;
    
    for(long long int i=0;i<N;i++){
        temp = sumA-A[i];
        temp = sumB-temp;
        
        if(temp%(N-1)==0 and temp/(N-1)>0){
            
           
           if(X>temp/(N-1))X=temp/(N-1);
           // break;
        }
    }
    cout<<X<<endl;
}
return 0;

}