• 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

TopCoder XorSequenceEasy problem

 
Ranch Hand
Posts: 423
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!!
 
Ranch Hand
Posts: 1167
11
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Leandro Coutinho
Ranch Hand
Posts: 423
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks a lot Ryan!

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.


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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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



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.
 
Ryan McGuire
Ranch Hand
Posts: 1167
11
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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 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.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!