Ryan McGuire wrote:The value for B is a number numBits bits long with each bit set to whichever value has a higher value in profits[bit][].
Ryan McGuire wrote:That guts of that if() figures out the value for that bit in B that would make C[i] < C[j] (with i < j). For instance, in the case above where A[i] = 01111 and A[j] = 01001 (with i < j), when bit=2, we would want to set bit 2 of B to a 1. That way, bit 2 of A[i] would get XORed from a 1 to a 0 and bit 2 of A[j] would get XORed from a 0 to a 1, which would make C[i] < C[j].
Leandro Coutinho wrote:Thanks a lot Ryan!
1)
Why
if ((A[i] >> bit & 1) != (A[j] >> bit & 1)) {
and not:
if (A[i] >> bit != A[j] >> bit) {
?
I tested and it gave the same result for all examples.
2)
In the example "0)", it says that only B=3 returns 8, but debugging it shows that B could also be =2:
profits[0][0] = 1
profits[0][1] = 4
profits[1][0] = 4
profits[1][1] = 4
right?
3)
It's still not clear to me where the xor happens (if it happens).
And I don't understand how he came up with this idea of finding B and the number of pairs and why it works. I'll think more hard here and work through the examples to find out.
Ryan McGuire wrote:I know you said you get it now but I'll answer anyhow:
Leandro Coutinho wrote:Thanks a lot Ryan!
1)
Why
if ((A[i] >> bit & 1) != (A[j] >> bit & 1)) {
and not:
if (A[i] >> bit != A[j] >> bit) {
?
I tested and it gave the same result for all examples.
No it doesn't. If A[i] = 3, A[j] = 1, and bit = 0, then A[i]>>bit & 1 == A[j]>>bit & 1, but A[i]>>bit != A[j]>>bit.
Leandro Coutinho wrote:Yes, it does. Because bit won't reach 0, it stops when bit = 1.
Ryan McGuire wrote:
Leandro Coutinho wrote:Thanks a lot Ryan!
2)
In the example "0)", it says that only B=3 returns 8, but debugging it shows that B could also be =2:
profits[0][0] = 1
profits[0][1] = 4
profits[1][0] = 4
profits[1][1] = 4
right?
I didn't work through the example, but if those values for profits[1][0] and profits[1][1] are correct then yes, B could be either 2 or 3.
Amateurs built google. Professionals built the titanic. We can't find the guy that built this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/ThreadBoostfeature
