Yes, but abs is a function and may not be inlined by the compiler, so you’re doing 2 \cdot 10^{10} subtractions plus abs operations, right?
But any way what you think most of test case can pass this approach ?
From experience, probably not, but I don’t really know how compilers work
Yes this might the case , so can i say 80% will get AC while in 20% due to more loop of abs calling will get TLE
To note, you can do abs quickly with a ternary operator, like so:
int x = a < b ? b - a : a - b;
Look up what that is if you don’t know it
But if they are providing partial marks then can i get AC in some of testcae?
I think it will get AC in most of testcase when n is <10^4
I have no idea how their format works, but yes, 5 seconds is generous for n = 10^4 and you’ll probably pass.
Yes i think i should use this
so it may give me a AC . As i used abs , but i used c++ so i think i will get AC in mostly 70 % testcase . Right?
Any way thanks
@galencolin
Maybe? Like I said, I haven’t done this contest before and don’t really know how it works (why do you have to wait so long for a verdict, anyway?), so I don’t know how much credit you’ll get.
@everule1 can you help in this problem ? I mean what you think as they provide 5 second then can we said that bruteforce will work in more than 70% testcase
I’m talking about this
If there are 10 test case then only atmost 2 TC will pass …
NO why dont you not understanding the actual scenario. All test case are not with n greater than 510000 so for 510000 you will get AC . Yeah surely it will fail in some n greater than 50000 but still you will get definately 70% AC in testcase
@ssrivastava990
Ok bro tu jeeta …maan gaye khush raho
NO , even galencolin is also saying that it will work for 10^4 , and he is 7* so i think …itsright upto some extent
Bro there is no competetion between coder we are just clarifying our issue. Anyways dont take on mind
are bro … HackerEarth TC are very strong (in case of these type of xams ) understand
Y’know, my solution would use C++ specific bitwise magic anyway, I might as well write it out
code
Main idea: exactly what @avenger786 said, just get rid of the abs condition because it’s annoying. Note that it doesn’t matter if we get something “wrong” - that is, we subtract when we should add for something, because it will only reduce the possible answer we consider and we’ll get it “right” later.
long long weird_abs(bool flip, long long a, long long b) {
return flip ? a - b : b - a;
}
int main() {
// read input, etc.
long long ans = -1e18;
for (int mask = 0, mask < (1 << 4); mask++) {
long long values[n];
for (int i = 0; i < n; i++) {
values[i] = weird_abs(mask & 1, 0, a[i]) + weird_abs(mask & 2, 0, b[i]) + weird_abs(mask & 4, 0, c[i]) + weird_abs(mask & 8, 0, d[i]);
}
// compute prefix (pmax) and suffix (smax) maximums over values - too lazy to write this here
for (int i = 0; i < n; i++) {
long long cur_v = weird_abs(mask & 1, a[i], 0) + weird_abs(mask & 2, b[i], 0) + weird_abs(mask & 4, c[i], 0) + weird_abs(mask & 8, d[i], 0);
long long left = i == 0 ? -1e18 : pmax[i - 1];
long long right = i == n - 1 ? -1e18 : smax[i + 1];
ans = max({ans, cur_v + left, cur_v + right});
}
}
cout << ans << '\n';
That looks like homework