manishbisht's blog

By manishbisht, history, 8 years ago, In English

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

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The third sentence in the explanation part has shown the most important part of the full solution of D in round E.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone describe how to solve last problem for Large input ?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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?