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

×

TAASEQ - editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming

Problem

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

Solution

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).

details

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

5★tuananh93
116513
accept rate: 0%

edited 19 Sep '16, 00:28

admin's gravatar image

0★admin ♦♦
19.0k348495533


12next »

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

answered 19 Sep '16, 02:13

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
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 https://www.codechef.com/viewsolution/11559787

link

answered 19 Sep '16, 00:25

likecs's gravatar image

6★likecs
3.5k1361
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 : https://www.codechef.com/viewsolution/11562158

but it fails on the following test case:

1

7

2 3 6 8 13 15 18

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

link

answered 19 Sep '16, 00:32

tihorsharma123's gravatar image

4★tihorsharma123
45718
accept rate: 15%

Yes,

Test cases are weak.

I have found accepted solutions of people with wrong answers.

Test Cases:

1

5

2 4 5 6 8

Given Ans: -1

Right Ans: 5

1

4

2 4 5 6

Given Ans: 5

Right Ans: 2

Some code are giving TLE.

I am checking through my compile list

Testcase:

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.

link

answered 19 Sep '16, 01:09

prakharjain's gravatar image

4★prakharjain
111
accept rate: 0%

edited 19 Sep '16, 01:20

Please add the question to practice section @admin @tuananh93

link

answered 21 Sep '16, 19:31

ankdas1996's gravatar image

5★ankdas1996
41
accept rate: 0%

Can someone rewrite this editorial with a better explanation ?

link

answered 06 Nov '16, 05:19

rohitnarayan's gravatar image

1★rohitnarayan
352
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 :)

link

answered 19 Sep '16, 00:29

amanchawla12's gravatar image

4★amanchawla12
1
accept rate: 0%

Your code fails for this test case

1

5

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) tihorsharma1234★

thanks! it has been submitted!

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

Used a different approach.

First I find the sum of all the given numbers. Now at each i, I will remove the ith number from the given list (and will subtract it from the cumulative sum too) and will check, whether the new sum obtained is equal to the sum of the first and last elements of the (supposedly) AP multiplied by the number of terms (now N-1), and divided by 2 or not. (Since we know that this is the actual formula for sum of all numbers in an AP). This is the first condition.

Secondly, we must check whether there exists a common difference or not. For that just check whether the difference between the first and last term in AP, is divisible by (N-1) or not (i.e. the difference is an integral multiple of N-1).

If both conditions are satisfied, we obtain a valid AP. Removing the minimum number clearly means that the sum of all numbers in the AP must be maximum. That can be taken care of.

My solution: https://www.codechef.com/viewsolution/11559413

Note that in order to avoid decimal point issues, I am multiplying the LHS in condition 1 by 2 (rather than division on RHS by 2).

link

answered 19 Sep '16, 00:48

utkarsh1997's gravatar image

4★utkarsh1997
7749
accept rate: 11%

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

link

answered 19 Sep '16, 10:32

rdrsadhu's gravatar image

4★rdrsadhu
1306
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

link

answered 19 Sep '16, 15:15

amanpreetsingh's gravatar image

3★amanpreetsingh
1
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★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×14,487
×3,212
×1,790
×42
×13

question asked: 18 Sep '16, 15:56

question was seen: 5,605 times

last updated: 13 Jul, 11:35