Longest Progression Solution Google Kickstart 2021

Longest Progression Solution Google Kickstart 2021

Problem

Sarasvati learned about arithmetic arrays. An arithmetic array is an array that contains at least two integers and the differences between consecutive integers are equal. For example, [9,10][9,10], [3,3,3][3,3,3], and [9,7,5,3][9,7,5,3] are arithmetic arrays, while [1,3,3,7][1,3,3,7], [2,1,2][2,1,2], and [1,2,4][1,2,4] are not.

Sarasvati again has an array of NN non-negative integers. The ii-th integer of the array is AiAi. She can replace at most one element in the array with any (possibly negative) integer she wants.

For an array AA, Sarasvati defines a subarray as any contiguous part of AA. Please help Sarasvati determine the length of the longest possible arithmetic subarray she can create by replacing at most one element in the original array.

Input

The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case begins with a line containing the integer NN. The second line contains NN integers. The ii-th integer is AiAi.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 1) and yy is the length of the longest arithmetic subarray.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100
0≤Ai≤1090≤Ai≤109.

Test Set 1

2≤N≤20002≤N≤2000.

Test Set 2

2≤N≤3×1052≤N≤3×105 for at most 1010 test cases.
For the remaining cases, 2≤N≤20002≤N≤2000.

Sample

Sample Input

3
4
9 7 5 3
9
5 5 4 5 5 5 4 5 6
4
8 5 2 0

Sample Output

Case #1: 4
Case #2: 6
Case #3: 4

In Sample Case #1, the whole array is an arithmetic array, thus the longest arithmetic subarray is the whole array.

In Sample Case #2, if Sarasvati changes the number at third position to 55, the array will become [5,5,5,5,5,5,4,5,6][5,5,5,5,5,5,4,5,6]. The subarray from first position to sixth position is the longest arithmetic subarray.

In Sample Case #3, Sarasvati can change the number at the last position to −1−1, to get [8,5,2,−1][8,5,2,−1]. This resulting array is arithmetic.

Also Read:

Solution:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1000005;
const ll MOD = 1000000007;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[N];

void go(){
int n;
cin>>n;
for(int i = 1; i <= n; ++i){ cin>>a[i];
}
if(n == 2){
cout<<“2\n”;
return;
}
int ans = 3;
for(int i = 1; i <= n; ++i){
ll d = a[i + 1] – a[i];
int r = i;
while(r <= n && a[r] == a[i] + (r – i) * d)
++r;
if(r == n + 1){
ans = max(r – i, ans);
break;
}
if(r == n){
ans = max(r – i + 1, ans);
break;
}
int tr = r + 1;
while(tr <= n && a[tr] == a[i] + d * (tr – i))
++tr;
ans = max(ans, tr – i);
i = max(i, r – 2);
}
reverse(a + 1, a + n + 1);

for(int i = 1; i <= n; ++i){
    ll d = a[i + 1] - a[i];
    int r = i;
    while(r <= n && a[r] == a[i] + (r - i) * d)
        ++r;
    if(r == n + 1){
        ans = max(r - i, ans);
        break;
    }
    if(r == n){
        ans = max(r - i + 1, ans);
        break;
    }
    int tr = r + 1;
    while(tr <= n && a[tr] == a[i] + d * (tr - i))
        ++tr;
    ans = max(ans, tr - i);
    i = max(i, r - 2);
}

cout<<ans<<'\n';

}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int tt;
cin>>tt;
for(int i = 1; i <= tt; ++i){
    cout<<"Case #"<<i<<": ";
    go();
}

}

Longest Progression Solution Google Kickstart 2021

Leave a Comment