- Post Reply Bookmark Topic Watch Topic
- New Topic

programming forums
Java
Mobile
Certification
Databases
Caching
Books
Engineering
Micro Controllers
OS
Languages
Paradigms
IDEs
Build Tools
Frameworks
Application Servers
Open Source
This Site
Careers
Other
all forums

this forum made possible by our volunteer staff, including ...

Marshals:

- Campbell Ritchie
- Liutauras Vilda
- Jeanne Boyarsky
- Devaka Cooray
- Paul Clapham

Sheriffs:

- Tim Cooke
- Knute Snortum
- Bear Bibeault

Saloon Keepers:

- Ron McLeod
- Tim Moores
- Stephan van Hulst
- Piet Souris
- Ganesh Patekar

Bartenders:

- Frits Walraven
- Carey Brown
- Tim Holloway

posted 4 years ago

Hi,

I read the problem's solution but couldn't understand it. So could someone here explain for me how the code works, please?

Problem: http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313

Solution:

http://apps.topcoder.com/wiki/display/tc/SRM+649

I understand the syntax, but not the logic behind this.

Thanks a lot!!

I read the problem's solution but couldn't understand it. So could someone here explain for me how the code works, please?

Problem: http://community.topcoder.com/stat?c=problem_statement&pm=13657&rd=16313

Solution:

http://apps.topcoder.com/wiki/display/tc/SRM+649

I understand the syntax, but not the logic behind this.

Thanks a lot!!

posted 4 years ago

- 1

First, a long, verbose explanation of the algorithm that may or may not clear things up:

-=-=-=-=-=-=-=-=-=-=-=-

Obviously A[] is the sequence of numbers and N a power of 2 that all elements of A[] will be less than.

numBits, is the number of bits in a binary number etbween 0 and N-1, inclusivie. e.g. N=1024 -> numBits = 10

profits[][] and the three nested for() loops are used to determine the value for B.

Specifically, the for loops for i and j, loop through all possible combinations of elements in A[] with i<j. The for loop for "bit" starts at the highest order bit for the possible values of A[i] and A[j]. For instance, when numBits=10, bit starts at 9, which corresponds to the 512 part of the binary numbers. What the 'bit' loop is doing is looking for the highest order bit where A[i] and A[j] differ. For instance, 01111 and 01001 are the same for bits 4 and 3 but differ for bit 2. That difference at bit makes the if() condition true. 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]. The break staement inside the if() makes sure that at only highest order bit that differs between A[i] and A[j] is considered. That's because when two numbers differ at a given bit, any lower-order bits don't matter. e.g. Once we know that 01000 (8 decimal) and 00111 (7) differ at bit 3 with 8 having the higher value for that bit, all the lower order 1s that are present in 7 don't matter.

All pairs of i and j with i<j are checked to determine the value for each bit of B that would make the most [i,j] pairs yield the desired condition. For instance, there may be 6 [i,j] pairs where we want bit 4 to be a 1, 5 pairs where we want it to be a 0 and 10 pairs where it doesn't matter.

We can figure out the best value for B based on the values in profits[][]. The value for B is a number numBits bits long with each bit set to whichever value has a higher value in profits[bit][]. e.g. If profits[4][1] > profits[4][0], then bit 4 of B is 1. Also, profits[][] shows the number of [i,j] pairs that satisfy the desired condition (C[i]<C[j] when i<j) when the given bit in B is set to a given value. e.g. If profits[4][1] = 6, then there are 6 [i,j] pairs that will have C[i] < C[j] if bit 4 of B is a 1.

-=-=-=-=-=-=-=-=-=-=-=-

However, your best bet for understanding what's going on is to just work through the first few examples given in the problem statement.

-=-=-=-=-=-=-=-=-=-=-=-

Obviously A[] is the sequence of numbers and N a power of 2 that all elements of A[] will be less than.

numBits, is the number of bits in a binary number etbween 0 and N-1, inclusivie. e.g. N=1024 -> numBits = 10

profits[][] and the three nested for() loops are used to determine the value for B.

Specifically, the for loops for i and j, loop through all possible combinations of elements in A[] with i<j. The for loop for "bit" starts at the highest order bit for the possible values of A[i] and A[j]. For instance, when numBits=10, bit starts at 9, which corresponds to the 512 part of the binary numbers. What the 'bit' loop is doing is looking for the highest order bit where A[i] and A[j] differ. For instance, 01111 and 01001 are the same for bits 4 and 3 but differ for bit 2. That difference at bit makes the if() condition true. 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]. The break staement inside the if() makes sure that at only highest order bit that differs between A[i] and A[j] is considered. That's because when two numbers differ at a given bit, any lower-order bits don't matter. e.g. Once we know that 01000 (8 decimal) and 00111 (7) differ at bit 3 with 8 having the higher value for that bit, all the lower order 1s that are present in 7 don't matter.

