Problem Statement
Recently, I realized that a rating graph can have two different intervals that look quite similar. Write a program that would detect such intervals.
You're given a user's rating graph in two int[]s: <tt>date</tt> and <tt>rating</tt>. Suppose that a user has participated in <tt>N</tt> contests; for <tt>0 <= i < N</tt>, the <tt>i</tt>-th contest has timestamp <tt>date[i]</tt> and the user's rating after this contest was <tt>rating[i]</tt>.
Formally, the rating graph is a sequence of points <tt>(date[i],rating[i])</tt>; an interval of the rating graph is a contiguous subsequence of those points - i.e., a subsequence corresponding to a contiguous range of indices. Two intervals are similar if one can be obtained from the other only by translation and scaling by a positive real factor (zooming). Note that both dimensions must be scaled by the same factor.
Consider the polyline obtained by visiting the points of an interval of the rating graph in order. The total length of this polyline is called the length of that interval.
Find the longest interval <tt>I</tt> of the given rating graph that's similar to some other (possibly partially overlapping) interval of that same rating graph and return the length of <tt>I</tt>.
Definition
Class:SimilarRatingGraphMethod:maxLength
Parameters:int[], int[]
Returns:double
Method signature:double maxLength(int[] date, int[] rating)
(be sure your method is public)
Constraints
- <tt>date </tt> and <tt>rating </tt> will contain the same number of elements.
- <tt>date </tt> will contain between <tt>2</tt> and <tt>400</tt> elements, inclusive.
- Each element of <tt>date </tt> will be between <tt>1</tt> and <tt>1,000,000</tt>, inclusive.
- The elements of <tt>date </tt> will be in strictly increasing order.
- Each element of <tt>rating </tt> will be between <tt>1</tt> and <tt>5,000</tt>, inclusive.
Examples
0)
{1,2,4,8,16,32}
{1,2,4,8,16,32}
Returns: 42.42640687119285The longest interval that's similar to another interval has length <tt>30*sqrt(2)</tt> and is formed by points (2,2), (4,4), ..., (32,32). It's similar to the interval formed by points (1,1), (2,2), ..., (16,16).
1)
{81,104,120,124,134,137}
{1866,2332,2510,2678,2876,3002}
Returns: 168.04761230080004
2)
{10,11,13,15,19}
{10,14,15,23,25}
Returns: 12.7183472062349
3)
{1,2,3,4}
{1700,1800,1750,1850}
Returns: 100.00499987500625
4)
{1,2,3,4}
{1,4,9,16}
Returns: 0.0Here, only an interval consisting of a single point can be similar to another interval. The length of such an interval is obviously 0.
5)
{5,11,25,58,92,162,255,350,458,566,677,792,919,1051,1189,1331,1489,1673,1882,2093,2315,2541,2771,3012,3254,3524,3797,4087,4379,4675,4973,5278,5588,5904,6225,6550,6888,7249,7612,8018,8428,8847,9267,9688,10109,10530,10964,11407,11870,12340,12811,13288,13768,14249,14734,15242,15774,16306,16847,17400,17966,18533,19108,19692,20278,20871,21471,22074,22679,23297,23916,24553,25190,25829,26472,27135,27814,28497,29181,29865,30555,31272,31994,32729,33487,34246,35005,35764,36537,37326,38119,38913,39725,40538,41360,42185,43010,43840,44671,45509,46350,47205,48063,48932,49807,50691,51577,52464,53289,54119,54950,55788,56629,57484,58342,59211,60086,60970,61856,62743,63568,64398,65388}
{1505,1462,1436,1416,1463,1421,1411,1450,1497,1465,1423,1394,1391,1367,1358,1323,1310,1279,1268,1279,1311,1342,1359,1387,1414,1376,1424,1382,1373,1335,1359,1318,1275,1266,1227,1203,1168,1163,1184,1144,1169,1207,1250,1235,1209,1162,1124,1148,1168,1202,1190,1155,1179,1194,1195,1195,1203,1240,1218,1245,1220,1190,1208,1180,1182,1148,1139,1126,1152,1159,1147,1158,1112,1091,1101,1116,1123,1086,1126,1110,1128,1085,1132,1145,1135,1140,1117,1081,1120,1131,1081,1032,1071,1102,1071,1065,1068,1027,980,947,987,968,959,980,990,974,1003,996,999,958,911,878,918,899,890,911,921,905,934,927,930,889,844}
Returns: 11940.179271014536
