REMONE - Editorial

editorial
, , ,
63

What is wrong with this code?

#include<bits/stdc++.h>
#define ll long  long int
using namespace std;
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll *arr1=new ll[n];
        ll *arr2=new ll[n-1];
        for(int i=0;i<n;i++)
        {
            cin>>*(arr1+i);
        }
        for(int i=0;i<n-1;i++)
        {
            cin>>*(arr2+i);
        }
        int o=n-1;
        ll min1=LLONG_MAX,max1=LLONG_MIN,min2=LLONG_MAX,max2=LLONG_MIN;
        for(int i=0;i<n;i++)
        {
            min1=min(arr1[i],min1);
            max1=max(arr1[i],max1);
        }
        for(int i=0;i<o;i++)
        {
            min2=min(arr2[i],min2);
            max2=max(arr2[i],max2);
        }
        if(n==2)
        {
            sort(arr1,arr1+n);
            sort(arr2,arr2+o);
            if(arr1[1]>=arr2[0])
            {
                cout<<-(arr1[0]-arr2[0])<<endl;
            }
            else
            {
                cout<<-(arr1[1]-arr2[0])<<endl;
            }
        }
        else if((max2-max1)==(min2-min1))
        {
            cout<<max2-max1<<endl;
        }
        else if(max2<=max1)
        {
            cout<<min2-min1<<endl;
        }
        else
        {
            ll secondmax=LLONG_MIN;
            for(int i=0;i<n;i++)
            {
                if(arr1[i]==max1)
                {
                    arr1[i]=-arr1[i];
                }
            }
            for(int i=0;i<n;i++)
            {
                secondmax=max(arr1[i],secondmax);
            }
            if((max2-secondmax)==(min2-min1))
            {
                cout<<max2-secondmax<<endl;
            }
            else
            {
                cout<<max2-max1<<endl;
            }
        }
    }
}
64

Same here, Couldn’t figure out why its giving wa on first case.

65

What is wrong in my approach? The logic goes this way - for every value at index i (0<=i<n-1) in B I stored the differences b[i]-a[i], b[i]-a[i+1] in a map. At last I traversed the map to find the difference with count==n-1 and as the difference is stored in a map so the value with count==n-1 will be lowest possible. Code is given below:

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define pii pair<int, int>
#define vii vector<pii>
#define make make_pair
#define si unordered_set<int>
#define sll unordered_set<ll>
#define mii unordered_map<int, int>
#define mll unordered_map<ll, ll>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define MOD (int) 1e9+7
#define take(n) int n; cin >> n
void pr(int x) {cout << x;}
void prl(int x) {cout << x << endl;}
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define tc(t) int t; cin >> t; while (t--)
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int max(int a, int b) {if (a > b) return a; else return b;}
int min(int a, int b) {if (a < b) return a; else return b;}
const int dx[4] = { -1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N =  (int)(5 * 1e5 + 10);
vector<vector<int>> divs(N);
void pre(){
    int i, j;
    for1(i, N-1){
        for(int j=i;j<N;j+=i)
            divs[j].pb(i);
    }
}
ll add(ll x, ll y) {ll res=x+y; return res>=MOD ? res-MOD:res;}
ll mul(ll x, ll y) {ll res=x*y; return res>=MOD? res%MOD:res;}
ll sub(ll x, ll y) {ll res=x-y; return res<0? res+MOD:res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){ if (y&1) res=mul(res, x); y >>=1; x=mul(x, x);} return res;}
ll mod_ind(ll x) {return power(x, MOD-2);}

