Connection Status:
Competition Arena > PiecewiseLinearFunctionDiv2

PiecewiseLinearFunctionDiv2

SRM 586 · 2013-06-25 · by gojira_tc

SRM 586 · 2013-06-25 · by gojira_tc · Simple Math, Simple Search, Iteration
Class Name: PiecewiseLinearFunctionDiv2
Return Type: int[]
Method Name: countSolutions
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

F is a function that is defined on all real numbers from the closed interval [1,N]. You are given a int[] Y with N elements. For each i (1 <= i <= N) we have F(i) = Y[i-1]. Additionally, you know that F is piecewise linear: for each i, on the interval [i,i+1] F is a linear function. The function F is uniquely determined by this information. For example, if F(4)=1 and F(5)=6 then we must have F(4.7)=4.5.

As another example, this is the plot of the function F for Y = {1, 4, -1, 2}.



You are also given a int[] query. For each i, compute the number of solutions to the equation F(x) = query[i]. Note that sometimes this number of solutions can be infinite.

Return a int[] of the same length as query. For each i, element i of the return value should be -1 if the equation F(x) = query[i] has an infinite number of solutions. Otherwise, element i of the return value should be the actual number of solutions this equation has.

Constraints

  • Y will contain between 2 and 50 elements, inclusive.
  • Each element of Y will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • query will contain between 1 and 50 elements, inclusive.
  • Each element of query will be between -1,000,000,000 and 1,000,000,000, inclusive.
Examples
0)
{1, 4, -1, 2}
{-2, -1, 0, 1}
Returns: {0, 1, 2, 3 }

This is the example from the problem statement. The detailed information about the queries is: There is no such x that F(x) = -2 is satisfied. F(x) = -1 is only true for x = 3. F(x) = 0 has two roots: 2.8 and 10/3. F(x) = 1 has three roots: 1, 2.6 and 11/3.

1)
{0, 0}
{-1, 0, 1}
Returns: {0, -1, 0 }

This function's plot is a horizontal segment between points (1, 0) and (2, 0). F(x) = 0 is satisfied for any x between 1 and 2 and thus the number of solutions is infinite. For any other value on the right-hand side, it has no solutions.

2)
{2, 4, 8, 0, 3, -6, 10}
{0, 1, 2, 3, 4, 0, 65536}
Returns: {3, 4, 5, 4, 3, 3, 0 }
3)
{5,4,-5,-5,4}
{3,4,5,-6,-5,-4,6}
Returns: {2, 2, 1, 0, -1, 2, 0 }
4)
{-999999999,1000000000,-1000000000,1000000000,-999999999}
{-999999999,-1000000000,1000000000,999999999,0}
Returns: {4, 1, 2, 4, 4 }

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

Coding Area

Language: C++17 · define a public class PiecewiseLinearFunctionDiv2 with a public method vector<int> countSolutions(vector<int> Y, vector<int> query) · 85 test cases · 2 s / 256 MB per case

Submitting as anonymous