REMONE - Editorial

Yeah i’ll tell you the problem.

Lets say that given test case

4
1 4 3 8
15 8 11

We know from sample ans = 7 for this.

Now think if the b array is changed to 16 7 11, sum of b doesnt change, but but but the answer does’nt hold anymore.

Now in this answer does’nt exist. But there will be cases where this problem of not dealing each bi’s separately will make a problem. :slight_smile:

2 Likes

I thought of the same approach,can someone explain why this was not an optimal solution?

can you tell such about such a test case where answer exists and still the algorithm doesnot work correctly

there’s definitely an issue with the test case for instance consider the following solution
https://www.codechef.com/viewsolution/50399022
for the test case:
1
1 2 3 4 6 7 8 9
4 5 6 9 10 11 12
the above code(which was accepted btw) gives answer 2
but the correct answer is 3.

1 Like

but they say there is atleast one solution,so i do that prblm assumming there is atleast one solution… and i think 16 7 11 for b is not a valid test case with same values of a

@the_eagle_eye can you please give a test case on which the ‘sum’ approach is giving wrong answer, please?

yes based on the explanation which i gave above
the test case is :-
1
5
6 9 15 17 14
13 16 22 24

correct answer : 7 u might get 5

6 Likes

(deleted)

@ankur10 It is guaranteed in the problem that x exists. Hence this test wouldn’t be valid.

thanks, bro

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

2 Likes

ur welcome

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

yeah bro I gave the proof :sweat_smile:

i am getting for your test case

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

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;

}

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?

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";

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