Zonal Computing Olympiad 2015, 29 Nov 2014

We say that two integers x and y have a variation of at least K, if |x − y| ≥ K (the absolute value of their difference is at least K). Given a sequence of N integers a1,a2,...,aN and K, the total variation count is the number of pairs of elements in the sequence with variation at least K, i.e. it is the size of the set of pairs

{(i,j)|1≤i<j≤N and|ai−aj|≥K} 

For example if K = 1 and the sequence is 3,2,4 the answer is 3. If K = 1 and the sequence is 3, 1, 3 then the answer is 2.

Your task is to write a program that takes a sequence and the value K as input and computes the total variation count.

-----Input format-----
The first line contains two positive integers N and K, separated by a space.

This is followed by a line containing N integers separated by space giving the values
of the sequence.

-----Output format-----
A single integer in a single line giving the total variation count.

-----Test data-----
You may assume that all integers in the input are in the range 0 to 10^8 inclusive.

Subtask 1 (40 marks) : 1 ≤ N ≤ 4000, 1 ≤ K ≤ 10^8 
Subtask 2 (60 marks) : 1 ≤ N ≤ 65000, 1 ≤ K ≤ 10^8 

-----Sample Input-----
3 1 
3 1 3

-----Sample Output-----
2

Difficulty: interview

Starter code:

Solutions:
n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        if(abs(a[i]-a[j])>=k):
            ans+=1
print(ans)


n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
i=0
s=0
for j in range(0,n):
    while(i<n):
        if(a[i]-a[j]>=k):
            s=s+(n-i)
            break
        i=i+1
print(s)

import sys
n,k=list(map(int,input().strip().split()))
a=list(map(int,sys.stdin.readline().strip().split()))
s=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if abs(a[i]-a[j])>=k:
            s+=1
    
print(s)


n,k=list(map(int,input().strip().split()))
a=list(map(int,input().strip().split()))
s=0
for i in range(len(a)):
    for j in range(i+1,len(a)):
        if abs(a[i]-a[j])>=k:
            s+=1
    
print(s)


n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
i=0
fin=0
for j in range(0,n):
    while(i<n):
        if(l[i]-l[j]>=k):
            fin=fin+(n-i)
            break
        i=i+1
print(fin)

n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
l.sort()
i=0
fin=0
for j in range(n):
    while(i<n):
        if(l[i]-l[j]>=k):
            fin=fin+(n-i)
            break
        i=i+1
print(fin)

n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
count=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if(abs(l[i]-l[j])>=k):
            count=count+1
print(count)
        


# cook your dish here
N, K = map(int, input().split(" "))
inputs = list(map(int, input().split(" ")))
inputs.sort()
data = [[inputs[0], 1]]
total = 0
previous = [inputs[0], 0]
for n in range(1,N): 
    if inputs[n] == previous[0]: 
        total+=previous[1]
        data[0][1] += 1
    else: 
        flag = True
        for point in data:
            if inputs[n] - point[0] >= K: 
                total += point[1]
                previous = [inputs[n], point[1]]
                flag = False
                break
        data = [[inputs[n], data[0][1] + 1]] + data
        if flag:
            previous = [inputs[n], 0]
print(total)

# cook your dish here
N, K = map(int, input().split(" "))
inputs = list(map(int, input().split(" ")))
inputs.sort()
data = [[None, 0]]
total = 0
previous = [None, None]
for n in range(N): 
    if inputs[n] == previous[0]: 
        total+=previous[1]
        data[0][1] += 1
    else: 
        previous = [None, None]
        data = [[inputs[n], data[0][1] + 1]] + data
        for point in data[1:-1]:
            if inputs[n] - point[0] >= K: 
                total += point[1]
                previous = [inputs[n], point[1]]
                break
        if previous == [None, None]:
            previous = [inputs[n], 0]
print(total)

