You are not logged in. Please login at to post your questions!


TAASEQ - editorial



Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng




Dynamic Programming


Remove a single number in the sequence to make it an arithmetic progression.


The number at position i can be removed if the sub-sequence on its left and right are both arithmetic progression and when when we concat that two parts they still make an arithmetic progression.

The first condition can be handled by precalculate f[i] = whether the prefix of i characters of the sequence is arithmetic progression and similarly g[] for the suffixes. Put all the corner cases aside the whole conditions can be represented as f[i] and g[i] and a[i - 2] - a[i - 1] = a[i - 1] - a[i + 1] = a[i + 1] - a[i + 2] (1).


We will use dynamic programming (dp) to calculate f and g. Since they are similar let’s just discuss how to calculate f. Initialize the dp with f[0] = f[1] = f[2] = true. We’ll have that

  • f[i] = (a[i - 1] - a[i] = a[i - 2] - a[i - 1] and f[i - 1]).

Before using the formula (1) some corner cases we need to consider is when N ≤ 3, i ≤ 2 and N - 2i.

Complexity is O(N).

Author's/Tester's Solutions:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 18 Sep '16, 15:56

tuananh93's gravatar image

accept rate: 0%

edited 19 Sep '16, 00:28

admin's gravatar image

0★admin ♦♦

Answer is hidden as author is suspended. Click here to view.

answered 19 Sep '16, 02:13

sarvagya3943's gravatar image

accept rate: 36%

I actually had a different type of solution for this. Either we can remove index 1 and see if the remaining sequence is in AP or not. If it is we get one of the possible answers. Now we will definitely make sure index 1 lies in the answer. Now we remove index 2 and see if the sequence is in AP or not. If it is then we get one of the possible answers. Now we definitely include both index 1 and 2 in our solution. This fixes the common difference "d" for our case. Now simply iterate through the array and check for fault positions. If no faulty positions are found, this means the given sequence was already in AP. In such a case find the minimum value in the array which can be removed. If some faulty position is found break at the first one, as we can make exactly one removal. Again after removing these positions check if we get a valid AP or not and update the answer.

Answer is the minimum of all the above 4 cases.

Here is my solution


answered 19 Sep '16, 00:25

likecs's gravatar image

accept rate: 9%


@likecs i did the way u did but got wa did u got ac

