Evg
BAN USERLinear search:
template<typename N, class RNG>
N random_exclude(N max, std::initializer_list<N> il, RNG&& gen) {
assert(std::is_sorted(il.begin(), il.end()));
std::uniform_int_distribution<N> distr(0, max - il.size());
auto r = distr(gen);
for (auto value : il)
if (value <= r)
++r;
else
break;
return r;
}
Binary search:
template<class It, typename T>
It upper_bound_vmi(It first, It last, T value) {
auto left = first;
auto right = last;
while (left < right) {
const auto mid = left + (right - left) / 2;
if (*mid <= value + static_cast<T>(mid - first))
left = mid + 1;
else
right = mid;
}
return right;
}
template<typename N, class RNG>
N random_exclude(N max, std::initializer_list<N> il, RNG&& gen) {
assert(std::is_sorted(il.begin(), il.end()));
std::uniform_int_distribution<N> distr(0, max - il.size());
const auto r = distr(gen);
return r + static_cast<N>(upper_bound_vmi(il.begin(), il.end(), r) - il.begin());
}
C++ solution:
template<class It, class Fn>
void smallest_pair_sums(It first1, It last1, It first2, It last2, std::size_t n, Fn fn) {
using Heap_node = std::pair<It, It>;
using Set_node = std::pair<std::ptrdiff_t, std::ptrdiff_t>;
struct Comparator {
bool operator()(Heap_node p1, Heap_node p2) const {
return *p2.first + *p2.second < *p1.first + *p1.second;
}
};
struct Hash {
std::size_t operator()(Set_node p) const {
return std::hash<Set_node::first_type>{}(p.first) ^ std::hash<Set_node::second_type>{}(p.second);
}
};
std::priority_queue<Heap_node, std::vector<Heap_node>, Comparator> min_heap;
std::unordered_set<Set_node, Hash> set;
const auto insert = [&](auto it1, auto it2) {
const Set_node key{it1 - first1, it2 - first2};
if (it1 != last1 && it2 != last2 && set.count(key) == 0) {
min_heap.emplace(it1, it2);
set.insert(key);
}
};
insert(first1, first2);
while (!min_heap.empty() && n-- > 0) {
const auto [it1, it2] = min_heap.top();
min_heap.pop();
fn(it1, it2);
insert(it1 + 1, it2);
insert(it1, it2 + 1);
}
}
If C (n in my code) is small (say, C <= 32), just do a linear search. Otherwise, do a binary search:
inline constexpr std::ptrdiff_t n_threshold = 32;
template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements1(
Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
if (first == last || n <= 0)
return {pos, pos};
auto left = pos;
auto right = pos + 1;
while (--n > 0 && left != first && right != last)
if (*right - *pos < *pos - *(left - 1))
++right;
else
--left;
if (left == first)
right += std::min(n, last - right);
if (right == last)
left -= std::min(n, left - first);
return {left, right};
}
template<class Random_access_it>
std::pair<Random_access_it, Random_access_it> closest_elements2(
Random_access_it first, Random_access_it last, Random_access_it pos, std::ptrdiff_t n) {
if (first == last || n <= 0)
return {pos, pos};
if (last - first <= n)
return {first, last};
auto left = first + std::max(std::ptrdiff_t{0}, (pos - first) - (n - 1));
auto right = pos - std::max(std::ptrdiff_t{0}, n - (last - pos));
while (left != right)
if (const auto mid = left + (right - left) / 2; *(mid + n) - *pos < *pos - *mid)
left = mid + 1;
else
right = mid;
return {left, left + n};
}
template<class Random_access_it, class T>
std::pair<Random_access_it, Random_access_it> closest_elements(
Random_access_it first, Random_access_it last, const T& value, std::ptrdiff_t n) {
if (n <= n_threshold) {
const auto pos = std::find(first, last, value);
return closest_elements1(first, last, pos, n);
} else {
const auto pos = std::lower_bound(first, last, value);
return closest_elements2(first, last, pos, n);
}
}
After reading papers referenced by Chris (thanks, Chris!), I've come up with the following solution:
struct Node
{
Node* left = nullptr;
Node* right = nullptr;
};
template<class G>
Node* random_binary_tree(std::size_t n, G&& gen)
{
Node* root;
auto curr = &root;
std::stack<Node*> st;
std::size_t m = n;
while (n > 0)
{
std::uniform_int_distribution<std::size_t> distr(0, (n + m) * (n - m + 1) - 1);
if (distr(gen) < (n + 1) * (n - m))
{
const auto node = st.top();
st.pop();
curr = &(node->right);
--n;
}
else
{
const auto node = new Node;
st.push(node);
*curr = node;
curr = &(node->left);
--m;
}
}
return root;
}
std::string tree_to_braces(const Node* root)
{
if (root)
return '(' + tree_to_braces(root->left) + ')' + tree_to_braces(root->right);
else
return {};
}
int main()
{
std::mt19937 gen;
std::map<std::string, std::size_t> counts;
for (int i = 0; i < 100'000; ++i)
{
auto tree = random_binary_tree(4, gen);
auto str = tree_to_braces(tree);
++counts[str];
}
for (auto c : counts)
std::cout << c.first << " -> " << c.second << std::endl;
}
The transition (W, R) -> (W - 1, R) has probability 1 - [R/(W+R)]^2, and the transition (W, R) -> (W, R - 1) has probability [R/(W+R)]^2.
After that you need just a couple of nested loops:
double last_white_prob(std::size_t nw, std::size_t nr)
{
const auto sq = [](double x) { return x * x; };
std::vector<double> prob(nr + 1);
prob[nr] = 1;
for (auto r = nr; r > 0; --r)
prob[r - 1] = sq(r) * prob[r] / sq(nw + r);
for (auto w = nw - 1; w > 0; --w)
{
prob[nr] *= 1 - sq(nr) / sq(w + nr + 1);
for (auto r = nr; r > 0; --r)
prob[r - 1] += (sq(r) * prob[r] - sq(r - 1) * prob[r - 1]) / sq(w + r);
}
return prob[0];
}
Simple O(N^2) solution is just a rotation in a loop:
template<class It>
void aabb_to_abab(It first, It last)
{
assert((last - first) % 2 == 0);
for (auto n = last - first; n > 2; n -= 2)
std::rotate(first + n / 2 - 1, first + n / 2, first + n - 1);
}
More involved O(N) solution is based on the decomposition of the permutation into cycles (this resembles the dolphin algorithm for array rotation). We don't know the number of cycles in advance, hence we have to count the number of elements left to process (the first and the last elements form cycles by themselves).
template<class It>
void aabb_to_abab(It first, It last)
{
assert((last - first) % 2 == 0);
auto n_left = last - first - 2;
const auto n = (last - first) / 2;
auto start = n;
while (n_left > 0)
{
auto curr = start;
auto hole = std::move(*(first + curr));
while (true)
{
--n_left;
const auto next = curr / 2 + n * (curr % 2);
if (next == start)
break;
*(first + curr) = std::move(*(first + next));
curr = next;
}
*(first + curr) = std::move(hole);
++start;
}
}
If integers are unsigned, just concatenate bits; if they are signed, reserve two bits for signes:
template<typename T>
T f(T x, T y) {
if constexpr (std::is_signed_v<T>) {
const bool is_neg_x = (x < 0);
const bool is_neg_y = (y < 0);
const T xy = (std::abs(x) << (4 * sizeof(T) - 1)) | std::abs(y);
return (xy << 2) | (is_neg_x ? 1 : 0) | (is_neg_y ? 2 : 0);
}
else
return (x << (4 * sizeof(T))) | y;
}
template<typename T>
std::pair<T, T> f_inv(T i) {
if constexpr (std::is_signed_v<T>) {
const bool is_neg_x = (i & 1);
const bool is_neg_y = (i & 2);
constexpr T mask = (T{1} << (4 * sizeof(T) - 1)) - 1;
const T x = (i >> (4 * sizeof(T) + 1)) & mask;
const T y = (i >> 2 ) & mask;
return {is_neg_x ? -x : x, is_neg_y ? -y : y};
}
else {
constexpr T mask = (T{1} << (4 * sizeof(T))) - 1;
return {i >> (4 * sizeof(T)), i & mask};
}
}
The average number of executions of `do` body is n / (n - len(ex)).
- Evg March 06, 2020