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

×

bitwise operation

i dont understand why 1 one is faster than 2 :-

1:-

for j in array:
 number+=(1<<(k-j))

2:-

for j in array:
 number+=(1<<(j))

link to the problem here

first solution link here

second solution link here

asked 16 Sep '17, 03:41

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%

@phantomhive the first difference is that the first one is compiled in PyPy and the other in Python. However even when both are compiled on PyPy or Python there is significant difference (> 3s) between the execution times. I tried a few variations to understand what's going on but sadly I don't.

If anyone else can figure it out, please do, this is very curious :D

(16 Sep '17, 13:46) meooow ♦6★
1

i think it about the input.. the input data must have more big number which when done this "number+=1«number" and when we or it larer takes much time as the number is too large but when we do this "1«(k-number)" where "k>=number" we make sure that we set bit from right not from left that results in a small number but it only works if we have more big numbers and less small numbers!

(16 Sep '17, 14:40) phantomhive4★
2

Yes that might be it. I tried to test this locally using Python, and for the worst case of T=10, N=K=2500, and each set={K}, the solutions took 9.39 and 11.7 seconds. But clearly if the test data had such a case neither solution would pass at all (assuming my system is at least as fast as the judge). So I reduced the difficulty of test cases and got something like 4.49 and 5.79 seconds which is close to the result on submission. So you're probably right.

(16 Sep '17, 17:27) meooow ♦6★
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:

×184

question asked: 16 Sep '17, 03:41

question was seen: 305 times

last updated: 29 Sep '17, 18:00