TAASEQ - editorial

editorial
, , , ,
6

You can also store the count of difference between adjacent elements .

Suppose you have x,y,z and you remove y , the count of (z-y) and (y-x) would decrease by 1 and the count of (z-x ) would increase by 1 .

Now to check if the remaining sequence is an AP or not , all you need to check is that there exists a “difference” with count = n-2 .

4 Likes
7

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

8

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

9

I Think i did this in a different way - Zj8LHm - Online C++0x Compiler & Debugging Tool - Ideone.com

10

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

11

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=arr[0](First element);
  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=arr[1](2nd element);
  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…CodeChef: Practical coding for everyone

12

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.

Submission

13

Can someone point out the mistake in my solution CodeChef: Practical coding for everyone
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.

14

Please add the question to practice section @admin @tuananh93

1 Like
15

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.

16

Can someone rewrite this editorial with a better explanation ?

1 Like
17

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 repl.it,however codechef just simply repeat ‘Wrong answer’,i cant get why
link text

18

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.

19

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

20

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)

21

thanks!
it has been submitted!

22

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

1 Like
23

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

1 Like
24

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.

25

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.