Well I’ve been trying this question on www.hackerrank.com for the past 3-4 days but am still not getting the perfect score.The problem is that in my code http://ideone.com/kfql6T when I used unsigned short as a chunk which is 16bit it works fine except for 3 test cases where it shows a TLE. So instead of short I used unsigned long long 64 bit.In this case only 2 test cases are right and on ideone I’m getting a SIGSEGV(http://ideone.com/lGkUmN)
The algorithm you are using will obviously give TLE because number of calculations performed by your program in the worst case is (N/16)*Q = (100000/16)*500000 = 3.125E9.
However your logic is very close to getting AC if just change the factor 16 to sqrt(N). That way, you can answer any query in O(sqrt(N)) time. So the no of calculations in the worst case would be sqrt(N)*Q = sqrt(100000)*500000 = 1.581E8.
Maybe it can be solved in O(Q log N) by using binary indexed tree or something but i am not very sure about that.
Here’s my implementation of the O(Q sqrt(N)) approach : Link. If you face any trouble understanding it, feel free to reply.
@jaskaran_1: for both of the submission @ideone, I am not able to see the test cases against which you are running your program. I have run it against the sample test cases and its working fine. Could you please give the test cases against it is failing/in parallel you can also use some debugger like gdb to trace the bug.
the first code link(in which unsigned short has been used) in the above doesn’t work for test case #1,#4,#5 on hackerrank for changing bits problem in the bit manipulation section.When I change this short to long long to make my submissions faster then it doesn’t give the right result on many test cases.you can have the test cases #1,#4,#5 using hackos on hackerrank.
here is the submission on hackerrank using short
Thanks for the reply though from next time share your code on github or ideone not a jpeg
sure, i’ll take care of that.
How are you calculating the sqrt(N) sized chunk?
I just noticed that I had removed the image from my dropbox. Anyway I am giving you an ideone link -> http://ideone.com/OGgWjR
As regards your question, calculating sqrt(N) chunk of C can be done by adding corresponding chunks of A and B.