Блог пользователя adipro1167

Автор adipro1167, история, 4 года назад, По-английски

Hello Codeforces! In the contest, Codeforces Round #648, in B problem- Trouble Sort, I thought of using the Custom Compare Function, though later I realized it wasn't required here. But a general problem that I have faced in Custom Compare Function is that I have never understood its working. Sometimes, I make my own Custom Functions and they work but how- I don't understand. I read about it on Sort()-CPP Reference and Sort(): GeeksForGeeks but I did not understand its working. I wrote the following code:

#define lpr pair<long long int,long long int>
#define S second
#define F first
#define ll long long int
bool comparefn(lpr a, lpr b)
{
    if(a.S!=b.S)
    return a.F<=b.F;
    return false;
}

This is my custom compare function and I used it as:

vector<lpr> a;
sort(a.begin(),a.end(),comparefn)

It passed the first test case successfully but failed in the second one. On debugging I found that it fails for the following case:

5 1 5
0 0 1

Output: No But for the case:

5 5 1
0 1 0

Output: Yes. It works correctly.

Please explain me a dry run of this test case with the custom compare function which I have made. It would be of great help. Thanks in Advance!

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

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

You should use first_value < second_value instead of first_value <= second_value in your compare function.

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

    I tried that also and got the same result.

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

      I mean

      bool comparefn(lpr a, lpr b)
      {
          if(a.S!=b.S)
          return a.F<b.F; // instead of <=
          return false;
      }
      

      Have you tried it?

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

    Why you need to do that? I figured out my code was not functioning as it should by using a <= instead of <?

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

        Thanks a lot qwexd. I tried to debug on my own but could not find mistake for very long. Finally found the mistake after reading this blog. For other people: If you use custom comparator for sorting, don't use <= operator. Instead use < operator. Ex.

        // correct way
        auto comp=[&](int a,int b){
                return a<b;
            };
        
        // leads to all kinds of errors 
        auto comp=[&](int a,int b){
                return a<=b;
            };
        
»
4 года назад, # |
Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

You need stateful comparator to use STL sort for this problem, your comparefn() cannot be used here.

Let us consider the following input: [3,0 2,1 1,1]

STL implementations differ, but let us assume std::sort() is dispatched to insertion_sort() if the number of elements to be sorted is less than 10 (our case). So we have iterations like this:

1: [3,0]
2: is 2,1 lt 3,0? yes, so swap elements -> [2,1 3,0]
3.1: is 1,1 lt 3,0? yes, so swap elements -> [2,1 1,1 3,0]
3.2: is 1,1 lt 2,1? no (second parts are equal, and comparefn() returns false in this case) so elements are not swapped and data are not sorted as a result.
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The problem is that the order of the swaps you want to perform may not be the same as the order in which the STL sort function makes its comparisons. The STL sort is one way to sort an array, but it doesn’t perform the only set of swaps that could potentially sort the array. When we can’t necessarily perform any swap we want, we need to verify that all sorting functions fail, rather than just one of them.

In general, going about this problem with built-in sorting cautions just isn’t the right approach. Failing to sort the array using one method of sorting tells you nothing about whether there’s some other way to perform the sorting.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Your comparefn isn't a compare function since it does not fulfil the requirements of the Compare concept, namely that of transitivity. Thus sort can not work with it.