On Tue, Jun 11, 2024 at 6:15 PM Aeren <tiltingwindmill1564@gmail.com> wrote:

Yes, this is one of the possible approaches. The other, which is probably what most competitive programmers would do, is just use twice as much memory by maintaining a parallel second `std::set` that's sorted on y instead of x. That way, you can just do lower_bound on the first set to answer queries of type Q2, and lower_bound on the second set to answer queries of type Q3.

If we also require that the element found in Q2 and Q3 must be deleted, this approach doesn't work anymore.

Why not? If you find (x, y) in Q2, you just delete it and then delete (y, x) from Q3 immediately thereafter, and vice versa.

 

 I think we need motivation outside of competitive programming in order to generate interest in standardization. I don't even mention competitive programming to WG21 because I know they'll just laugh at me.

This is my first time proposing and I don't know how things get decided on WG21 so please correct me if I'm missing something, but this statement sounds weird to me for the following reasons

1. In my initial proposal, I stated that my motivation is adding a counterpart to std::partition_point to BBST structures, just like std::lower_bound and std::upper_bound, and this doesn't really sound "competitive-programming-motivated" to me. This is motivated by the "completeness" of the standard library more than anything. 

2. The example I gave applies to any setting that can be abstracted into that form, and it looked general enough that whenever you're dealing with optimization over multivariate functions, I thought that this proposal can be very useful. I'm not sure how adding "competitive programming" changes anything. Would it be better if I instead wrote "I found this abstractization in my production code"?

From a theoretical point of view, I agree that `partition_point` seems like a natural generalization of `lower_bound` and `upper_bound`. The internal balanced binary search tree repeatedly descends into one subtree or another based on some predicate, so why not just let the user specify that predicate directly?

And you can certainly write a paper and submit it in a mailing and get a slot allocated in LEWG to discuss the proposal. If that happens, then there will be a bunch of people in the room, some of them will say "oh yeah, I've also had to do X, Y, and Z where this proposed method would have helped" and there will also be other people who could be persuaded to encourage further work on your paper even if they haven't personally encountered the use cases, if you can convince them that the use cases are common enough to make it worthwhile. If they think that the use cases are rare, they'll probably vote against it.

Writing and presenting papers is a lot of work, so my advice is to think about how you would write the "motivation" section of the paper before you actually start writing it. A code example that could plausibly be in a non-competitive-programming application would help.

 

On Wed, Jun 12, 2024 at 6:38 AM Brian Bi <bbi5291@gmail.com> wrote:

On Tue, Jun 11, 2024 at 5:05 PM Aeren via Std-Proposals <std-proposals@lists.isocpp.org> wrote:

template<class UnaryPred>

iterator partition_point(UnaryPred p);

template<class UnaryPred>

const_iterator partition_point(UnaryPred p) const;

It examines the keys in the container, which must be partitioned by bool(p(key)), and returns the end iterator to the first partition (i.e. the first key which bool(p(key)) is false, end() if no such key).

If the keys are not partitioned with respect to bool(p(key)), the behavior is undefined.

It calls p(key) at most O(log(size() + 1)) times.

Following is one of the use cases I've encountered a lot in competitive programming.

We need to process three kinds of queries, starting from an empty set S. (assume everything fits in int)

Q1. Add a point (x, y) to S, assuming that all x coordinates are non-negative and unique for the sake of simplicity. Same for y coordinates.

Q2. Given A, find the point (x, y) with maximum y such that x >= A, or report that there are none

Q3. Given B, find the point (x, y) with maximum x such that y >= B, or report that there are none

We want to do this online. i.e. if the current query is Q2 or Q3, we only get to know queries after answering it.

With this proposal, there's a simple way to solve this in amortized O(log(n)) time for each queries.

// T contains all points (x, y) such that there is no point (z, w) with x < z and y < w
// Clearly, (x, y) not in T cannot be an answer to Q2 or Q3
// The points are maintained in increasing order of x
// By the definition of T, y coordinates are in decreasing order

std::set<std::pair<int, int>> T;

auto Q1 = [&](int x, int y)->void{

    auto it = T.lower_bound(std::pair{x, y});
    // erase all point (z, w) with z < x and w < y from T
    while(it != T.begin() && std::prev(it)->second < y) T.erase(std::prev(it));
    // insert (x, y) if no point (z, w) satisfy x < z and y < w
    if(it == T.end() || y > it->second) T.insert(it, std::pair{x, y});
};

// Returns (-1, -1) if no answer
auto Q2 = [&](int A)->std::pair<int, int>{
    // use the fact that x coordinate is in increasing order
    auto it = T.partition_point([&](auto key){ return key.first < A; });
    return it == T.end() ? std::pair{-1, -1} : *it;
};

// Returns (-1, -1) if no answer
auto Q3 = [&](int B)->std::pair<int, int>{
    // use the fact that y coordinate is in decreasing order
    auto it = T.partition_point([&](auto key){ return key.second >= B; });
    return it == T.begin() ? std::pair{-1, -1} : *std::prev(it);
};

On Wed, Jun 12, 2024 at 4:29 AM Jonathan Wakely <cxx@kayari.org> wrote:

On Tue, 11 Jun 2024, 20:02 Aeren via Std-Proposals, <std-proposals@lists.isocpp.org> wrote:

Hi, this is my first proposal to C++ STL and I'm looking forward to getting some feedback :)

std::lower_bound / std::upper_bound lets you binary search on a range defined by a pair of legacy random access iterators, and we have a BBST counterpart for this: std::(set / map / multiset / multimap)::(lower_bound / upper_bound)

I would like to propose to add the BBST counterpart of std::partition_point, which generalizes both std::lower_bound and std::upper_bound.

This addition would let us binary search on dynamically changing points with an arbitrary binary predicate on which the points are "partitioned".

What would be your proposed API, what would the precise semantics be, and what are the motivating use cases? 

Currently, there's a workaround for this using the signature (3) and (4) on cppreference lower_bound doc. However, it is very ugly to do this because it forces K and x to be meaningless and forces me to define a weird comparator with K.

Yes, this is one of the possible approaches. The other, which is probably what most competitive programmers would do, is just use twice as much memory by maintaining a parallel second `std::set` that's sorted on y instead of x. That way, you can just do lower_bound on the first set to answer queries of type Q2, and lower_bound on the second set to answer queries of type Q3.

I think we need motivation outside of competitive programming in order to generate interest in standardization. I don't even mention competitive programming to WG21 because I know they'll just laugh at me.

 

Thank you for taking your time to read this proposal :)

Aeren

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals

--

Brian Bi

--

Brian Bi