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)