My issue
1
2 3
3 6
8
9
10
in this input my output is showing:
-1
3 6
-1
which is correct but it is showing failed test case why?
My code
#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
void tc(){
int n, q;cin>>n>>q;
int a[100000];
for(int i=0; i<n; i++){
cin>>a[i];
}
sort(a, a+n);
vector<int> vec(n);
int x=0, y=0;
for(int i=0; i<n; i++){
if(i&1){
vec[n-1-y]=a[i];
y++;
}
else{
vec[x]=a[i];
x++;
}
}
// for(auto v : vec)cout<<v<<" ";
// cout<<endl;
int ans=0;
for(int i=0; i<n-1; i++){
ans+=vec[i]+vec[i+1];
}
for(int i=0; i<q; i++){
cin>>x;
x=ans-x;
bool p(0);
int z;
for(int i=0; i<n; i++){
if((vec[i]-vec[0])==x){
y=i;z=0;p=1;
break;
}
if((vec[i]-vec[n-1])==x){
y=i;z=n-1;p=1;
break;
}
}
if(p==0){
cout<<"-1";
}
else{
swap(vec[y], vec[z]);
for(auto v : vec)cout<<v<<" ";
swap(vec[y], vec[z]);
}
cout<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t>0){
t--;
tc();
// cout<<endl;
}
return 0;
}
Problem Link: Check Adjacent Sum Practice Coding Problem - CodeChef
Your code works on those inputs due mere fortune.
There are some issues like:
-
After you sort your array of ints “A”, you distribute each element in the vector “vec” based on their parity. There’s no need for that. That would’ve not been an issue if you haven’t done the next thing.
-
You sum up the elements in the variable “ans” assuming that’s the right arrangement to get any X. Thats false. You need the create a new arrangement for each X (if possible).
-
After getting X, you loop your prearranged array, and only look if the any element and either the first or the last meet X. You ignore any other possibility.
Your code “works” on [3,6] because it does this:
- The prearragement swaps it to [6,3]
- It sums 9
- When you get the 9 from Q, it gets your X to 0.
- On the first iteration of your loop right after, i=0
vec[i] is 6, and vec[0] is also 6, so 6-6 will be 0, and fakes your flag “p”.
- Then it’s printed.
This code will only work (maybe) for an array of two elements
I think this is more due a misunderstanding of the statement and contraints than actual bad implementation.
-
Problem is asking you to rearrange the array, so that you get any (possible) arrangement f(A) == X.
This is mainly why your code was wrong since the begining. You must create an arragement for each X (if possible), not before.
-
You won’t performe the summing up for every loop. That probably will get TLE. I don’t know. Sounds like a horribly O(n^2) impementation.
-
The function f(A) for any array is:
(a1+a2) + (a2+a3) + … + (a[N-2]+a[N-1]) + (a[N-1]+aN) =
a1 + 2(a2 + a3+ … + a[N-2] + a[N-1]) + a[N]
-
Note that the sum for f(A) is reduced to:
2 * sum(A) - a1 - aN
where “sum” is the sum of all elements
-
If you want an arragement so f(A) == X, the you should look for an i,j in A to be rearranged to the front and back of the array, so:
X == 2 * sum(A) - ai - aj
(if possible)
Let me share you my solution to this problem:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
// Get the elements
ll N,Q;
cin >> N >> Q;
// Fill the vector
vector<ll> A(N);
for(ll i=0; i<N; i++){
cin >> A[i];
}
// Get the sum of all the elements inside
ll total_sum = accumulate(A.begin(), A.end(), 0);
// Iterate all the Queries
for(ll q=0; q<Q; q++){
ll X;
cin >> X;
// Check for all the possible pairs
// Flag to know if possible
// Two variables 'l' and 'r' to know what pair would be
bool possible = false;
ll l, r;
for(ll i=0; i<N-1; i++){
for(ll j=i+1; j<N; j++){
if(2*total_sum - A[i] - A[j] == X){
possible = true;
l = i;
r = j;
}
if (possible) break;
}
if (possible) break;
}
// Print the array (if possible)
// l and r must be at the edges
if (possible){
cout << A[l] << " ";
for (ll i=0; i<N; i++){
if ((i != l) && (i != r)){
cout << A[i] << " ";
}
}
cout << A[r] << "\n";
}
else{
cout << "-1\n";
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while(T--){
solve();
}
}
Hope this is helpful. 