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

Автор Zzyzx, 11 лет назад, По-английски

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

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

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

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

Link to sol-2: http://codeforces.net/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

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

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

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

    But that shouldn't give wrong answer.

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

      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.

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

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

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

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

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

    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?

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

      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.

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

      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.