Google is calling all BS, MS and PhD students expecting to graduate in 2016 and interested in a career at Google, it's time to register and start practicing for the Google APAC 2016 University Graduates Test!!
Don't wait, register now!!
- Registration Link : https://code.google.com/codejam/apactest
- Full Schedule : https://code.google.com/codejam/apactest/schedule.html
can someone who participated provide short editorials of problem B, C, D. here are the problems https://code.google.com/codejam/contest/8264486/dashboard#s=p3
For B, The solution is simple. You anyhow have to check by XORring four elements at a time, i.e. a[i] ^ a[j] ^ a[p] ^ a[q]. But, instead of brute force'ing at one single time, you can divide the brute force into two. i.e. first compute a[i] ^ a[j], i.e. run brute force once in ( O(n^2) ) save the results, again brute force ( in O(n^2) again ) for a[p] ^ a[q] now either you can brute force again through previous results or just simply look for k ^ ( a[p] ^ a[q] ) in the previous results if you've stored them in a Map.
The third sentence in the explanation part has shown the most important part of the full solution of D in round E.
Can anyone describe how to solve last problem for Large input ?
Here is a short explanation .. First calculate all sums ( sum[i]= number of subarrays with sum 'i' ) This can be done in O(n^2) Now for each query, go through all sums ( for sum=0 to 2*10^7) and calculate the answer. HINT: for each sum 'i' find how many of s[i]'s will lie between L and R . So the complexity is O(n^2 + (10^7)*Q) . This is just an easy solution (and runs in time . For me it ran in 2.39 mins) . Can anyone discuss a better solution ??!
I missed submitting the code by 1-2 minutes time. Instead of going sum = 0 to 2*10^7, you could apply binary search on this.. The resulting complexity is O(n^2 + log(S).N.Q) S = Sum of all N elements
In problem C I have seen many people using dp with state as ( N , j ) where N is the the machine and j is the jth bit of number I am not able to understand about the intution behind that , Can anybody please explain?