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

×

How to solve Big number array problem?

Hey all,

I was trying this problem Big Number Array on Hackerearth. I tried simple brute force but only one test case passed.

I also looked at the editorial but they only published the code and not the explanation.

It will be very helpful if someone could explain the approach.

Thanks in advance!

asked 12 Apr, 11:05

solo_loser's gravatar image

4★solo_loser
5112
accept rate: 0%


Flipping the l-th bit to r-th bit in a number is same as XORing that number with a number having 1s only in positions from 'l' to 'r'. Let's denote the number whose first 'k' bits are 1s and the remaining are 0s as Xk . So, if you flip the bits from position 'l' to position 'r' in a number 'A', the resulting number will be equal to A XOR Xl-1 XOR Xr. But, since l,r are big, it is impossible to actually XOR with those numbers.

So, we will use some random numbers to take the place of each Xk. Suppose that we will assign each Xk a value that is uniformly randomly selected from the range [0,2h-1]. Each update will be a range XOR operation now. However, there is a problem with this approach, because there is a chance that two numbers might end up getting the same value (after XORing), even though the bits present in them are different. It is impossible to completely eliminate this, but we can decrease the probability of this happening, to a point where its almost negligible. This can be done by choosing a suitably large value for the range of random numbers.

If the numbers are uniformly randomly chosen from the range [0,2h-1], a sequence of XOR operations will give us a result in the same range as well. Irrespective of the length of the sequence, the probability of the result being equal to any number in the range [0,2h-1] is same (why?). In the worst case, all the 'N' numbers will be different, and we need to minimise the probability that the value we get after performing XOR operations on any two numbers out of them are equal. If you set h=64, and N=10^5, the probability of getting a random collision (two numbers with same value) will be less than 10-9 ( https://en.wikipedia.org/wiki/Birthday_attack ).

link

answered 13 Apr, 19:17

hemanth_1's gravatar image

6★hemanth_1
1.3k9
accept rate: 26%

edited 13 Apr, 19:26

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,595
×1,302
×126

question asked: 12 Apr, 11:05

question was seen: 139 times

last updated: 13 Apr, 19:26