You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] 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

asked 27 Dec '17, 18:05

divik544's gravatar image

4★divik544
5251110
accept rate: 10%

closed 27 Dec '17, 22:17

1

Please Choose appropriate title for your problem.

PS: Writing an explanation for your problem.

(27 Dec '17, 18:14) taran_14075★

Taking time to make implementation as simple as possible.

(27 Dec '17, 19:05) taran_14075★

I remember answering this once: link

(27 Dec '17, 19:09) meooow ♦6★

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.

(27 Dec '17, 19:11) taran_14075★

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

(27 Dec '17, 19:14) meooow ♦6★

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

(27 Dec '17, 19:27) taran_14075★

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

(27 Dec '17, 19:44) vivek_19982996★

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

(27 Dec '17, 22:16) divik5444★
showing 5 of 8 show all

The question has been closed for the following reason "Duplicate Question" by divik544 27 Dec '17, 22:17


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.

link

answered 27 Dec '17, 19:24

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

edited 27 Dec '17, 19:25

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

link

answered 27 Dec '17, 20:36

taran_1407's gravatar image

5★taran_1407
4.0k31105
accept rate: 22%

edited 27 Dec '17, 20:38

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×890
×688

question asked: 27 Dec '17, 18:05

question was seen: 322 times

last updated: 27 Dec '17, 22:17