The Loop Problem-HackerEarth April Easy'21

help
1

Alice and Bob are playing a game to get rid of the boredom during this lockdown. The game consists of N rounds.

Alice challenges Bob in each round of the game by asking for the output of the following loop using the integers A,B,C and D.

sum = 0;
for(i=A;i<=B;i++) {
    for(j=C;j<=D;j++) {
        sum = sum + (i^j)
    }
}
print(sum)

Note: Here ^ stands for Bitwise XOR and other symbols have their usual meanings.

For Bob to win the game, he needs to answer Alice’s questions quickly.He needs your help to do this.

Input format

  • The first line contains an integer N denoting the number of rounds in the game.
  • The next N lines contain 4 space-separated integers denoting A,B,C and D.

Output format

Print N lines where each line contains the value of the sum. Since this value can be large, print it modulo 10^9+7.

Please help me with the problem!

2

I solved this problem. I think i have a good solution for this.

Here’s the idea to solve this problem the non-trivial way
We have 2 ranges basically [a…b] and [c…d]

now take range [a…b]
let c1 = number of numbers in range a…b that have x’th bit on
let c2 = number of numbers with x’th bit close in the range [a…b]

Similarly for range [c…d]
let c3 = number of numbers in range c…d that have x’th bit on
let c4 = number of numbers with x’th bit close in the range [c…d]

then you have total T = c1 x c4 + c2 x c3 number pairs which has x’th bit on after xor
In simple words you can fix your x’th bit and find c1, c2, c3, c4. then the contribution of x’th bit towards answer would be (c1 x c4 + c2 x c3) * (2 ^ (x-1)) cause u have total of T numbers with x’th bit on

Below is the given code. Hope it Helps
PS: f is the function that finds number of numbers with i’th bit on in range [0 … N)

Spoiler, Contains Code 
mod = 10**9 + 7
 
def f(n, pw):
    if n==0:
        return 0
    bl = n // (2*pw)
    rem = max(n % (2*pw) -pw, 0)
    return bl*pw + rem
 
def solve(a, b, c, d):
    ans = 0
    pw = 1
    while pw <= 10**9:
        c1 = f(b+1, pw) - f(a, pw)
        c2 = b+1-a - c1
        c3 = f(d+1, pw) - f(c, pw)
        c4 = d+1-c - c3
 
        v = (c1*c4 % mod + c2*c3 % mod) % mod
        v = v * pw % mod
        ans = (ans + v) % mod
 
        pw *= 2
    return ans 
 
for case in range(int(input())):
    li = map(int, input().split())
    print(solve(*li))
3

Hi, Thank you for the response. I have actually seen this solution almost everywhere and just can’t put a finger as to how to think like this intuitively? Because apart from Brute Force, I wasn’t able to think of any other solution until I saw the solution.

Also on another note- in this solution, I get how we calculated the total number of integers between the range a->b and c-> d by using b+1-a and d+1-c respectively

But could you explain how did we calculate c1 and c3, where the xth bit is on? I would highly appreciate that. Thank you once again.

4

Hey Man i didn’t came online as i already had done all problems. If U still haven’t got this i would tell you how the function f works. Also The idea to solve most of this range problems(atleast a trick of mine to always think in ranges of powers of 2). There are many such situations where i have seen that work. So I am looking for such patterns based on previous experience.

5

Check this