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] = f1 = f2 = true. We’ll have that
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.
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
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);
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.
When N<4, then just take minimum of all them.
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);
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);
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…
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.
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.
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.
Can someone point out the mistake in my solution https://www.codechef.com/viewsolution/11575414
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.
