HackerEarth The weighted graph problem solution

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.

Topics we are covering

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("rn")

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)

coding problems solutions