THREEAPFREE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Tester: udhav2003
Editorialist: iceknight1093

DIFFICULTY:

1170

PREREQUISITES:

None

PROBLEM:

Given a sorted sequence of integers, check whether it is AP-free or not.

EXPLANATION:

Since N is quite small here (in particular, it’s \leq 100), there’s a rather straightforward solution utilizing nested loops.

From the definition of AP-free sequences, all we need to do is to check whether there are three indices 1 \leq i \lt j \lt k \leq N such that (A_j - A_i) = (A_k - A_j)

To do this, use nested loops to iterate across all possibilities of i, j, and k.
The pseudocode for this would look something like

for i from 1 to N:
    for j from i+1 to N:
        for k from j+1 to N:
            check if a[j] - a[i] == a[k] - a[j]

which you can then translate into code for your language of choice.

TIME COMPLEXITY

\mathcal{O}(N^3) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 'Yes'
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if a[j] - a[i] == a[k] - a[j]: ans = 'No'
    print(ans)
2

Is there a better way to solve this rather than N^3 ?

3

I think if we use hashmap to store all the elements then simply check if(ai+ak==aj/2) if exist simply we return false else we return true

Time complexity: O(n^2)
Space Complexity: O(n)

4

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

int main() {
int t;
cin >> t;

while (t--) {
    int N;
    cin >> N;

    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int d = arr[1] - arr[0]; 
    bool flag = true;  
    for (int i = 1; i < N - 1; i++) {  
        if (arr[i + 1] - arr[i] != d) {  
            flag = false;  
            break;  
        }
    }

    if (flag) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

return 0;

}

why is this solution not correct?

5

I thought the O(n^3) solution will give TLE so I didn’t write the solution and thinking of some another approach :sweat_smile:

6

I coded in O(n^2) time complexity and constant space, there is no requirement of hashmap