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*, A*-1, A*+1}
in left direction and in right direction, add ar**(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*-1, i2 = index of A*+1, and i3 = index of A* 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**(V1-V2) to sum for every i from 0 to N-1.

Have a look at This Submission

Please Choose appropriate title for your problem.

PS: Writing an explanation for your problem.

1 Like

Taking time to make implementation as simple as possible.

I remember answering this once: link

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.

Should you feel to need help, add comment.

@taran_1407 if your solution is different from the ones mentioned in that thread then please go ahead and share it.

Mine was to map every value with a smaller value so that we can make frequency array and from that, i will get number of Ai-1 in left and right, Ai+1 in left and right. Rest is easy.

PS: Please help me too for this TLE https://www.codechef.com/viewsolution/16655060

@taran_1407 could u plz elabarote ur approach for 903D??

Indeed i must search properly before posting. btw Awesome solution @meooow much much clear than the posted editorial. you are great buddy :smiley: