PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
SIMPLE
PREREQUISITES:
Greedy
PROBLEM:
You are given an array A of N distinct integers. You are also given an array B of N-1 distinct integers. Determine the smallest possible positive integer X such that B_i-X exists in A, for all valid i.
It is guaranteed that X exists.
EXPLANATION:
Sort A and B. Then A_1 is the smallest element of A, and A_N the largest. Similarly with B too.
Claim: X is either B_1-A_1 or B_1-A_2.
Proof
Since array B was generated using N-1 elements of A, exactly one element of A was left out. Therefore, at least one of \{A_1,A_2\} was selected to generate array B.
Say A_1 was selected. Since X was added to each selected term to create array B, A_1+X is still the smallest term, corresponding to the smallest term in B. Thus A_1+X=B_1 implies X=B_1-A_1.
A similar argument can be made for when only A_2 is selected.
All that remains now is to set X to each of the two possible values and validate if B_i-X exists in A, for all i. This can be done efficiently using hash tables.
If both values are possible, select the smallest positive value of the two.
TIME COMPLEXITY:
Sorting A and B takes O(N\log N) each. Checking if B_i-X exists in array A, for all i, takes O(N) using hash tables.
The total time complexity per test case is thus:
O(2*(N\log N)+N+N) \approx O(N\log N)
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
2 Likes
hey can somebody figureout where is the prblm in my algorithm,
so, i took sum of all element of a ,lets say sum(a).
i.e, a1+a2+a3+…+aN=sum(a).
then took sum of all elements of b,lets say sum(b)
i.e, b1+b2+b3+…+bN-1=sum(b).
now we can show that the value of required answer will satisfy the one of the value form below set
s={x|x(i)=(sum(b)-sum(a)+a[i])/(n-1)};
if sum(b)-sum(a)+a[i]) is divisible by (n-1).
then take the least positive value from the set and that would be our answer…
26 Likes
i did the same and got WA in 1st task , I cant find my mistake too
5 Likes
i am having the same issue, pls tell me if u find any reason why this logic is failing
same bro
i want to know mistake in this approach
Same thought bro. Still haven’t figured out what went wrong in the first task. Wish they(codechef) provided at least the test cases once the contest is over
need help
why this logic is wrong
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
while(t–){
ll n;cin>>n;
ll k=n-1;
int *a=new int[n];
ll sum1=0,sum2=0;
for(ll i=0;i<n;i++){
cin>>a[i];
sum1+=a[i];
}
for(ll i=0;i<n-1;i++){
ll temp;cin>>temp;
sum2+=temp;
}
ll ans=LONG_LONG_MAX;
if(n==2){
if((sum2-a[0])>0&&(sum2-a[1]>0)){
ans=min(sum2-a[0],sum2-a[1]);
}
else if(sum2-a[0]>0) ans=sum2-a[0];
else ans=sum2-a[1];
}
else{
for(int i=0;i<n;i++){
ll temp=(sum2+a[i]-sum1);
if(temp%k==0&&temp>=k){
ans=min(ans,(temp/k));
}
}
}
cout<<ans<<endl;
}
}
Credits : @waltzer47
1
3
1 10 12
13 14
this test case has no answer but the approach suggested above gives 7.
So it might happen that an incorrect minimum value is generated by this algo
they already say that there exist atleast one solution of x ri8???
so this is not a valid test case
can anyone explain ,why i am getting WA in subtask 1.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n],b[n-1];
ll suma=0;
for(ll i=0;i<n;i++)
{
cin>>a[i];
suma+=a[i];
}
ll sumb=0;
for(ll i=0;i<n-1;i++)
{
cin>>b[i];
sumb=sumb+b[i];
}
sort(a,a+n);
ll c=(sumb-suma);
ll res;
ll min1=INT_MAX;
for(int i=0;i<n;i++)
{
if(c+a[i]>0 && (c+a[i])%(n-1)==0)
{
min1=min(min1,c+a[i]);
res=(min1)/(n-1);
}
}
cout<<res<<endl;
}
}
2 Likes
It is mentioned in the question that there exists atleast one value of x
Same bro, did the exact same thing, trying to figure out the test case where this may go the wrong from the last 3 hours but everything looks fine to me about this approach.
If somebody figures out the edge case, please share it. This is just making me mad.
1 Like
Yeah ,my approach is same as @bish_1433 . I have wasted more than an hour to find what’s wrong in this logic and still couldn’t figure out the mistake in this logic .
Here is my code CodeChef: Practical coding for everyone
so this input can’t be given as it doesn’t have an answer
what is problem in my solution?
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
void solve(){
ll n; cin>>n;
vector<ll> arr;
ll sum1=0,sum2=0;
for(ll i=0;i<n;i++){
ll x; cin>>x;
sum1+=x;
arr.pb(x);
}
for(ll i=0;i<n-1;i++){
ll x; cin>>x;
sum2+=x;
}
sort(arr.begin(),arr.end());
ll ans=9999999999*1ll;
for(ll i=n-1;i>=0;i--){
ll temp=sum1-arr[i];
ll res=(sum2-temp)/(n-1);
if(((sum2-temp)%(n-1))==0 && res && temp){
if(res>0 && res<ans){
ans=res;
}
}
}
cout<<ans<<"\n";
return;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
ll t; cin>>t;
while(t--){
solve();
}
return 0;
}
same i spend more than hour for this in contest still cant figure out.somebody pls help
ok I have got the proof , so understand this
Intitial array : A[ ]: {a,b,c,d,e}
Array B [ ] : { a+x,b+x,c+x,d+x}
so clearly e was not choosen
so lets say when we are applying our algorithm by excluding a suppose
then the difference in sum is (a+x+b+x+c+x+d+x)-(b+c+d+e) = 4x-e+a
now this difference must be divisble by 4 and we know that e is not a part so 4x-a+e should not be divisible by 4
But what if (e-a) is divisble by 4 , → then leads to wrong answer, based on this anti test cases can be generated
2 Likes