Connection Status:
Competition Arena > PiecewiseLinearFunction

PiecewiseLinearFunction

SRM 586 · 2013-06-25 · by gojira_tc

SRM 586 · 2013-06-25 · by gojira_tc · Simple Math, Simple Search, Iteration
Class Name: PiecewiseLinearFunction
Return Type: int
Method Name: maximumSolutions
Arg Types: (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}.



Given a real number y, we can count the number of solutions to the equation F(x)=y. For example, for the function plotted above there are 0 solutions for y=7, there is 1 solution for y=4, and there are 3 solutions for y=1.1. We are looking for the largest number of solutions such an equation can have. For the function plotted above the answer would be 3: there is no y such that F(x)=y has more than 3 solutions.

If there is an y such that the equation F(x)=y has infinitely many solutions, return -1. Otherwise, return the maximum possible number of solutions such an equation may have.

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{3, 2}
Returns: 1

The graph of this function is a line segment between (1, 3) and (2, 2). For any y such that 2 ≤ y ≤ 3 the equation F(x)=y has 1 solution, and for any other y it has 0 solutions.

1)
{4, 4}
Returns: -1

The function's plot is a horizontal line segment between points (1, 4) and (2, 4). For y=4, F(x)=y has infinitely many solutions.

2)
{1, 4, -1, 2}
Returns: 3

This is the example from the problem statement. Three solutions are obtained for any value of y between 1 and 2, inclusive:

3)
{2, 1, 2, 1, 3, 2, 3, 2}
Returns: 5
4)
{125612666, -991004227, 0, 6, 88023, -1000000000, 1000000000, -1000000000, 1000000000}
Returns: 6

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

Coding Area

Language: C++17 · define a public class PiecewiseLinearFunction with a public method int maximumSolutions(vector<int> Y) · 165 test cases · 2 s / 256 MB per case

Submitting as anonymous