# Almost difference help

I am unable to solve the problem 903D

i am unable to get the approach from the editorial. It would be great if anyone could help me with this problem

I think we can solve it using segment tree.Traverse from right to left,and add elements to segment tree ,so at index i,i have a segment tree for indices i+1 to n-1,so store two things in segment tree ,first sum and count,we store these at the value ie if arr[]={3},segment[3:3]={1,3} (Count,sum),so for element ai,search for ai+2,int_max and int_min,ai-2 ,so res+=sum1-cnt1 * ai + cnt2 * ai - sum2, u could use cordinate compression if values are large.

My idea is to first map input array to smaller values (to enable creation of frequency array).

Now, read input, put value as key and its index in count table as value in map. Develop a count array simultaneously.

Initialize another count array.

Now, loop from 0 to N-1, Deriving count of Number of elements Not belonging to set {A[i], A[i]-1, A[i]+1}
in left direction and in right direction, add ar[i]*(left - right) to Final answer and output.

Calculation of Number of elements can be done as follows.

During the loop, we are maintaining another count array NEWcount, which is count of elements In left side. So, if i1 = index of A[i]-1, i2 = index of A[i]+1, and i3 = index of A[i] in count table, Then:

1. Reqd Number of elements in left side V1 = i - (NEWcount[i1]+NEWcount[i2]+NEWcount[i3])
2. Reqd Number of elements in right side V2 = N - (count[i1]+count[i2] + count[i3]) - V1.

Add ar[i]*(V1-V2) to sum for every i from 0 to N-1.

Have a look at This Submission

PS: Writing an explanation for your problem.

1 Like

Taking time to make implementation as simple as possible.

Oh yeah…

I too remember my incorrect solution. @meooow

@divik544, i don’t think there would be need to another explanation, seeing that @meooow’s solution is very clear.