int main(){
//#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//#endif

    fio;
    tc(t){
        take(n);
        int arr[n], brr[n-1];
        for (auto &i: arr)
            cin >> i;
        for (auto &i: brr)
            cin >> i;
        sort(arr, arr+n);
        sort(brr, brr+n-1);
        if (n==2){
            int ans;
            if (brr[0]-arr[1]>0)
            ans=brr[0]-arr[1];
            else
            ans=brr[0]-arr[0];
            cout << ans << "\n";
            continue;
        }
        
        map<int, int> mp; 
        for (int i=0;i<n-1;i++){
            mp[brr[i]-arr[i]]++;
            mp[brr[i]-arr[i+1]]++;
        }
        int ans;
        for (auto i:mp){
    // 		if (i.first<0)
    // 		continue;
            if (i.second==n-1){
                ans=i.first;
                break;
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

please help!!

71

could someone help me find the error in my code

import java.io.*;
import java.util.*;
class Main
{
	public static void main(String args[]) throws IOException
	{
		InputStreamReader isr=new InputStreamReader(System.in);
		BufferedReader in=new BufferedReader(isr);
		String s1=in.readLine();
		int t=Integer.parseInt(s1);
		for(int i=0;i<t;i++)
		{
			String s2=in.readLine();
			int n=Integer.parseInt(s2);
			String[] a=in.readLine().split(" ");
			String[] b=in.readLine().split(" ");
			int[] a1=new int[n];
			int[] b1=new int[n-1];
			long suma=0,sumb=0;
			for(int j=0;j<n-1;j++)
			{
				a1[j]=Integer.parseInt(a[j]);
				b1[j]=Integer.parseInt(b[j]);
				suma+=a1[j];
				sumb+=b1[j];
			}
			a1[n-1]=Integer.parseInt(a[n-1]);
			suma+=a1[n-1];
			int ans=0;
			Arrays.sort(a1);
			Arrays.sort(b1);
			if(n>2)
			{
				for(int k=0;k<n-1;k++)
				{
					double x=(sumb-suma+a1[k])/(n-1);
					if(x%1!=0)
					{
						continue;
					}
					int diff;
					if(k==0)
					{
						diff=b1[0]-a1[1];
						if(diff==x)
						{
							ans=diff;
							break;
						}
						else
						{
							continue;
						}
					}
					diff=b1[0]-a1[0];
					if(diff==x)
					{
						ans=diff;
						break;
					}
				}
				double y=(sumb-suma+a1[n-1])/(n-1);
				int diff10=b1[0]-a1[0];
				if(diff10==y)
				{
					ans=diff10;

				}
				System.out.println(ans); 
			}
			else
			{
				int diff1=b1[0]-a1[0];
				int diff2=b1[0]-a1[1];
				if(diff1<0)
				{
					ans=diff2;
				}
				else if(diff2<0)
				{
					ans=diff1;
				}
				else
				{
					ans=Math.min(diff1,diff2);
				}
				System.out.println(ans);
			}
		}
	}
}
73

edge case is of minimizing x, when n=2 or Ai’s are in AP multiple values of x are possible and one more case is x is positive this case i did wrong and wasted my 15 mins in contest

74

if arr is 1 2 3 4 and suppose bob added 1 to each then it will become 2 3 4 5 now consider the case when u are given 2 3 4 now in your map mp[2-1]++;mp[2-2]++; mp[3-2]++;mp[3-3]++;mp[4-3]++;mp[4-4]++
and so on now u iterate from first element of map that is mp[0] which is = 3=n-1;u cosider it as answer and print 0 this cotradicts the fact that x is positive i hope u got the error

1 Like
75

@infinitepro Instead of using extra space to store elements of A in a map, we can simply use Binary Search as initially we have sorted both the arrays A and B which will optimize the space complexity of the solution.

Here is the link to my solution :wink:
REMONE - By dark_coder007

76

Yep, but I think not implementing binary search is worth the memory tradeoff.

77

ohhk I got it. Thanks a lot

78

1
3
1 3 4
3 6
i think this one is the edge case
here is correct answer is 2 but using above approach the answer we get is 1

79

Yeah i made the test case from your proof.

80

you shall see the proof above.

81

I know that your solution was accepted but it’s not correct.
1
8
1 2 3 4 6 7 8 9
4 5 6 9 10 11 12
try the above test case with your code the answer your code gives is 2
while the code provided in the editorial gives 3.

1 Like
82

Thanks for pointing it out. Even I was having doubt but didn’t bother to think much after this had got accepted.

83

I think there is something wrong in test case
x may be -ve , so we must have to check for that , and in that case we have to return b[0]-a[0] (because this can’t be -ve)

85

Guys, found the issue with this approach. This approach gives some extra solutions which are not possible.

For example, consider the test case(Found by @raj_abhinav39):
1
3
1 3 4
3 6
Here, sumA=8, sumB=9.
For A[0]=1, sumB-(sumA-A[0])=2, which is divisible by n-1, giving the answer 1.
But there is no way we can add 1 to any possible combination of array A to get the array B. However, we can get to the arrayB if we add 0 to A[1], and 2 to A[2].
The program written cannot differentiate between the following cases:
a) Adding 0 to one element, 2 to another element. (Incorrect, program thinks correct).
b) Adding 1 to both elements. (Correct, program thinks correct).
In both cases, the final sums (sumA and sumB) remain unchanged, and the program thinks it’s a valid solution, when it’s not.

88

can anyone help me why my approach is wrong?

#include<bits/stdc++.h>
#include
#define ll long long int
#define pb push_back
const ll mod = 1e9 + 7;
// typedef long long int ll;
using namespace std;
// const ll maxx = 1e8 + 10;
// ll a[maxx];
ll _gcd(ll a, ll b)
{
if (b == 0)
return a;
return _gcd(b, a % b);
}
ll pow(ll a, ll b, ll mod)
{
if (b == 0)
return 1;
if (b == 1)
return a;
ll smallans = pow(a, b / 2, mod);
if (b & 1)
return ((smallans * smallans) % mod * a) % mod;
return (smallans * smallans) % mod;
}
int main()
{
#ifndef ONLINE_JUDGE
// For getting input from input.txt file
freopen(“input.txt”, “r”, stdin);

// Printing the Output to output.txt file
freopen("output.txt", "w", stdout);

#endif
ll t; cin >> t;
while (t–)
{
ll n; cin >> n;
vector a(n), b(n - 1);
for (ll i = 0; i < n; i++)
cin >> a[i];
for (ll i = 0; i < n - 1; i++)
cin >> b[i];
if (n == 2)
{
ll ans = LONG_MAX;
if (b[0] - a[0] > 0)
ans = min(ans, b[0] - a[0]);
if (b[0] - a[1] > 0)
ans = min(ans, b[0] - a[1]);
cout << ans << endl;
continue;
}
ll ans = LONG_MAX;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (b[0] - a[0] == b[1] - a[1]) //chooses 3rd
ans = min(ans, b[0] - a[0]);
if (b[0] - a[0] == b[1] - a[2]) //chooses 2nd
ans = min(ans, b[0] - a[0]);
if (b[0] - a[1] == b[1] - a[2]) //chooses 1st
ans = min(ans, b[0] - a[1] );
cout << ans << endl;
}
};

89

can someone help me what is wrong in my approach?
code-

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

int main(){
int t;
cin>>t;
while(t–){

    int n;
    cin>>n;
    long long int a[n],b[n-1];
    
    long long int max1 = INT_MIN,max2 = INT_MIN;

    for(long long int i=0;i<n;i++){
        cin>>a[i];
        max1 = max(max1,a[i]);
    }

    for(long long int i=0;i<n-1;i++){
        cin>>b[i];
        max2 = max(max2,b[i]);
    }

    long long int x;
    x = abs(max1 - max2);
    cout<<x<<endl;

}

return 0;

}

90

https://www.codechef.com/viewsolution/50747709

I need help, Unable to clear One subtask.
Thanks In Advance

91
1 Like