REMONE - Editorial

editorial
, , ,
25

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

26

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

27

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
28

(deleted)

29

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

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