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
For your struct
operator <returns onlyBut for
std::pair<int, int>the corresponding operator will returnBut that shouldn't give wrong answer.
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 youroperator <it follows that all such elements are equal. Withpair<int, int>, the set will store one element per eachfirst/secondcombination.I made the change. Still wrong.
Link: http://mirror.codeforces.com/contest/424/submission/6474158
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 tostd::setandstd::upper_bound.Ok, andreyv . Thanks for your input. I definitely need to brush up my STL knowledge again. :/
now with std::pair 6474287 TL, not WA
you have written comparator, but didn't use it :)
because std::pair operator< is
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
Thank you SO MUCH Igorjan94 . It's so careless of me to use the other version of lower_bound.
But when you iterate from
::set.begin()to::set.end(), the elements are in a sorted fashion. So shouldn't the other version oflower_boundalso work?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.std::lower_boundwill use something likestd::distanceandstd::advanceto operate on the iterator range. But these functions are linear in time if they operate on forward iterators instead of random iterators.