Editorial for CTU Open Contest 2017 - Amusement Anticipation - Olympiads Online Judge

Editorial for CTU Open Contest 2017 - Amusement Anticipation

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Naive solution sufficed – for each index $i$ ~i~ of the array, check whether it is a start of an arithmetic sequence $a_i, a_{i+1}, \dots, a_n$ ~a_i, a_{i+1}, \dots, a_n~ by iterating through all of its elements
The smallest such index is the result
This approach runs in $\mathcal O(n^2)$ ~\mathcal O(n^2)~ time

$\displaystyle 6\ 2\ 3\ \underline{5\ 7}$

However, last two numbers of the array are always contained in the optimal arithmetic sequence ending at index $n$ ~n~ ⇒ the difference $d$ ~d~ of the optimal sequence is $a_n-a_{n-1}$ ~a_n-a_{n-1}~ (for $n > 1$ ~n > 1~)
It then suffices to check, starting from the end of the array, how many numbers correspond to the difference
The first index $i$ ~i~, s.t. $a_i+d \ne a_{i+1}$ ~a_i+d \ne a_{i+1}~, is the result (or if no such index exists, the whole array is an arithmetic sequence)
This approach yields an $\mathcal O(n)$ ~\mathcal O(n)~ solution

Comments

There are no comments at the moment.