Mr.obeidat's blog

By Mr.obeidat, history, 5 years ago, ,

Hello everyone. how i could avoid time limit exceeded in this problem E.Time Limit Exceeded? http://codeforces.com/gym/100676

• 0

 » 5 years ago, # |   0 Hello...This problem solvable using Binary Search, but you need to edit something in the algorithm. 1- read the input. 2- sort the sequence. 3- initialize answer = 0. 4- For i=0 to n do: s = i; // start e = n-1; // end res=i; While s<=e do: // binary search m = (e+s)/2; // mid if(abs(x[i]-x[m])>31) // if the difference more than 31. e = m - 1; else{ // so we found element with difference less than or equal to 31. s = m + 1; res=m; // save it!! } endWhile answer += res-i; // add the distance between the desired element and the current location. endFor 5- print the answer. // hope this helped you. ^_^ 
•  » » 5 years ago, # ^ |   0 There is no need to use Binary Search. Two pointers can do step 4 in O(n)
•  » » » 5 years ago, # ^ |   0 can you show me how we can code it using two pointers
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0
•  » » » » 5 years ago, # ^ |   0 Just keep two pointers P1 and P2, initially both pointing to the first element. If increasing P2 won't cause them to be 32 apart, increase it. If it will cause them to be too far apart, then increase P1.Each time you increase P1 you can add (P2-P1) before increasing it, and there you go!Both pointers will travel a total distance of O(N), it is often easy to replace binary with two pointers.If you want to be super-optimal you could even replace the regular sorting with counting sort, making use of small values, to achieve linear solution for the whole problem :)
•  » » » » 5 years ago, # ^ |   0 codeline 39-43
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 nothing :/
 » 5 years ago, # |   0 Auto comment: topic has been updated by Mr.obeidat (previous revision, new revision, compare).