FoxSequence
SRM 498 · 2010-11-01 · by ir5
SRM 498 · 2010-11-01 · by ir5 · Simple Search, Iteration
Problem Statement
Problem Statement
Fox Ciel likes sequences. One day, she invented a new type of sequence and named it the fox sequence. A sequence seq containing N elements is called a fox sequence if and only if there exist four integers a, b, c and d such that 0 < a < b <= c < d < N-1 and the following five conditions are met:
In the following image, the top 3 sequences are fox sequences, while the bottom 3 sequences are not:
You are given a sequence seq. Return "YES" if it is a fox sequence, or "NO" if it is not (all quotes for clarity).
- seq[0], seq[1], ... , seq[a] forms an arithmetic progression with a positive common difference. An arithmetic progression is a sequence where the difference between successive elements is equal. The difference between successive elements is called the common difference. Note that 0 is neither positive nor negative.
- seq[a], seq[a+1], ... , seq[b] forms an arithmetic progression with a negative common difference.
- seq[b], seq[b+1], ... , seq[c] are all equal.
- seq[c], seq[c+1], ... , seq[d] forms an arithmetic progression with a positive common difference.
- seq[d], seq[d+1], ... , seq[N-1] forms an arithmetic progression with a negative common difference.
In the following image, the top 3 sequences are fox sequences, while the bottom 3 sequences are not:
You are given a sequence seq. Return "YES" if it is a fox sequence, or "NO" if it is not (all quotes for clarity).
Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 1 and 2,000, inclusive.
Examples
0)
{1,3,5,7,5,3,1,1,1,3,5,7,5,3,1}
Returns: "YES"
This is the top-left sequence of the image shown in the statement. The next five examples are also from that image.
1)
{1,2,3,4,5,4,3,2,2,2,3,4,5,6,4}
Returns: "YES"
2)
{3,6,9,1,9,5,1}
Returns: "YES"
3)
{1,2,3,2,1,2,3,2,1,2,3,2,1}
Returns: "NO"
4)
{1,3,4,3,1,1,1,1,3,4,3,1}
Returns: "NO"
6)
{1}
Returns: "NO"
N=1
7)
{20,19}
Returns: "NO"
N=2
8)
{5,5}
Returns: "NO"
N=2
9)
{7,8}
Returns: "NO"
N=2
10)
{1,2,1,2,1}
Returns: "YES"
smallest fox
11)
{3,5,8}
Returns: "NO"
N=3
12)
{12,18,12}
Returns: "NO"
N=3
13)
{30,99,30,99}
Returns: "NO"
N=4
14)
{55,99,65,65}
Returns: "NO"
N=4
15)
{34,45,56,9}
Returns: "NO"
N=4
16)
{3,2000,1,1998,2}
Returns: "YES"
N=5, fox
22)
{2000,2000,2000,2000,2000}
Returns: "NO"
N=5, non-fox
37)
{1293,1413,1533,1334,1485,1310}
Returns: "YES"
N>=6, fox (random)
57)
{1000,1050,1100,1150,1200,1250,1300,1350,1400,1450,1500,1450,1400,1350,1300,1250,1200,1150,1100,1050,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1050,1100,1150,1200,1250,1300,1350,1400,1450,1500,1450,1400,1350,1300,1250,1200,1150,1100,1050}
Returns: "YES"
N=50, fox (beautiful fox sequence)
58)
{1,2000,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2000,1}
Returns: "YES"
N=50, fox (maybe edge cases)
63)
{2000,1967,1934,1901,1868,1835,1802,1769,1736,1703,1670,1637,1604,1571,1538,1505,1472,1439,1406,1373,1340,1307,1274,1241,1208,1175,1142,1109,1076,1043,1010,977,944,911,878,845,812,779,746,713,680,647,614,581,548,515,482,449,416,383}
Returns: "NO"
Straight Chain(non-fox)
66)
{460,491,522,553,584,615,646,677,708,739,770,801,832,863,894,925,956,987,1018,1049,1080,1111,1142,1173,1204,1235,1266,1297,1328,1301,1274,1247,1220,1193,1166,1139,1112,1085,1058,1031,1004,977,950,923,896,869,842,815,788,761}
Returns: "NO"
2-Chain
69)
{398,429,460,491,522,553,584,615,646,677,708,739,770,801,832,863,894,925,956,987,1018,1049,1080,1111,1142,1173,1204,1235,1266,1239,1212,1185,1158,1131,1104,1077,1050,1023,1023,1023,1023,1023,1023,1023,1023,1023,1023,1023,1023,1023}
Returns: "NO"
3-Chain
70)
{264,295,326,357,388,419,450,481,512,543,574,605,636,667,698,729,760,791,822,795,768,741,714,687,660,633,606,579,552,525,525,525,525,525,525,525,525,525,525,525,525,525,568,611,654,697,740,783,826,869}
Returns: "NO"
4-Chain
71)
{923,969,1015,1061,1107,1153,1199,1245,1291,1337,1288,1239,1190,1141,1092,1043,994,945,896,847,847,847,847,900,953,1006,1059,1112,1165,1218,1271,1324,1377,1430,1483,1536,1589,1541,1493,1445,1397,1349,1301,1253,1205,1157,1109,1061,1013,12}
Returns: "NO"
+1 Noize at tail
75)
{500,969,1015,1061,1107,1153,1199,1245,1291,1337,1288,1239,1190,1141,1092,1043,994,945,896,847,847,847,847,900,953,1006,1059,1112,1165,1218,1271,1324,1377,1430,1483,1536,1589,1541,1493,1445,1397,1349,1301,1253,1205,1157,1109,1061,1013,965}
Returns: "NO"
+1 Noize at head
79)
{923,969,1015,1061,1594,1153,1199,1245,1291,1337,1288,1239,1190,1141,1092,1043,994,945,896,847,847,847,847,900,953,1006,1059,1112,1165,1218,1271,1324,1377,1430,1483,1536,1589,1541,1493,1445,1397,1349,1301,1253,1205,1157,1109,1061,1013,965}
Returns: "NO"
+1 Noize at random position
83)
{1933,1807,1681,1555,1429,1303,1177,1051,925,771,617,463,309,155,155,155,155,280,405,530,655,780,905,1030,1155,1280,1405,1530,1655,1780,1905,1667,1429,1191,953,715}
Returns: "NO"
5-separator
89)
{1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014,1014}
Returns: "NO"
4-Separator
95)
{1082,1108,1134,1160,1186,1229,1272,1315,1358,1401,1444,1487,1530,1573,1616,1389,1162,935,708,481,613,745,877,1009,1141,1273,1273,1273,1273,1273,1273,1273,1273,1273,1273,1273,1273,1273,1415,1557,1699,1841,1983}
Returns: "NO"
6-Separator
101)
{2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1,2000,1}
Returns: "NO"
ZigZag
102)
{3,1999,2,2000,1,2000,1,2000,2,2000,1,2000,2,1999,2,1998,3,1999,2,2000,3,1998,3,1998,3,1998,3,2000,2,1999,2,2000,1,1998,1,1998,2,1999,2,1998,2,1999,3,2000,2,1998,3,1999,2,1999}
Returns: "NO"
ZigZag part 2
103)
{833,736,1952,396,782,794,1671}
Returns: "NO"
Completely Random (Small)
106)
{55,1356,1779,562,1411,1464,1530,541,938,1286,1775,1539,1741,16,876,651,625,1301,1346,431,1094,334,85,1382,1168,251,1078,1952,1325,737,463,17,896,651,476,1628,955,1059,1306,775,76,8,873,318,759,352,1548,141}
Returns: "NO"
Completely Random (Large)
109)
{1000,1050,1100,1150,1200,1250,1300,1350,1400,1451,1500,1450,1400,1350,1300,1250,1200,1150,1100,1050,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1050,1100,1150,1200,1250,1300,1350,1400,1450,1500,1450,1400,1350,1300,1250,1200,1150,1100,1050}
Returns: "NO"
+alpha
Submissions are judged against all 242 archived test cases, of which 35 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxSequence with a public method string isValid(vector<int> seq) · 242 test cases · 2 s / 256 MB per case