Velocities of balls | hackerearth solution

Rajnish Tripathi 21:52
Problem

There are � balls along a number line, each ball is represented by a point on the line. Ball � moves at velocity �� (��≠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,…��. Print, ∑�=1�⌊��⌋ for each ball.

It is guaranteed that whenever two balls �,� collide, the signs of their velocities will be different (��⋅��<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 ��ℎ being the sum of the floors of each time ball � collides with another ball.

Constraints

1≤�≤100

1≤�≤2000

|��|≤2000

0<|��|≤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 43. 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 ⌊43⌋=1. The second ball then hits the first ball at �=103 and then no balls ever collide again. Thus, the answer for the second ball is ⌊43⌋+⌊103⌋=4 and the answer for the second ball is simply ⌊103⌋=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) {
pq.add(new int[]{xvi[j][1]-xvi[i][1],xvi[i][2]-xvi[j][2],xvi[i][0],xvi[j][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<>();
for (int i:a) list.add(i);
Collections.sort(list);
for (int i=0; i<a.length; i++) a[i]=list.get(i);
}
static class Fast{
public BufferedReader br;
public StringTokenizer st;
public Fast(){
try{
br = ONLINE_JUDGE? (new BufferedReader(new FileReader("input.txt"))):(new BufferedReader(new InputStreamReader(System.in)));
}
catch(Exception e){
throw new RuntimeException(e);
}
}
String next(){
while(st==null || !st.hasMoreTokens()){
try{
st=new StringTokenizer(br.readLine());
}
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
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
}


Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags: