I am trying to grasp the solution for the problem from december cook-off, I am banging my head from a long time but I didn’t get, how this nicely obfuscated java code is working.
Problem:- https://www.codechef.com/COOK65/problems/CHEFQUE
Solution:- https://www.codechef.com/viewsolution/8988285
Please any one can decode this code. I am not getting the way how the guy is indexing the array.
Thanks!!
@arpit728, this is similar to my code in c++. Here is a link to the solution. https://www.codechef.com/viewsolution/8989357 (for optimised code refer to https://www.codechef.com/viewsolution/8990011).
For the details of the indexing of array, let us first consider the genral discussion of marking large integers into array.
Try using bits to mark integers. It will decrease your memory by size of type of array. As in lets say we have an array of integer type
int mark[MAX/32];
where MAX is maximum integer we need to mark. Here we use know that int is 32 bits longs. So we use each bits of every number to store a value (here 1 means it is present and 0 means it is absent). This means mark[0] will represent 0 to 31 values, mark[2] will represent 64 to 95 values and and so… i.e. mark[i] will represent 32*(i-1) to (32*i)-1 vales.
So for given number n, he first do integer divide (n/32) to get which index of array should taken and to get which bit to check in that index, we take (n%32) which is clear from the above values which are given for nth index which is 32*(n-1) to (32*n)-1.
Suppose we get 18, what we will do is
mark[0] = (mark[0] | (1<<18)
it will make mark[0] something like 00000000000000100000000000000000, marking the 18th bit, so we can mark numbers like this. This actually means mark[0] is given the value 2^18 = 262144. As you see my first implementation, to find the sum I have checked which bits are set which is similar to conversion to binary and checking whether the bit is 1 or not. To check, a simple way can be
mark[(n)/32] = (mark[n/32] | (1<<(n%32))
this should work! (Reason n/32 gives the index and n%32 gives bit value, which for setting we require it as pow(2, n%32) which is same as 1<<(n%32)).
now how to check hash table, approach is similar, there should be one in that place…
if(mark[n/32]&(1<<(n%32)) then yes else no (here we use bitwise & operation and not && operation. a&b will give bitwise anding and we are interested in checking given bit, so 1<<(n%32) will set the number to pow(2,n%32) which is similar to only one bit equal to 1 and rest ones equal to 0, and bitwise anding will give 0 for other bits except for the desired bit for which the answer will be yes if bit was set in mark[n/32] else no).
using this your memory reduced by 32, you can reduce it by 64 also using long long(because long long uses 64 bits to store number)!
Now, adding and erasing operations. In my optimised code, you can see that first we check whether the object is already present using x[temp/32]&(1<<(temp%32)) which checks whether the corresponding bit is set of not. It return 1 if it is set else 0. So use x[temp/32]&(1<<(temp%32)) with !(not) in add operation and x[temp/32]&(1<<(temp%32)) in erase operation. Now using the properties of or and xor which are
a ‘|’ 1 = 1, a ‘|’ 0 = a, a ‘^’ 1 = !a(complement of a), a’^’ 0 = a, where ‘|’ represents or and ‘^’ represents xor).
so using x[temp/32] = (x[temp/32] | (1<<(temp%32))) sets the bits at desired position (mark it as 1) and x[temp/32] = (x[temp/32] ^ (1<<(temp%32))) flips the bit at desired position, which here will be equivalent to reseting it to 0 because this operation is performed only when the bit is set to 1 at this position (the if condition checks for this).
If you have any more doubts, you can ask in the comment section below.
Happy coding 
PS: If you like the answer, upvote it and if any changes are required, do mention in comment section below.
@arpit, it is similar to the way described above. In java >>> stands for unsigned shifting. Here as all the numbers are positive, >>> works better. So x[val>>>6] is similar to x[val/64] (here integer division) and the condition checks whether that bit is set or not. The equal to condition (==0) is included in the erase query because if x[val/64] is zero, this means all the bits are reset to 0. Here instead of performing or operation in add query, xor can also be performed because the code has already first checked for the bit set/reset at desired position.
@likecs
Dude, I understand that condition is checking whether the corresponding bit is set or not. But I didn’t get how that condition is working can you please decode that, it’ll be a great help.
this part: x[val>>>6]<<~val
First, one concept used, since the number are stored in int i.e. inside the memory, the numbers are signed binary representations. If the left most digit is 1, then the number is negative and if it is 0, then it is positive. Seceond, ~ is bitwise complement operations which inverts all the bits inside the binary representation of number. Now refer to this small code of mine at http://pastebin.com/t9LU7kEj
Run this code at your machine and u will see that 1<<~i, goes in a cyclic manner and it shifts the bit (31-i%32) times. Here actually operation are on long so it is (63-i%64) times. So [x>>>6], actually takes us to the desired index x[val/64] and the vale in this index is shifted desired number of times. The desired bit where checking needs to be done becomes the signed bit and >0 means it was set and <=0 means it was not set.
Also, the user uwi has used opposite representation of bits to store the value. In the process described by me i used 00000000000000100000000000000000 to represent 18 at mark[0], i.e. starting from the right-most position but uwi has used the opposite i.e. starting from the left. For example- 00000000000000000100000000000000 to represent value 18 at mark[0].
I hope it is clear now… If yes, mark the answer as correct and answered and do upvote it.
@likecs
hey,can you figure out what is wrong in this code, I am getting the wrong answer.
https://www.codechef.com/viewsolution/9001105
set[temp>>>6]|=(1<<(temp>>>6)) statement is wrong. We require 1<<(temp%32) which can’t be achieved using temp>>>6 operator. Refer above explanation for or and xor operation along with erase and add operation…
and it works in cyclic fashion then why do we need a modulus.
do not know the reason for this one. may be ~ works in cyclic manner but for ur code it does not. May be ask someone else.
@likecs
hey, please check this out I am not getting my mistake https://www.codechef.com/viewsolution/9002475
bothered you a lot, this is the last one.