Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя Mr.obeidat

Автор Mr.obeidat, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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. ^_^        
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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 :)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        code

        line 39-43

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      nothing :/