# Velocities of balls | hackerearth solution

Problem

There are $�$ balls along a number line, each ball is represented by a point on the line. Ball $�$ moves at velocity ${�}_{�}$ (${�}_{�}\ne 0$) along this number line and is initially at point ${�}_{�}$.

When two balls collide (occupy the same point along the number line), their velocities switch. For example, if ball $�$ with velocity $2$ collides with ball $�$ with velocity $-3$, ball $�$ will have velocity $-3$ and ball $�$ will have velocity $2$ after the collision.

Given each ball's initial distinct position and velocity, find for each ball $�$ the sum of the floor of the times that ball $�$ collides with another ball. Formally, ball $�$ collides with another ball $�$ times in total at times ${�}_{1},{�}_{2},\dots {�}_{�}$. Print, $\sum _{�=1}^{�}⌊{�}_{�}⌋$ for each ball.

It is guaranteed that whenever two balls $�,�$ collide, the signs of their velocities will be different (${�}_{�}\cdot {�}_{�}<0$).

Input format

• The first line of the input contains a single integer $�$ denoting the number of test cases.
• The first line of each test case contains a single integer $�$ denoting the number of balls.
• The second line of each test case contains $�$ integers ${�}_{�}$ denoting the initial position of ball $�$.
• The third line of each test case contains $�$ integers ${�}_{�}$ denoting the velocity of ball $�$.

Output format

Print $�$ integers denoting the ${�}^{�\mathrm{â„Ž}}$ being the sum of the floors of each time ball $�$ collides with another ball.

Constraints

$1\le �\le 100$

$1\le �\le 2000$

$|{�}_{�}|\le 2000$

$0<|{�}_{�}|\le 2000$

• It is guaranteed that, in the given input, whenever two balls collide the signs of their velocities will be different.

• It is guaranteed that the sum of $�$ over all test cases is less than or equal to $2000$.

• No two pairs of balls collide at the same place at the same time.

Sample Input
4
2
0 2
-1 1
2
0 2
1 -1
3
-5 1 5
1 1 -2
5
8 4 0 -3 2
-3 2 1 1 -4

Sample Output
0
0
1
1
3
4
1
0
2
3
1
4

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, the balls never collide so the total sum of times will be $0$.

In the second test case, the ball collides exactly ones at $�=1$, so the sum of the floor of times for each ball will be $1$.

In the third test case, the first collision happens between the 2nd and 3rd balls at time $\frac{4}{3}$. When they collide, the second ball and third ball switch velocities so the second ball is now traveling at velocity $-2$ and the third ball is now traveling at velocity $1$. The third ball never hits anything else so it's final value is $⌊\frac{4}{3}⌋=1$. The second ball then hits the first ball at $�=\frac{10}{3}$ and then no balls ever collide again. Thus, the answer for the second ball is $⌊\frac{4}{3}⌋+⌊\frac{10}{3}⌋=4$ and the answer for the second ball is simply $⌊\frac{10}{3}⌋=3$

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 14;
ll x[N], v[N], id[N], ans[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
iota(id, id + n, 0);
for (int i = 0; i < n; ++i)
cin >> x[i];
for (int i = 0; i < n; ++i)
cin >> v[i];
vector<pair<int, int>> con;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (x[i] < x[j] && v[i] > 0 && v[j] < 0)
con.emplace_back(i, j);
sort(con.begin(), con.end(), [](pair<int, int> a, pair<int, int> b) {
return (x[a.second] - x[a.first]) * (v[b.first] - v[b.second]) <
(x[b.second] - x[b.first]) * (v[a.first] - v[a.second]);
});
fill(ans, ans + n, 0);
for (auto[i, j] : con) {
int t = (x[j] - x[i]) / (v[i] - v[j]);
ans[id[i]] += t;
ans[id[j]] += t;
swap(id[i], id[j]);
}
for (int i = 0; i < n; ++i)
cout << ans[i] << '\n';
}
}

Code(JAVA):-

import java.io.*;
import java.util.*;
import java.math.*;
public class Main{
static boolean ONLINE_JUDGE = false;//change before submit
static Fast f = new Fast();
static PrintWriter out = new PrintWriter(System.out);
static boolean TEST_CASES = true;
static void solve() {
int n = ri();
int[] x = ra(n);
int[] v = ra(n);
int[][] xvi = new int[n][3];
for(int i = 0; i < n; i++) {
xvi[i][0] = i;
xvi[i][1] = x[i];
xvi[i][2] = v[i];
}
Arrays.sort(xvi,(a,b)->{
return a[1]-b[1];
});
int[] ans = new int[n];
int[] map = new int[n];
for(int i = 0; i < n; i++) map[i] = i;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
return Double.compare(1.0*a[0]/a[1],1.0*b[0]/b[1]);
});
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(xvi[i][2]-xvi[j][2]>0 && xvi[i][2]*xvi[j][2]<0) {
}
}
}
while(!pq.isEmpty()) {
int[] cur = pq.poll();
int val = cur[0]/cur[1];
ans[map[cur[2]]] += val;
ans[map[cur[3]]] += val;
int temp = map[cur[2]];
map[cur[2]] = map[cur[3]];
map[cur[3]] = temp;
}
for(int i = 0; i < n; i++) out.println(ans[i]);
/* WARNING : change [ONLINE_JUDGE = false] before SUBMIT */
}
public static void main(String[] args)throws Exception{
out = ONLINE_JUDGE? new PrintWriter(new BufferedWriter(new FileWriter("output.txt"))):new PrintWriter(System.out);
if(TEST_CASES){
int t = f.nextInt();
while(t-->0){
solve();
}
}
else {
solve();
}
out.close();
}
static int ri() {
return f.nextInt();
}
static long rl() {
return f.nextLong();
}
static String rs(){
return f.next();
}
static String rS(){
return f.nextLine();
}
static char rc(){
return f.next().charAt(0);
}
static int[] ra(int n) {
int[] a = new int[n];
for(int i = 0;i<n;i++) a[i] = ri();
return a;
}
static char[] rac(){
char[] c = rs().toCharArray();
return c;
}
static int[][] rm(int n, int m){
int[][] mat = new int[n][m];
for(int i = 0; i < n; i++) mat[i] = ra(m);
return mat;
}
static char[][] rmc(int n){
char[][] cmat = new char[n][];
for(int i = 0; i < n;) cmat[i] = rac();
return cmat;
}
static void sort(int[] a) {
ArrayList<Integer> list=new ArrayList<>();
Collections.sort(list);
for (int i=0; i<a.length; i++) a[i]=list.get(i);
}
static class Fast{
public StringTokenizer st;
public Fast(){
try{
}
catch(Exception e){
throw new RuntimeException(e);
}
}
String next(){
while(st==null || !st.hasMoreTokens()){
try{
}
catch(IOException e){
throw new RuntimeException(e);
}
}
return st.nextToken();
}
int nextInt(){
return Integer.parseInt(next());
}
long nextLong(){
return Long.parseLong(next());
}
double nextDouble(){
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
}

### Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-