You may know this from diferent sources, these are my case: - You implemented an adder either for electronics or for long integers, and remember that there are two parts one that does the result and one the carry out, and remember that the result is XOR of the two operands. - You may have worked with graphic effects and used to invert the colors in a given region, and of course you remember that that is done with XOR. - You try it out a lot until you finally discovered it because you needed it for this contest.
Look at this truth table (read carefully): A B C 0 0 0 0 1 1 1 0 1 1 1 0 If (A != B) C = 1 else C = 0 Only when A and B are different, C is 1.** If (A == 0) C = B else C = NOT B C is equal to B where A is 0. C is equal to NOT B where A is 1. If (B == 0) C = A else C = NOT A C is equal to A where B is 0. C is equal to NOT A where B is 1. C = A XOR B **: Yes XOR is the negative of equality (also known as XNOR, EQV, equivalent, double implication, biconditional, if and only if...) You notice we did copy A to the result where B has a 0 and copied NOT A where B has a 1. So XOR can be used for inversions, when you whan to get the negative of some bits and not others. Also if you repeat the operation you get back to the original: C B A 0 0 0 1 1 0 1 0 1 0 0 1 A = B XOR C So you can use XOR to change some bits and others not. If you change each bit an even number of times it will be equal to the original (for example the original is 0, then after inverting with XOR each bit an even number of times you are back to 0). So if you are doing a series of XOR that changes each bit a even number of times (note: don't forgive that 0 is even too) then they cancel out. Now if you take the set of XOR operations and separate them in two sets, you will notice that the results of the XORs those sets are equal because they will cancel out when you do XOR of them. So if the result is not 0, it will mean that there are bits that are inverted an odd number of times, meaning that you will not be able to split the set in two and get the same value of both sides. 2011/5/10 Marcelo Ramires <[email protected]>: > Right, I didn't ask how does one figure out that it's about XOR, because > this I've figured out too when I was solving, what I didn't know and > surprised me that everybody else knew is: > > If the xor of all numbers is zero, you can pick any candy, and the xor to > this number is going to be equal to the xor from the rest of them. > > I did't know this property of XOR, must be because I've never worked with > XOR in integers, but I'd say that if I had only used it a little I wouldn't > catch it quickly... > > On Mon, May 9, 2011 at 6:01 PM, Reniery O'Hara <[email protected]> wrote: >> >> Hi, >> One could come to this solution by understanding the Sean adding skills, >> >> 1100 >> + 0101 >> ------ >> 1001 >> >> compare this with the XOR truth table and you will have a match. >> As others posted before practice will help us to see these patterns while >> reading the problems. >> >> (Personally I didn't use an explicit integer XOR, I used mod 2) >> >> >> On Mon, May 9, 2011 at 4:59 PM, rahul raghavendra <[email protected]> >> wrote: >>> >>> u can do a lot of stuff with the bitwise operators , u just gotta >>> experiment with it >>> >>> On Tue, May 10, 2011 at 2:21 AM, Morgan Bauer <[email protected]> >>> wrote: >>>> >>>> XOR is the bread and butter of Symmetric Cryptography. >>>> ~mhb >>>> >>>> On Mon, May 9, 2011 at 4:44 PM, Marcelo Ramires >>>> <[email protected]> wrote: >>>> > I understood how to solve this, but how does one come to this solution >>>> > ? >>>> > >>>> > If the xor of all numbers is zero, you can pick any candy, and the xor >>>> > to >>>> > this number is going to be equal to the xor from the rest of them. >>>> > >>>> > I get this, if I have 9 numbers with XOR 3, XORing it with 3 will get >>>> > me >>>> > zero. >>>> > >>>> > How has everybody thought of this at the same time ? have I skipped a >>>> > logics >>>> > class ? is this concept so disseminated among coders ? >>>> > >>>> > I had never XORed nubmers before this code jam, only booleans, and I >>>> > didn't >>>> > know you could. >>>> > >>>> > As a side questions, can anybody tell me any alternative uses for >>>> > XORing >>>> > integers other than 1 and 0 ? >>>> > >>>> > Thanks! >>>> > >>>> > Marcelo Ramires >>>> > >>>> > On Sun, May 8, 2011 at 1:50 AM, vivek dhiman <[email protected]> >>>> > wrote: >>>> >> >>>> >> Lucky! >>>> >> >>>> >> You are right. >>>> >> >>>> >> if xor of two lists is same. (say xor1 = xo2) >>>> >> >>>> >> So the exor of these two wil be 0 (xor (xor1,xor2) = 0) >>>> >> Or in other words lists can be divided if the xor of all the elements >>>> >> is >>>> >> zero. >>>> >> >>>> >> :) >>>> >> >>>> >> >>>> >> >>>> >> On Sun, May 8, 2011 at 8:17 AM, keshav agarwal <[email protected]> >>>> >> wrote: >>>> >>> >>>> >>> please tell me of my logic was correct or i just got lucky to get it >>>> >>> correct >>>> >>> >>>> >>> if xor to a list of nos. is zero only then the division is possible >>>> >>> in this case patrick can be given the one candy with lowest value >>>> >>> while >>>> >>> sean keeps the rest >>>> >>> >>>> >>> if xor(n nos.)=0 >>>> >>> then (nth no.) xor (xor of n-1 nos.)=0 >>>> >>> >>>> >>> so patrick gets the nth candy and sean keeps the rest >>>> >>> >>>> >>> -- >>>> >>> You received this message because you are subscribed to the Google >>>> >>> Groups >>>> >>> "google-codejam" group. >>>> >>> To post to this group, send email to [email protected]. >>>> >>> To unsubscribe from this group, send email to >>>> >>> [email protected]. >>>> >>> For more options, visit this group at >>>> >>> http://groups.google.com/group/google-code?hl=en. >>>> >> >>>> >> >>>> >> >>>> >> -- >>>> >> Regards >>>> >> Vivek Dhiman >>>> >> >>>> >> -- >>>> >> You received this message because you are subscribed to the Google >>>> >> Groups >>>> >> "google-codejam" group. >>>> >> To post to this group, send email to [email protected]. >>>> >> To unsubscribe from this group, send email to >>>> >> [email protected]. >>>> >> For more options, visit this group at >>>> >> http://groups.google.com/group/google-code?hl=en. >>>> > >>>> > -- >>>> > You received this message because you are subscribed to the Google >>>> > Groups >>>> > "google-codejam" group. >>>> > To post to this group, send email to [email protected]. >>>> > To unsubscribe from this group, send email to >>>> > [email protected]. >>>> > For more options, visit this group at >>>> > http://groups.google.com/group/google-code?hl=en. >>>> > >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "google-codejam" group. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/google-code?hl=en. >>>> >>> >>> >>> >>> -- >>> K.Rahul ) >>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "google-codejam" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/google-code?hl=en. >> >> >> >> -- >> Reniery >> >> -- >> You received this message because you are subscribed to the Google Groups >> "google-codejam" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
