Velocities of balls

★★★★★

2.4

20 votes

, Algorithms, Linear Search, Simulation

Details

Submissions

Discussion

Editorial

Problem

There are $n$ balls along a number line, each ball is represented by a point on the line. Ball $i$ moves at velocity $v_i$ ( $v_i \neq 0$ ) along this number line and is initially at point $x_i$ .

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

Given each ball's initial distinct position and velocity, find for each ball $i$ the sum of the floor of the times that ball $i$ collides with another ball. Formally, ball $i$ collides with another ball $k$ times in total at times $t_1, t_2, \ldots t_k$ . Print, $\sum_{i=1}^k \lfloor t_i \rfloor$ for each ball.

It is guaranteed that whenever two balls $i, j$ collide, the signs of their velocities will be different ( $v_i \cdot v_j < 0$ ).

Input format

The first line of the input contains a single integer $t$ denoting the number of test cases.
The first line of each test case contains a single integer $n$ denoting the number of balls.
The second line of each test case contains $n$ integers $x_i$ denoting the initial position of ball $i$ .
The third line of each test case contains $n$ integers $v_i$ denoting the velocity of ball $i$ .

Output format

Print $n$ integers denoting the being the sum of the floors of each time ball $i$ collides with another ball.

Constraints

$1 \leq t \leq 100$

$1\leq n \leq 2000$

$|x_i| \leq 2000$

$0 < |v_i| \leq 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 $n$ 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

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 $t = 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 $\lfloor \frac{4}{3} \rfloor = 1$ . The second ball then hits the first ball at $t = \frac{10}{3}$ and then no balls ever collide again. Thus, the answer for the second ball is $\lfloor \frac{4}{3} \rfloor + \lfloor \frac{10}{3} \rfloor = 4$ and the answer for the second ball is simply $\lfloor \frac{10}{3} \rfloor = 3$ .

Contributers:

Allen Zhang

Arpa PoorAkhavan