Zzyzx's blog

Weird Error
By Zzyzx, 11 years ago, In English

Spoiler Alert: This is regarding problem D of the latest Codeforces round (242).

Link to problem statement: http://mirror.codeforces.com/contest/424/problem/D

I have two solutions, Let's call them sol-1 and sol-2

Link to sol-1: http://mirror.codeforces.com/contest/424/submission/6472455

Link to sol-2: http://mirror.codeforces.com/contest/424/submission/6472637

In sol-1 I use a struct node

struct node {
  int tot, col;
  bool operator <(const node &rhs) const {
    return tot < rhs.tot;
  }
};

In sol-2 I use std::pair <int, int> with the necessary changes to the remaining part of the code.

In sol-1 I get TLE on test case 17.

But In sol-2 I get WA on test case 3.

How is that possible?! Can someone please help me out?

UPD: Found my mistake. Thank you so much Igorjan94 and andreyv

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

For your struct operator < returns only

lhs.tot < rhs.tot

But for std::pair<int, int> the corresponding operator will return

lhs.first != rhs.first ? lhs.first < rhs.first : lhs.second < rhs.second
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But that shouldn't give wrong answer.

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

      You insert values into a set. With your struct, the set will store at most one element for each tot, ignoring the second value — because from your operator < it follows that all such elements are equal. With pair<int, int>, the set will store one element per each first/second combination.

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

        I made the change. Still wrong.

        Link: http://mirror.codeforces.com/contest/424/submission/6474158

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          You can insert debugging output and see that your function isn't even called. If you still want to use pair<int, int>, you have to define a comparator functor and pass it to std::set and std::upper_bound.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Ok, andreyv . Thanks for your input. I definitely need to brush up my STL knowledge again. :/

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

          now with std::pair 6474287 TL, not WA

          you have written comparator, but didn't use it :)

          → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

because std::pair operator< is

template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ 
    return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); 
}

your solution, but accepted 6474171

difference is in lower/upper_bound. You used this, and set doesn't have random access iterator so works linear time, but I changed it to this and it works in logarithmic time

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

    Thank you SO MUCH Igorjan94 . It's so careless of me to use the other version of lower_bound.

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

    But when you iterate from ::set.begin() to ::set.end() , the elements are in a sorted fashion. So shouldn't the other version of lower_bound also work?

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

      yes. if we iterate for (auto it = set.begin(); it != set.end(); ++it), the elements are in a sorted fashion. But std::lower_bound can't get random element. Of course it works, but much slower.

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

      std::lower_bound will use something like std::distance and std::advance to operate on the iterator range. But these functions are linear in time if they operate on forward iterators instead of random iterators.

      → Reply