I am solving PAIRSUM2 problem of September Lunch Time. My solution is here. I don’t know which test case it is failing.
Please help me with this.
Your calculation of A seems wrong. How do you know that A0 is 10? Apparently there is no way to calculate A with the given information (n unknowns, n-1 equations). But you can calculate certain (not all) sums with the use of the given information.
Okay, I got it. I have assumed A[0] = 10, if I assume other value then output will be different?
Sure, test it yourself. Idea is to determine the value of Ap + Aq by adding and subtracting values in the whole range from p to q.
Example p = 1, q = 4
By definition:
B1 = A1 + A2
B2 = A2 + A3
B3 = A3 + A4
And you need to add A1 and A4.
We can achieve this by: B1 - B2 + B3 = A1 + A2 - A2 - A3 + A3 + A4 = A1 + A4.
Hey bro @denjell , I have exactly done like what you mentioned above. The code works for all the test cases I could think of but the solution isn’t accepted. Could you please help me getting at least a test case for which it might fail ?
#include <iostream>
using namespace std;
int main() {
int t, *p;
cin >> t;
while(t--){
int n, q;
cin >> n >> q;
p = new int[n - 1];
for (int i = 0;i < (n - 1);i++)
cin >> p[i];
while (q--) {
int a, b;
cin >> a >> b;
int k;
k = a - b;
k = abs(a - b);
if (k ==1 ) {
int m;
a < b ? m = a : m = b;
cout << p[m-1] << endl;
}
else if (k % 2 == 0) {
cout << "UNKNOWN" << endl;
}
else {
int res=0;
int* e = NULL ;
a < b ? e = &p[a-1] : e = &p[b-1];
for (int h = 1;h < k;h++)
e++;
for (int s = 0;s < k;s++) {
if (s % 2 == 1) {
res = res - (*e);
}
if (s % 2 == 0) {
res = res + (*e);
}
e--;
}
cout << res << endl;
}
}
}
}Subtask 1 you will get correct by replacing
int res = 0;
with
int64_t res = 0;
Because sum could be larger than 32 bit integer.
For subtask2 you need further optimisation. Havent done it myself but would use some kind of prefix sum array to calculate value of range with one calculation instead of iterating through whole subarray for each query.