(19 Sep '16, 16:53) mahipalsaran3★

If did not get AC, I would not have discussed the approach in detail, rather asked for help :P. As, per your question, I got AC

(19 Sep '16, 16:59) likecs6★

The test cases for this problem are weak.

Here is my accpeted solution :

but it fails on the following test case:



2 3 6 8 13 15 18

The answer for the above test case is -1 but my accepted solution gives 2 (link text)


answered 19 Sep '16, 00:32

tihorsharma123's gravatar image

accept rate: 15%


Test cases are weak.

I have found accepted solutions of people with wrong answers.

Test Cases:



2 4 5 6 8

Given Ans: -1

Right Ans: 5



2 4 5 6

Given Ans: 5

Right Ans: 2

Some code are giving TLE.

I am checking through my compile list


14 7 2 3 6 8 13 15 18 3 3 5 7 3 7 5 3 3 1 7 12 3 12 7 1 5 2 6 7 8 11 3 2 7 12 4 2 5 7 11 4 3 6 7 11 6 2 4 6 15 8 10 5 2 4 5 6 8 4 2 4 5 6 2 1 1 4 4 5 6 8

Ans: -1 3 3 1 1 -1 2 -1 6 15 5 2 1 5

Everyone check your answer against this.

I request to recheck all the submission.


answered 19 Sep '16, 01:09

prakharjain's gravatar image

accept rate: 0%

edited 19 Sep '16, 01:20

Please add the question to practice section @admin @tuananh93


answered 21 Sep '16, 19:31

ankdas1996's gravatar image

accept rate: 0%

Can someone rewrite this editorial with a better explanation ?


answered 06 Nov '16, 05:19

rohitnarayan's gravatar image

accept rate: 0%

I used the same approach while the contest was running as this editorial says . but got WA, I also took care of some boundary cases. can anyone tell mistake in my code.? my solution ( I am storing common diff. of the A.P. starting from 0 and ends at pos i in pre[i] else -1 ) thanks in advance :)


answered 19 Sep '16, 00:29

amanchawla12's gravatar image

accept rate: 0%

Your code fails for this test case



2 4 6 8 10

Your code gives 10 but actual answer is 2 ( we have to output the smallest number)

(19 Sep '16, 00:36) tihorsharma1233★

thanks! it has been submitted!

(19 Sep '16, 00:42) amanchawla123★

can anybody explain me why we need to initialise the dp with f[0]=f[1]=f[2]=true ?


answered 19 Sep '16, 10:32

rdrsadhu's gravatar image

accept rate: 11%

f[0] means "Is it an AP with first 0 elements?" - Yes it is. So, f[0] = true f[1] means "Is it an AP with first 1 elements?" - Yes, a single element is in AP so, f[1] = true; similarly, f[2] is true since any two numbers will always be in AP. And same is true if we took elements from backwards. Hope it helps.

(20 Sep '16, 14:05) easy_2★

Please anybody explain why we need to intialise the dp with f[0]=f[1]=f[2]= true and why we took g[n+1]=g[n]=g[n-1]=true. Please make it clear


answered 19 Sep '16, 15:15

amanpreetsingh's gravatar image

accept rate: 0%

f[0] means "Is it a AP with 0 first elements?" - Yes it is. So, f[0] = true f[1] means "--------------- 1 --------------?" - Yes, a single element is in AP so, f[1] = true; similarly, f[2] is true since any two numbers will always in AP. And same is true if we took elements from backwards. Hope it helps.

(20 Sep '16, 14:06) easy_2★

I Think i did this in a different way -


answered 19 Sep '16, 15:46

avvinci's gravatar image

accept rate: 0%

can someone point out mistake in this solution.I tried all the test cases mentioned above.I have considered three cases: when a1=1St term and a[2] is second term of AP(deque x); when a1=1st term and a[3] is second term of AP(deque y); when a[2]=1st term and a[3] is second term of AP(deque z);


answered 19 Sep '16, 16:44

ronaldo123's gravatar image

accept rate: 0%

Its just a ad hoc for me.. in this only 4 cases will be made.. Firstly array can be increasing order or decreasing order, so Make algo keeping in mind of smallest one. 1. When N<4, then just take minimum of all them. 2. Leave 1st element and check difference from arr[3] to arr[N-1] by taking d=arr[2]-arr[1], If loop iterates through whole element then just take only ans=arr0; 3. Leave 2nd element and check difference from arr[3] to arr[N-1] by taking d=arr[2]-arr[0], If loop iterates through whole element then just take only ans=arr1; 4. This case is boundary or will cover all others like ,d=arr[1]-arr[0].. Loop iterate from arr[2] to arr[N-1] and if condition fail one time then we just store the position of that element and iterate through loop... Here if loop iterates to end without breaking path then we just take minimum of 1st element and last element and print ans otherwise we print the element of that alteration..

To know more Just see my code..


answered 19 Sep '16, 22:47

bansal1232's gravatar image

accept rate: 16%

Can someone help me with my Java solution as well? I checked for corner cases, then stored the count of differences. If there was only one entry, then either first or last element is the answer. If more than three entries (if only only term is wrong then only 2 or 3 different kinds of differences can exist), then invalid solution. Else, I've found the difference which occurs maximum number of times and checked each pair of elements afterwards.



answered 19 Sep '16, 23:10

epsilonalpha's gravatar image

accept rate: 16%

Can someone point out the mistake in my solution I have tried all test cases mentioned above, and it gives the expected answer for all.I divided the problem into three cases, if first element is to be removed, last element is to be removed or any other element except these two is to be removed to convert the sequence into AP.


answered 20 Sep '16, 19:52

nihal_292's gravatar image

accept rate: 0%

I was getting TLE when I used cin - cout and with the statement "ios::sync_with_stdio(0);". But then I simply changed these input output statements to scanf and printf: AC in 0.06 seconds.


answered 26 Oct '16, 13:21

mjguru's gravatar image

accept rate: 0%

can anyone help me with my python submission?i retried a few times and tested all the test cases i can think and find but it works correctly when i was using,however codechef just simply repeat 'Wrong answer',i cant get why link text


answered 11 Nov '16, 16:26

thinker97's gravatar image

accept rate: 0%

You just have to store the difference of adjacent values and count them. If you remove y from x,y,z sequence then you have to check if count of [z-x] + 1 should be equal to N-2.

This is the simplest approach.


answered 20 Mar '18, 03:23

ashudeshwal's gravatar image

accept rate: 0%

Here's my approach, I created a difference array defined by d[i] = v[i+1] - v[i]. Then made a freq set which contains sorted list of pairs of(difference, its frequency) sorted by decreasing frequency.

Click here for submission

  1. If the first element has freq n-1 its already a AP so simply remove the min(first,last) element.
  2. If the first element has freq n-2, then there is 1 unequal element, now it can only be adjusted if that element is either at the front(remove the first element) or at the end(remove the last element) , else the answer is -1.
  3. If the first has freq n-3, then there's 2 other differences. By property of d[] array, if I remove 1 element from v[], then the new d[] is is found by adding the 2 indices and merging it to one. So if the 2 differences does not add to the first element (with freq n-4) then it's impossible so print -1. If it is then check if they are adjacent. If they are adjacent then remove the common element from v[] accordingly else can't make it a AP and print -1

Note: For n=2,3 there is an edge case, it can be easily noted that removing any of the element makes it a valid AP. Thus remove the minimum of all element in this case.

-Thank You


answered 13 Jul '18, 11:35

faded4k's gravatar image

accept rate: 14%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 18 Sep '16, 15:56

question was seen: 5,978 times

last updated: 13 Jul '18, 11:35