In this HackerRank Direct Connections problem, we need to find out how much cable they need to implement this telecommunication system, given the coordination of the cities and their respective population.
Problem solution in Python programming.
class fenpiece:
__slots__ = ['x','p','px','c']
def __init__(self,x=0,p=0,px=0,c=0):
self.x = x
self.p = p
self.px = px
self.c = c
def __iadd__(self,other):
self.x += other.x
self.p += other.p
self.px += other.px
self.c += other.c
return self
def __radd__(self,other):
return fenpiece(self.x,self.p,self.px,self.c)
def __sub__(self,other):
return fenpiece(self.x-other.x,self.p-other.p,self.px-other.px,self.c-other.c)
def fensum(seq,i):
sum = 0
while i:
sum += seq[i-1]
i -= i&-i
return sum
def fensumrange(seq,i,j):
return fensum(seq,j) - fensum(seq,i)
def fenadd(seq,i,v):
i += 1
bound = len(seq) + 1
while i < bound:
seq[i-1] += v
i += i&-i
pBound = 10001
magicmod = 1000000007
fenlist = [fenpiece() for i in range(pBound)]
T = int(input())
for t in range(T):
total = 0
N = int(input())
X = [int(s) for s in input().split()]
P = [int(s) for s in input().split()]
cities = sorted(zip(X,P))
cable = 0
for x,p in cities:
underP = fensum(fenlist,p)
overP = fensumrange(fenlist,p,pBound)
cable = (cable + p*(underP.c*x - underP.x) + overP.p*x - overP.px)%magicmod
fenadd(fenlist,p,fenpiece(x,p,x*p,1))
print(cable)
for f in fenlist:f.__init__()Problem solution in Java Programming.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
class Solution{
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
while (t-- > 0) {
int n = scan.nextInt();
ArrayList<City> coordinateList = new ArrayList<>(n);
ArrayList<City> populationList = new ArrayList<>(n);
for (int i = 0; i < n; i++)
coordinateList.add(new City(scan.nextInt()));
for (int i = 0; i < n; i++)
coordinateList.get(i).population = scan.nextInt();
// Sort according to their coordinates
coordinateList.sort((x, y) -> Integer.compare(x.coordinate, y.coordinate));
int sortedCoordinates[] = new int[n];
for (int i = 0; i < n; i++) {
populationList.add(new City(coordinateList.get(i), i));
sortedCoordinates[i] = coordinateList.get(i).coordinate;
}
// Sort according to their populations (max to min)
populationList.sort((x, y) -> Integer.compare(y.population, x.population));
int cityNumber[] = new int[n];
for (int i = 0; i < n; i++)
cityNumber[i] = 1;
BinaryIndexTree cityNumberTree = new BinaryIndexTree(cityNumber);
BinaryIndexTree cityCoordinateTree = new BinaryIndexTree(sortedCoordinates);
long totalCable = 0;
for (int i = 0; i < n; i++) {
City currentCity = populationList.get(i);
int index = currentCity.index;
int coordinate = currentCity.coordinate;
long leftCable = cityNumberTree.getSum(index - 1) * coordinate;
leftCable -= cityCoordinateTree.getSum(index - 1);
long rightcable = cityCoordinateTree.sumRange(index + 1, n - 1);
rightcable -= cityNumberTree.sumRange(index + 1, n - 1) * coordinate;
totalCable += (leftCable + rightcable) * currentCity.population;
totalCable %= 1000000007;
cityCoordinateTree.update(index, 0);
cityNumberTree.update(index, 0);
}
System.out.println(totalCable);
}
}
static class City {
int coordinate;
int population;
int index;
public City(int coordinate) {
this.coordinate = coordinate;
}
public City(City other, int index) {
this.coordinate = other.coordinate;
this.population = other.population;
this.index = index;
}
}
static class BinaryIndexTree {
int[] nums;
long[] BIT;
int n;
public BinaryIndexTree(int[] nums) {
this.nums = nums;
n = nums.length;
BIT = new long[n + 1];
for (int i = 0; i < n; i++)
init(i, nums[i]);
}
public void init(int i, int val) {
i++;
while (i <= n) {
BIT[i] += val;
i += (i & -i);
}
}
void update(int i, int val) {
int diff = val - nums[i];
nums[i] = val;
init(i, diff);
}
public long getSum(int i) {
long sum = 0;
i++;
while (i > 0) {
sum += BIT[i];
i -= (i & -i);
}
return sum;
}
public long sumRange(int i, int j) {
return getSum(j) - getSum(i - 1);
}
}
}Problem solution in C++ programming.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
pair<long long, int> aib[200001];
int n;
const long long MOD = 1000000007;
void update(long long crd, int poz) {
for (; poz <= n; poz += (poz ^ (poz - 1)) & poz) {
aib[poz].first += crd;
aib[poz].first %= MOD;
aib[poz].second++;
}
}
pair<long long, int> get(int poz) {
pair<long long, int> r = make_pair(0, 0);
for (; poz; poz -= (poz ^ (poz - 1)) & poz) {
r.first += aib[poz].first;
r.first %= MOD;
r.second += aib[poz].second;
}
return r;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int nr_tests;
cin >> nr_tests;
while (nr_tests--) {
cin >> n;
set<int> s;
vector<int> coord(n);
vector<pair<int, int> > pop(n);
for (int i = 0; i < n; i++) {
cin >> coord[i];
s.insert(coord[i]);
aib[i + 1].first = aib[i + 1].second = 0;
}
for (int i = 0; i < n; i++) {
cin >> pop[i].first;
pop[i].second = i;
}
sort(pop.begin(), pop.end());
int p = 0;
map<int, int> mp;
for (auto x : s) {
mp[x] = ++p;
}
long long sum = 0, rez = 0;
for (int i = 0; i < n; i++) {
long long crd = coord[pop[i].second];
pair<long long, int> cur = get(mp[crd]);
long long lower = (crd * cur.second) % MOD;
lower -= cur.first;
if (lower < 0) {
lower += MOD;
}
long long higher = sum - cur.first;
if (higher < 0) {
higher += MOD;
}
higher -= ((i - cur.second) * crd) % MOD;
if (higher < 0) {
higher += MOD;
}
long long curR = (lower + higher) % MOD;
update(crd, mp[crd]);
curR *= pop[i].first;
rez = (rez + curR) % MOD;
sum += crd;
sum %= MOD;
}
cout << rez << "\n";
}
return 0;
}Problem solution in C programming.
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long read(int idx,long long*tree);
void update(int idx ,int val,long long*tree,int MaxVal);
void sort_a(int*a,int*b,int*c,int size);
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int main()
{
int i,j,T,N;
int *x,*p,*x_sort,*p_sort,*index;
long long ans,temp,*n_tree,*d_tree;
x=(int*)malloc(200000*sizeof(int));
p=(int*)malloc(200000*sizeof(int));
x_sort=(int*)malloc(200000*sizeof(int));
p_sort=(int*)malloc(200000*sizeof(int));
index=(int*)malloc(200000*sizeof(int));
n_tree=(long long*)malloc(200001*sizeof(long long));
d_tree=(long long*)malloc(200001*sizeof(long long));
scanf("%d",&T);
for(i=0;i<T;i++){
ans=0;
scanf("%d",&N);
for(j=0;j<=N;j++)
n_tree[j]=d_tree[j]=0;
for(j=0;j<N;j++)
scanf("%d",x+j);
for(j=0;j<N;j++){
scanf("%d",p+j);
update(j+1,1,n_tree,N);
}
sort_a2(x,p,N);
for(j=0;j<N;j++){
x_sort[j]=x[j];
p_sort[j]=p[j];
index[j]=j;
update(j+1,x[j],d_tree,N);
}
sort_a(p_sort,x_sort,index,N);
for(j=N-1;j!=0;j--){
temp=x_sort[j]*read(index[j],n_tree)-read(index[j],d_tree);
while(temp<0)
temp+=MOD;
temp%=MOD;
ans+=p_sort[j]*temp;
ans%=MOD;
temp=(read(N,d_tree)-read(index[j]+1,d_tree))-x_sort[j]*(read(N,n_tree)-read(index[j]+1,n_tree));
while(temp<0)
temp+=MOD;
temp%=MOD;
ans+=p_sort[j]*temp;
ans%=MOD;
update(index[j]+1,-1,n_tree,N);
update(index[j]+1,-(x_sort[j]),d_tree,N);
}
printf("%lld\n",ans);
}
return 0;
}
long long read(int idx,long long*tree){
long long sum = 0;
while (idx > 0){
sum += tree[idx];
sum%=MOD;
idx -= (idx & -idx);
}
return sum;
}
void update(int idx ,int val,long long*tree,int MaxVal){
while (idx <= MaxVal){
tree[idx] += val;
tree[idx]%=MOD;
idx += (idx & -idx);
}
}
void sort_a(int*a,int*b,int*c,int size)
{
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a(left_a,left_b,left_c,m);
sort_a(right_a,right_b,right_c,size-m);
merge(a,left_a,right_a,b,left_b,right_b,c,left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int*c,int*left_c,int*right_c,int left_size, int right_size)
{
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void sort_a2(int*a,int*b,int size)
{
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size)
{
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}Problem solution in JavaScript programming.
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the solve function below.
function solve(ws, n, locations, populations) {
const cities = locations.map((loc, i) => ({ loc, pop: populations[i]}));
cities.sort((a, b) => b.pop - a.pop);
let ans = 0;
for (let i = 0; i < n - 1; ++i) {
let d = 0;
for (let j = i + 1; j < n; ++j) {
d += Math.abs(cities[i].loc - cities[j].loc);
}
d %= 1000000007;
ans = (ans + d * cities[i].pop) % 1000000007;
}
ws.write(ans + '\n');
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let i = 0; i < t; i++) {
const n = parseInt(readLine(), 10);
const locations = readLine().split(' ').map(s => parseInt(s, 10));
const populations = readLine().split(' ').map(s => parseInt(s, 10));
solve(ws, n, locations, populations);
}
ws.end();
}
0 Comments