All pairs of i and j with i<j are checked to determine the value for each bit of B that would make the most [i,j] pairs yield the desired condition. For instance, there may be 6 [i,j] pairs where we want bit 4 to be a 1, 5 pairs where we want it to be a 0 and 10 pairs where it doesn't matter.

We can figure out the best value for B based on the values in profits[][]. The value for B is a number numBits bits long with each bit set to whichever value has a higher value in profits[bit][]. e.g. If profits[4][1] > profits[4][0], then bit 4 of B is 1. Also, profits[][] shows the number of [i,j] pairs that satisfy the desired condition (C[i]<C[j] when i<j) when the given bit in B is set to a given value. e.g. If profits[4][1] = 6, then there are 6 [i,j] pairs that will have C[i] < C[j] if bit 4 of B is a 1.

-=-=-=-=-=-=-=-=-=-=-=-

However, your best bet for understanding what's going on is to just work through the first few examples given in the problem statement.

Leandro Coutinho

Ranch Hand

Posts: 423

posted 4 years ago

Thanks a lot Ryan!

Really cool.

So "int bit = numBits - 1", to get the high order bit.

If "int bit = numBits" it would right shift all bits and the number would be zero.

When A[i] < A[j], then A[i] >> bit & 1 equals 0. So:

++profits[bit][A[i] >> bit & 1]; => ++profits[bit][0];

Interesting.

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.

Thanks again.

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][].

Really cool.

So "int bit = numBits - 1", to get the high order bit.

If "int bit = numBits" it would right shift all bits and the number would be zero.

When A[i] < A[j], then A[i] >> bit & 1 equals 0. So:

++profits[bit][A[i] >> bit & 1]; => ++profits[bit][0];

Interesting.

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.

Thanks again.

Leandro Coutinho

Ranch Hand

Posts: 423

posted 4 years ago

Got it.

In the first example:

{3, 2, ...}

i = 0, j = 2

They differ in bit 0, then ++profits[0][]

And to make the changes, the 0 bit of B must be 1, then ++profits[0][1]

Thanks a lot Ryan.

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].

Got it.

In the first example:

{3, 2, ...}

i = 0, j = 2

They differ in bit 0, then ++profits[0][]

And to make the changes, the 0 bit of B must be 1, then ++profits[0][1]

Thanks a lot Ryan.

Ryan McGuire

Ranch Hand

Posts: 1167

11

posted 4 years ago

- 1

I know you said you get it now but I'll answer anyhow:

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.

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.

The XOR happens in line 8. Instead of...

...that line could have been rewritten...

...or even...

...to make the XOR more obvious.

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.

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.

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.

The XOR happens in line 8. Instead of...

...that line could have been rewritten...

...or even...

...to make the XOR more obvious.

Leandro Coutinho

Ranch Hand

Posts: 423

posted 4 years ago

Yes, it does. Because bit won't reach 0, it stops when bit = 1.

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.

Yes, it does. Because bit won't reach 0, it stops when bit = 1.

Ryan McGuire

Ranch Hand

Posts: 1167

11

posted 4 years ago

Ohh... I see what you're saying.**In this particular chunk of code,** the "& 1" operations are unnecessary. I thought you meant that in general those two expressions work out the same. You are absolutely correct. Well played, sir.

Leandro Coutinho wrote:Yes, it does. Because bit won't reach 0, it stops when bit = 1.

Ohh... I see what you're saying.

Ryan McGuire

Ranch Hand

Posts: 1167

11

posted 4 years ago

Before anyone else notices it...

With bit0 = 1 and bit1 = either 0 or 1, the two possible values for B are 1 and 3.

Also, it doesn't say B=3 is the*only* value that produces 8 pairs; it says that no other value for B produces more than 8. It leaves the door open for other values for B to produce 8 [i,j] pairs.

- 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.

Before anyone else notices it...

With bit0 = 1 and bit1 = either 0 or 1, the two possible values for B are 1 and 3.

Also, it doesn't say B=3 is the

It is sorta covered in the JavaRanch Style Guide. |

- Post Reply Bookmark Topic Watch Topic
- New Topic

Boost this thread!