Hello!
After taking the afternoon debugging, I made enough tests to spot what is wrong, although I can not explain why, (you’ll see that the why is not the most important here).
I summarize my comments, so someone with better understanding can lead us directly to the explanation to why without making all this debugging work.
Theses were my tests:
1- Is this an issue of understanding the problem or its implementation?
2- What sections of the code work?
3- What is doing the wrong section?
4- Is this a problem of the language or the implementation?
5- General comments and conclusions
6- I share your code, but commenting every step for anyone could see step by step
7- I share my commented C++ submission
- Understanding vs Impementation
CheckAdjacentSum is a problem in which you should, by any deduction, conclude that any possible input X should follow this equation:
X = 2*sum(A) - A[i] - A[j]
where:
"A" is the array
"sum" is the sum of all elements of A
"i" and "j" any different index of A
You indeed understood the problem. There is no doubt about that. Actually, you tried an interesting approach to how to find these to i and j indexes. The issue is in the implementation.
- Sections working
Your code is roughly divided in 3 sections:
- Getting the input of the variables.
- Looping to find the needed pair i,j
- Printing
I used different parts of different codes, and I could conclude that your problem is in the looping part. The apprantly clever implementation of using map DS was counterproductive.
After trying once, and once again with different test and conditionals, I can assure that your map is indeed throwing a number between 1 and N, but not the one that is useful for the problem, the problem is the map approach. Why? I don’t know.
- What is doing the wrong section?
You use your “key” variable and the map for two porpuses:
- Flag to know if X query input is possible
- Spot where the the j in the pair i.j is
Surprisingly, it worked as a flag even using other proved code sections. Moreover, I could also prove it always throws a number between 1 and N.
Even more suprising, it does not always work to find either i and j. God knows why you map does one thing good the another wrong.
- Is this a problem of the language or the implementation?
I tried translating your code to Python, and throws the same errors. So we can assume that C++ was doing the right thing. It was a problem of implementation, not a language problem.
- General comments and conclusions
I used my afternoon to this because I’m a fan of C++ and Python. I’m more of a debugger or QA than actually a competitive programming fan. BUT it is important to know what competitive programming is. And this is definitely not using an entire day to debug. If you can’t solve a 1500 problem whitin 30 minutes, there’s likely 4 reasons:
- You are not concentrated
- You don’t have enough background to understand the problem.
- You don’t have enough knowledge of the programming language
- You tried an implementation you shouldn’t have.
This falls in the 4rd.
From the very beginning, you knew your map wasn’t actually tracking the position of all the elements. I actually thought you were thinking out of the box, and that’s a great skill!
But that is also a “try-catch” movement. Since all these competitive programming problems are closed tested problems, you can assume there is an answer. You definitely can try to think out of the box. But if the implementation is giving problems, and you know it was a risky approach, you’d better try another approach.
If someone knows ever knows why this fails, that’d be more of mathematical curiosity. But you should have tried another approach since it failed, well knowing it was risky.
- Commented C++ code and Python equivalent
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t>0){
// Get the size of the Array (n) and number of Queries (q)
t--;
int n,q,key,sum=0;
cin>>n;
cin>>q;
/*
Store the elements into an array
Store the index (base 1) of each element in a map, but in a risky way,
map is only tracking the last element position
Summing up *2 while reciving, so the total is 2*accumlate()
*/
map<int,int>m;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
m[a[i]]=i+1;
sum+=a[i]*2;
}
// "qnn" is what problem states as "X"
// "qn" is 2*accumlate - X, so the difference to find
int qn;
int qnn;
for(int k=0;k<q;k++){
key=0;
cin>>qnn;
qn = sum-qnn;
// Runs the array of ints... looking for the pair?
for(int j=0;j<n;j++){
/*
a[j] represent the element of the array we are in
qn -a[j] ... are you lookin for the complement?
if m[qn -a[j] ] points to something in the map...
... and that pointing is more than j+1?
I'd be logical what you don't want is your 1-indexed
map points to itself j+1 (which would be 1-index fixed),
and altough this should work, the most according to the
context statement would be:
m[qn-a[j]] != j+1
However, let's take into consideration that you don't
have all the elements. I don't really know what is
looking for nor if that approach is optimal.
"key" is one of the pair
Then you swap the pair elements to the corners
*/
if(m[qn-a[j]]!=0&&m[qn-a[j]]>j+1)
{
key=m[qn-a[j]];
int temp=a[0];
int temp2=a[n-1];
a[0]=a[j];
a[j]=temp;
a[n-1]=a[key-1];
a[key-1]=temp2;
break;
}
}
// If the key was changed, then print the array
if(key!=0){
for(int l=0;l<n;l++){
cout<<a[l]<<" ";
}
cout<<""<<endl;
}
else
cout<<"-1"<<endl;
}
}
}
Python equivalant:
# cook your dish here
for T in range(int(input())):
n,q = map(int,input().strip().split())
a = list(map(int,input().strip().split()))
summ= 0
m = {}
for i in range(n):
m[a[i]] = i+1
summ += a[i]*2
for k in range(q):
key = 0
qnn = int(input())
qn = summ-qnn
for j in range(n):
if qn-a[j] in m:
if m[qn-a[j]] > j+1:
key = m[qn-a[j]]
temp = a[0]
temp2 = a[n-1]
a[0] = a[j]
a[j] = temp
a[n-1] = a[key-1]
a[key-1] = temp2
break
if key != 0:
print(*a)
else:
- My solution:
#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 adjacent elements
// Flag to know if possible
// Two variables 'l' and 'r' to know what would be the pair
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)
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();
}
}