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

Автор shashank21j, 10 лет назад, По-английски

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

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

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

How was Problem 'XOR love' to be solved?

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

    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;
    }
    
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      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

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

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

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

        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).