# cook your dish here
N, K = map(int, input().split(" "))
inputs = list(map(int, input().split(" ")))
inputs.sort()
total = 0
previous = [None, None]
for n in range(1, N): 
    if inputs[n] == previous[0]: 
        total+=previous[1]
        continue
    previous = [None, None]
    for i in range(n-1, -1, -1):
        tmp = inputs[n] - inputs[i]
        if tmp < 0: 
            tmp = -tmp
        if tmp >= K: 
            total += i+1 
            previous[1] = i+1
            previous[0] = inputs[n]
            break
    if previous[0] is None: 
        previous[0] = inputs[n]
        previous[1] = 0
print(total)

# cook your dish here
N, K = map(int, input().split(" "))
inputs = list(map(int, input().split(" ")))
inputs.sort()
total = 0
for n in range(N): 
    for i in range(n-1, -1, -1):
        tmp = inputs[n] - inputs[i]
        if tmp < 0: 
            tmp = -tmp
        if tmp >= K: 
            total += i+1 
            break
print(total)

# cook your dish here
N,K=map(int,input().split())
x=list(map(int,input().split()))[:N]
count=[]
for i in range(len(x)):
    for j in range(i,len(x)):
        if abs(x[i]-x[j])>=K:
            count.append(1)
print(len(count))

# cook your dish here
N,K=map(int,input().split())
x=list(map(int,input().split()))[:N]
count=[]
for i in range(len(x)):
    for j in range(i,len(x)):
        if abs(x[i]-x[j])>=K:
            count.append(1)
print(len(count))

n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr.sort()
i=0
res=0
for j in range(n):
    while(i<n):
        if(arr[i]-arr[j]>=k):
            res=res+(n-i)
            break
        i+=1
print(res)        
        


n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr.sort()
i=0
res=0
while(i<len(arr)):
    j=i+1
    while(j<len(arr)):
        if(arr[j]-arr[i]>=k):
            res=res+len(arr)-j
            break
        j+=1
    i+=1
print(res)        
        


n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr.sort()
i=0
res=0
while(i<len(arr)):
    j=i+1
    while(j<len(arr)):
        if(arr[j]-arr[i]>=k):
            res=res+1
        j+=1
    i+=1
print(res)        
        


n, k = list(map(int, input().split()))
arr = list(map(int, input().split()))
arr.sort()
count = 0

j = 0
for i in range(n) :
    while(j < n) :
        if arr[j] - arr[i] >= k :
            count += n-j
            break
        j += 1
            
print(count)# cook your dish here


nk=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr.sort()
count=0
for i in range(0,len(arr)):
    for j in range (i+1,len(arr)):
        x=arr[j]-arr[i]
        if x>=nk[1]:
            count=count+1
print(count)
3

nk=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr.sort()
count=0
for i in range(0,len(arr)):
    for j in range (i+1,len(arr)):
        x=arr[i]-arr[j]
        if x<0:
            x=x*(-1)
        if x>=nk[1]:
            count=count+1
print(count)
3

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
count = 0

j = 0
for i in range(n) :
    while(j < n) :
        if arr[j] - arr[i] >= k :
            count += n-j
            break
        j += 1
            
print(count)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
count = n*(n-1)//2

for i in range(n-1, -1, -1) :
    for j in range(i-1, -1, -1) :
        if arr[i] - arr[j] >= k :
            break
        else :
            count -= 1
            
print(count)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
arr.reverse()
count = n*(n-1)//2

for i in range(n) :
    for j in range(i+1, n) :
        if arr[i] - arr[j] >= k :
            break
        else :
            count -= 1
            
print(count)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
count = 0

for i in range(n) :
    for j in range(i+1, n) :
        if arr[i] - arr[j] <= -1*k :
            count += 1
            
print(count)

n, k = map(int, input().split())
arr = []

arr = list(map(int, input().split()))
count = 0

for i in arr :
    for j in arr :
        if i - j >= k :
            count += 1
            
print(count)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
count = 0

for i in arr :
    for j in arr :
        if i - j >= k :
            count += 1
            
print(count)