Cheerio Contest 1 J5 - Arithmetic Sequence

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

rickyqin005

Problem type

You are given a list of $N$ $N$ integers $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ . Determine whether or not you can modify the list into an arithmetic sequence by rearranging the list and/or changing the value of at most $1$ $1$ number.

An arithmetic sequence is a sequence in which each term is obtained by adding the previous term by a constant number, called the common difference. For example, $2, 5, 8, 11$ $2, 5, 8, 11$ is an arithmetic sequence with a common difference of $3$ $3$ .

Constraints

For all subtasks:

$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

Points Awarded	$N$ $N$
6 points	$2 \le N \le 400$ $2 \leq N \leq 400$
5 points	$2 \le N \le 4\,000$ $2 \leq N \leq 4 000$
4 points	$2 \le N \le 2 \times 10^5$ $2 \leq N \leq 2 \times 10^{5}$

Input Specification

The first line contains one integer $N$ $N$ .

The second line contains $N$ $N$ integers $a_i$ $a_{i}$ .

Output Specification

Output YES if the list can be modified to become an arithmetic sequence and NO otherwise.

Sample Input 1

Copy

4
3 1 5 10

Sample Output 1

Copy

YES

Explanation for Sample Output 1

We can change the $4^{\text{th}}$ $4^{th}$ number in the list to be $7$ $7$ . The list of numbers becomes $3, 1, 5, 7$ $3, 1, 5, 7$ , which can be rearranged to form the arithmetic sequence $1, 3, 5, 7$ $1, 3, 5, 7$ .

Sample Input 2

Copy

5
3 6 9 12 15

Sample Output 2

Copy

YES

Explanation for Sample Output 2

The list is already an arithmetic sequence, so no changes are necessary.

Comments

0

ColonelBy_team10 commented on June 30, 2022, 7:57 p.m.

Can change element in array to negative number?