You are not logged in. Please login at www.codechef.com to post your questions!

×

working of code for chef and queries???

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

asked 21 Dec '15, 16:17

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%


@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 (32i)-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 (32n)-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.

link

answered 21 Dec '15, 17:53

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 21 Dec '15, 22:14

@likecs Hey, can you please add a bit more on indexing part, I didn't get it.

(21 Dec '15, 19:29) arpit7281★

@likecs What does this if condition mean. if(x[val>>>6]<<~val>=0)

(22 Dec '15, 08:20) arpit7281★
3

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

(22 Dec '15, 12:52) likecs6★

@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

(22 Dec '15, 14:07) arpit7281★
2

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

(22 Dec '15, 18:09) likecs6★
1

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.

(22 Dec '15, 18:13) likecs6★
1

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

(22 Dec '15, 18:16) likecs6★
1

I hope it is clear now.. If yes, mark the answer as correct and answered and do upvote it.

(22 Dec '15, 18:16) likecs6★

@likecs hey,can you figure out what is wrong in this code, I am getting the wrong answer. https://www.codechef.com/viewsolution/9001105

(23 Dec '15, 01:06) arpit7281★
1

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

(23 Dec '15, 01:57) likecs6★

@likecs check this one, I sent that by mistake https://www.codechef.com/viewsolution/9002475

(23 Dec '15, 02:16) arpit7281★

and it works in cyclic fashion then why do we need a modulus.

(23 Dec '15, 02:16) arpit7281★
1

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.

(23 Dec '15, 12:45) likecs6★

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

(23 Dec '15, 18:08) arpit7281★
showing 5 of 14 show all

@likecs good explanation :)

link

answered 23 Dec '15, 16:06

deep1996's gravatar image

5★deep1996
661
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,657
×1,302
×847
×344
×342
×221
×68
×13

question asked: 21 Dec '15, 16:17

question was seen: 2,260 times

last updated: 25 Feb '16, 16:16