shashank21j's blog

101 Hack June'14 — HackerRank
By shashank21j, 10 years ago, In English

Hello Coders!

The June edition of 101 Hack is here. 5 interesting challenges in 2 hours. The contest commences on 28th June 1:00 PM UTC. You can sign up for the contest here.

The problem statements will be available in English, Russian and Chinese.
Top 10 on leaderboard get cool HackerRank T Shirts

Problem Setters
darkshadows
amitp08
Bidhan

Problem Tester
Gerald
kevinsogo

GL&HF

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

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How was Problem 'XOR love' to be solved?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    First calculate d[i][j], 1 <= i <= 20, 1 <= j <= N — how many numbers from A[1] .. A[j] have i'th bit set.

    Now for each query (K, P, R) look at each 20 bits of K (20 because numbers do not exceed 10^6).

    Calculate the following:

    for (int i = 0; i < 20; ++i) {
	LL z1 = d[i][r] - d[i][p - 1]; //how many numbers from A[p] .. A[r] have i'th bit set
	LL z0 = r - p + 1 - z1; //how many numbers in A[p] .. A[r] have i'th bit not set
	if (k & (1 << i)) //if K has i'th bit set, only count pairs in A[p] .. A[r] where both bits are not set or both bits are set, multiply the count by 2^i
		answer = (answer + ((LL)1 << i) * (z0 * (z0 - 1) + z1 * (z1 - 1)) / 2) % MOD;
	else //else count pairs where one bit is set and one is not
		answer = (answer + ((LL)1 << i) * z0 * z1) % MOD;
}
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Can you explain why we are doing this?

      if k has i'th bit set, only count pairs (A[i], A[j]) where both bits are not set or both bits are set, multiply the count by 1 << i

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

        I will try after TopCoder SRM 626 ends if nobody has still explained it by that time ^.^

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well, multiplying by 2^i is obvious i guess, because we are calculating each bits occurance. And about bot set or bot nonset stuff, look at this equations:

        K^ai^aj = 1 so,

        If k=1 then thoose pairs are good

        (0,0) , (1,1) else (0,1).

        → Reply