Mr.obeidat's blog

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

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no need to use Binary Search. Two pointers can do step 4 in O(n)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you show me how we can code it using two pointers

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        code

        line 39-43

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      nothing :/

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Mr.obeidat (previous revision, new revision, compare).