How does Counting Inversions work in the following code? - Codeforces

→ Pay attention

Before contest
Codeforces Round 1006 (Div. 3)
3 days
Register now »

→ Top rated

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	157
6	Qingyu	156
7	djm03178	151
7	adamant	151
9	luogu_official	150
10	awoo	147

View all →

→ Find user

→ Recent actions

Detailed →

-synx-'s blog

How does Counting Inversions work in the following code?

By -synx-, history, 8 years ago, In English

In English

a = 0
while max(V) > 0:
    C = [ 0 ] * max(V)
    for x in V:
        if x%2==0:
            a += C[x//2]
        else:
            C[x//2] += 1
    V = [ x//2 for x in V ]
print(a)

+10

-synx-
8 years ago
2

Comments

Comments (1)

Show archived | Write comment?

»

8 years ago, # |

← Rev. 2 →

Vote: I like it

+12

Vote: I do not like it

Consider 2 numbers $\text{[math]}$ and $\text{[math]}$ . Write them down in binary (Assume both of them to be $\text{[math]}$ digit binary number (Incase their length is unequal , pad leading zeroes to the shorter one).

$\text{[math]}$
$\text{[math]}$

Let $\text{[math]}$ be the minimum index such that $\text{[math]}$

So $\text{[math]}$ is an inversion pair if and only if index of $\text{[math]}$ $\text{[math]}$ index of $\text{[math]}$ and $\text{[math]}$
So for any $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ and $\text{[math]}$ and after that they are both equal so each pair gets counted towards as an inversion exactly once.

→ Reply