Header Ads Widget

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  (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

1100

12000

||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:-