The weighted graph
Practice
3.4 (9 votes)
Algorithms
Basics of greedy algorithms
C++
Greedy algorithms
Problem
82% Success 1683 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code
You are given a complete graph with \(n\) nodes. There are two values associated with each node \(i\), denoted by \(a_i\) and \(b_i\).
The weight of the edge between two nodes \(i\) and \(j\) is denoted by \(w_{ij} = |a_ib_j-a_jb_i|\).
Find the sum of the square of weights of all the edges. Formally, find the value \(\sum_\limits{i=1}^n\sum_\limits{j=i+1}^nw_{ij}^2\).
Input format
- The first line contains a single integer \(n\).
- The second line contains \(n\) space-separated integers \(a_1,a_2,...,a_n\).
- The third line contains \(n\) space-separated integers \(b_1,b_2,...,b_n\).
Output format
Print a single integer denoting the required value (mod \(10^9+7\)).
Constraints
\(2\le n\le 10^6\\-10^{15}\le a_i,b_i\le 10^{15} \)
Submissions
Please login to view your submissions
Similar Problems
Points:30
7 votes
Tags:
EasyGreedy Algorithms
Points:30
57 votes
Tags:
Basic ProgrammingBit ManipulationBit manipulationMathSorting
Points:30
5 votes
Tags:
AlgorithmsBasics of Greedy AlgorithmsGreedy Algorithms
Editorial