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.
Can someone rewrite this editorial with a better explanation ?
1 Like
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
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.
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.
- If the first element has freq n-1 its already a AP so simply remove the min(first,last) element.
- 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.
- 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