SimilarRatingGraph
SRM 635 · 2014-08-25 · by Xellos0
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
Formally, the rating graph is a sequence of points (date[i],rating[i]); 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 I 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 I.
Constraints
- date and rating will contain the same number of elements.
- date will contain between 2 and 400 elements, inclusive.
- Each element of date will be between 1 and 1,000,000, inclusive.
- The elements of date will be in strictly increasing order.
- Each element of rating will be between 1 and 5,000, inclusive.
{1,2,4,8,16,32}
{1,2,4,8,16,32}
Returns: 42.42640687119285
The longest interval that's similar to another interval has length 30*sqrt(2) 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).
{81,104,120,124,134,137}
{1866,2332,2510,2678,2876,3002}
Returns: 168.04761230080004
{10,11,13,15,19}
{10,14,15,23,25}
Returns: 12.7183472062349
{1,2,3,4}
{1700,1800,1750,1850}
Returns: 100.00499987500625
{1,2,3,4,5,6,7,8,9,10,11}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 9.0
{1,2,3,4}
{1,4,9,16}
Returns: 0.0
Here, only an interval consisting of a single point can be similar to another interval. The length of such an interval is obviously 0.
{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}
{500,948,1187,1460,1992,1615,1848,1848,2275,2486,2648,2941,3212,3523,3523,3762,4177,4421,4780}
Returns: 239.00209204105306
rd
{1125,1150,1166,1233,1383,1443,1451,1569,1590,1618,1667,1684,1720,1728}
{1532,1282,1296,1570,1644,1656,1608,1779,1653,1893,1990,1733,1866,1879}
Returns: 127.73801313626261
rd
Submissions are judged against all 114 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SimilarRatingGraph with a public method double maxLength(vector<int> date, vector<int> rating) · 114 test cases · 2 s / 256 MB per case