ZCO16002 - Editorial

editorial
, , ,
1

PROBLEM LINK

ZCO16002

DIFFICULTY

Easy

PREREQUISITES

Dynamic Programming

PROBLEM IN SHORT

Output the length of the longest arithmetic sequence possible from the elements of the given array

SOLUTION

The first thing to observe is that the order of elements in the array doesn’t matter. Thus, to simplify
things - we just sort the array. This takes O(n log n) time - which is well within the constraints.

A naive approach to the problem would be to look at one pair of elements, take their difference and
find the largest length of AP possible with this difference and the given two elements as the first
two numbers. This will clearly take O(n^3), thus it would fail on the second sub-task.

Now, observe that to define an AP, we require the last two elements and it’s length. The difference
of the last two elements would be the common difference of the AP. Using dynamic programming,
we can compute dp[i][j], where dp[i][j] is length of the AP with the last two elements as a[i] and a[j].

For the recursive function, we need to find the previous element in the AP. This can be done in
O(1) time if we maintain another array, location, where location[i] represents the index of number i
in array a if it exists, otherwise location[i] = -1.

Now, simply, difference = a[j] - a[i], and previousElement = a[i] - difference. Hence, if
location[previousElement] = -1, dp[i][j] = 2, else, dp[i][j] = dp[ location[previousElement] ][i] + 1.

Finally, the answer is simply the maximum dp[i][j] over all i and j.

TIME COMPLEXITY

O(n^2)

EDITORIALIST’s SOLUTION

#include <bits/stdc++.h>
using namespace std;

int dp[2507][2507], n, a[2507], locOfNumber[1000007];

int recur(int i, int j) {
	if (i < 0 || j < 0 || i >= n || j >= n)
		return 0;
	if (dp[i][j] != -1)
		return dp[i][j];
	else if (i == 0)
		return dp[i][j] = 2;
	else {
		int diff = a[j] - a[i];
		int prev = a[i] - diff;
		if (prev >= 0) {
			int prevInd = locOfNumber[prev];
			if ( prevInd != -1 )
				return dp[i][j] = recur(prevInd, i) + 1;
			else
				return dp[i][j] = 2;
		}
		else
			return dp[i][j] = 2;
	}
}

int main() {
	memset(dp, -1, sizeof(dp));
	memset(locOfNumber, -1, sizeof(locOfNumber));
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		locOfNumber[a[i]] = i;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i != j)
				ans = max(ans, recur(i,j) );
		}
	}
	printf("%d", ans);
	return 0;
}
2

Nice way to do this, but I had a different approach and to be frank I am still slightly amazed that it passed. After sorting and starting a nested loop within the outer loop. Something like :

for ( int i = 0 ; i < n ; i++ ){
    for ( int j = i + 1 ; j < n ; j++ ){
        diff = a[j] - a[i] ;
        // rest of the code
    }
}

And after finding each diff, using the formula for finding the next element of the AP I found the next element and searched for it using binary search , decreasing the search space every time.
And even though your approach is much more efficient , I wanted to show that dumb solutions can also pass if the testcases are benevolent enough :wink:
Anyway , my solution for reference, if someone really wishes to do it this way 27996359

3

Or you could store the presence of elements in a map and u just check if A[j]+d existed in map (Which is O(1)) , thus saving you even more time.

4

Map takes O(log n) check up.

5

In java :man_technologist:, by using only arrays we will get a partial correct answer, as searching takes linear time
using the set (for searching as all elements are distinct)along with arrays will give correct answer

6

Can anyone tell why i am getting WA although it would have been fine if i would have got TLE because mine solution is bruteforce. Mine solution link

7

Very Interesting, But how did you got the intution to solve this problem, like how you thought this relation?