PiecewiseLinearFunction
SRM 586 · 2013-06-25 · by gojira_tc
SRM 586 · 2013-06-25 · by gojira_tc · Simple Math, Simple Search, Iteration
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.
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.
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