Get Time

   Problem Statement  

 Problem Statement for PiecewiseLinearFunction

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.


Method signature:int maximumSolutions(int[] Y)
(be sure your method is public)


-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.


{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.
{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.
{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:

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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 586 Round 1 - Division I, Level One