In this HackerEarth The weighted graph problem solution You are given a complete graph with n nodes. There are two values associated with each node i, denoted by ai and bi.

The weight of the edge between two nodes i and j is denoted by wij = |aibj - ajbj|.

Find the sum of the square of weights of all the edges. Formally, find the value Sigma(i=1,n) Sigma(j=i+1,n) (wij)^2.

HackerEarth The weighted graph problem solution


HackerEarth The weighted graph problem solution.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define mod 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define int long long
#define endl '\n'
#define pll pair<long long,long long>
#define LONGLONG_MAX 100000000000000
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long power(long long a,long long b){
long long ans=1;
while(b>0){
if(b&1){ans=(ans*a)%mod;}
a=(a*a)%mod;
b>>=1;
}
return ans;

}

int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
srand(time(0));
int t=1;
//cin>>t;
while(t--){
int n;
cin>>n;
assert(n>=2&&n<=1000000);
int a[n];
int b[n];
int x=0,y=0,ans=0,x1=0,y1=0;
for(int i=0;i<n;i++){
cin>>a[i];
assert(a[i]>=-1000000000000000ll&&a[i]<=1000000000000000ll);
a[i]%=mod;
x+=(a[i]*a[i])%mod;
x%=mod;
}
for(int i=0;i<n;i++){
cin>>b[i];
assert(b[i]>=-1000000000000000ll&&b[i]<=1000000000000000ll);
b[i]%=mod;
y+=(b[i]*b[i])%mod;
y%=mod;
y1+=(b[i]*a[i])%mod;
y1%=mod;
}
ans+=(x*y)%mod;
ans%=mod;
ans-=(y1*y1)%mod;
ans+=mod;
ans%=mod;
cout<<ans;
}
return 0;
}

Second solution

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192


class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()

def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")


input = lambda: sys.stdin.readline().rstrip("\r\n")

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print((sum(x ** 2 for x in a) * sum(x ** 2 for x in b) - sum(x * y for x, y in zip(a, b)) ** 2) % 1000000007)
# print(sum((a[i] * b[j] - a[j] * b[i]) ** 2 for i in range(n) for j in range(i + 1, n)) % 1000000007)