How to solve this problem ? - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
3 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

papa-ka-para's blog

How to solve this problem ?

By papa-ka-para, history, 20 months ago, In English

In English

we are given 4 integers, where a <= b , c <= d.

We have to find Sum of Xor of all the pairs (i,j) such that ( a <= i <= b , && c <= j <= d )


int sum = 0;

for(int i=a ; i <= b; i++) {
    for(int j = c; j <= d ; j++) {
         sum += (i ^ j)
    }
}
return sum;

How to find this sum optimally ?

-18

papa-ka-para
20 months ago
1

Comments

Comments (1)

Write comment?

»

20 months ago, # |

← Rev. 3 →

Vote: I like it

+8

Vote: I do not like it

For each x calculate the effect of 2^x on the answer.

The problem then becomes 32 "at position i, calculate how many zeros are in a certain interval". After getting the number of 1's and 0's just multiply them together. Then add up all the answers and you're done.

Implementation code

def calc(x,y):    # count y-bit on [0,x]
    return (x+1)//(1<<(y+1))*(1<<y)+max(0,(x+1)%(1<<(y+1))-(1<<y))
def query(l,r,y): # count y-bit on [l,r]
    return calc(r,y)-calc(l-1,y)
a,b,c,d=map(int,input().split())
answer=0
for i in range(0,32):
    cnt1_ab,cnt1_cd=[query(a,b,i),query(c,d,i)]
    cnt0_ab,cnt0_cd=[b-a+1-cnt1_ab,d-c+1-cnt1_cd]
    xor_ans=cnt1_ab*cnt0_cd+cnt0_ab*cnt1_cd
    answer+=xor_ans*(1<<i)
print(answer)

→ Reply