Connection Status:
Competition Arena > OneDimensionalBalls

OneDimensionalBalls

SRM 496 · 2010-11-01 · by gojira_tc

SRM 496 · 2010-11-01 · by gojira_tc · Graph Theory, Simple Math, Simple Search, Iteration
Class Name: OneDimensionalBalls
Return Type: long
Method Name: countValidGuesses
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

There is an infinite axis with N balls on it. The balls are moving with equal positive velocity, some of them in the positive direction of the axis and some in the opposite. The balls are small enough to be treated as points on the axis. If two balls meet at a point, they do not collide, and instead, they each continue moving in the same direction and at the same speed as before.

Manao is shown a picture of the axis taken at some moment of time. All the balls are at different points in the picture. The balls are numbered from 0 to N-1 and the i-th ball is at point firstPicture[i].

Some time after the first picture is taken, several balls are added to the axis and another picture is taken. Yet again, no two balls share a point in this picture. The balls seem indistinguishable and their coordinates are given in int[] secondPicture in ascending order.

For each ball in the second picture, Manao has to guess whether it is present on the first one as well, and if so, say its number. Sometimes, this can't be determined unambiguously, so any valid guess is welcome. A guess is valid if the balls could move in the way described above and appear in the named locations in the second picture. Two guesses are different if there is a ball in the second picture which Manao identifies differently in these guesses. Return the number of valid guesses for the given pictures.

Constraints

  • firstPicture will contain N elements, where N is between 1 and 50, inclusive.
  • Each element of firstPicture will be between 0 and 100,000,000, inclusive.
  • Elements in firstPicture will be distinct.
  • secondPicture will contain between N and 50 elements, inclusive.
  • Each element of secondPicture will be between 0 and 100,000,000, inclusive.
  • Elements in secondPicture will be in strictly ascending order.
Examples
0)
{12,11}
{10,11,13}
Returns: 3

There are 2 balls in the first picture at points 12 and 11, respectively. One more ball is added in the second picture. The following three guesses are valid: 1) The ball at point 10 is ball 0, the ball at point 11 is the new one, the ball at point 13 is ball 1. 2) The ball at point 10 is ball 1, the ball at point 11 is ball 0, the ball at point 13 is the new one. 3) The ball at point 10 is ball 1, the ball at point 11 is the new one, the ball at point 13 is ball 0.

1)
{1,2,3}
{1,2,3}
Returns: 0

Each picture contains the same number of balls, so they must contain the same set of balls. However, given that some time has passed between the shots, and the balls move with equal positive velocity, there is no way for them to have interchanged positions.

2)
{9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}
Returns: 161140441
3)
{1,3}
{1,3}
Returns: 1

If the balls move in opposite directions, they will interchange their positions at some moment.

4)
{1,2,3}
{0,1,3,4,5,6}
Returns: 8
5)
{7234}
{6316,689156,689160,689161,800000,1000001}
Returns: 6

Ball 0 could be any of the balls in the second picture.

Submissions are judged against all 184 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OneDimensionalBalls with a public method long long countValidGuesses(vector<int> firstPicture, vector<int> secondPicture) · 184 test cases · 2 s / 256 MB per case

Submitting as anonymous