Блог пользователя manishbisht

Автор manishbisht, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?