By retrograd, history, 4 weeks ago, Hello!

Today I will present a data structure that I have worked on for my Bachelor thesis a while ago, called (by me) a PreTree (link to thesis). This is a type of "compressed" trie that is arguably easier to implement than a regular compressed trie, and it achieves merging in amortized $O(N L)$ complexity for $N$ keys of equal length $L$. I will present an implementation as a segment tree, though, as it is easier to understand.

Prerequisite: know segment trees, and "sparse" segment trees (a.k.a. bitwise tries).

### Main idea

We will keep a regular segment tree, with the twist that the root contains the minimum key. Basically, a PreTree on keys in the universe $[b, e)$ is a binary tree $T$ where either $T$ is empty, or the following conditions hold:

1. $T$ holds the lowest key present in the range $[b, e)$
2. $T$'s left son is a PreTree on values $[b, \frac{b + e}{2})$
3. $T$'s right son is a PreTree on values $[\frac{b + e}{2}, e)$

Because $T$ is a one-to-one mapping between tree vertices and keys, then the memory complexity of $T$ is obviously $O(N)$.

The reason for the name PreTree comes from it being a "pretty tree" (of course, beauty is subjective), and also because their pre-order traversals yield keys in sorted order.

### Implementation

In order to make the implementation easier, we will define a single big operation called "merging" two PreTrees. Suppose we have two trees $T1$ and $T2$. Merging the two trees would be done as the following recursive procedure:

function Merge(T1, T2, b, e):
if T1 is empty then return T2
if T2 is empty then return T1

m = (b + e) / 2
if T1.k > T2.k then swap T1 and T2
T1.l = Merge(T1.l, T2.l, b, m)
T1.r = Merge(T1.r, T2.r, m, e)
T2.l = T2.r = empty

if T1.k != T2.k:
## We have to insert T2 into the corresponding child
if T2.k >= m:
T1.r = Merge(T1.r, T2, m, e)
else:
T1.l = Merge(T1.l, T2, b, m)
return T1


#### Insertion

In order to insert a key into the tree, just merge it with a singleton tree.

#### Erase

This is a bit more involved. Notice, however, that any PreTree $T$ is a min-heap on the keys. Find the key and then pop it as you would do in a heap.

#### Predecessors

In order to find the greatest key smaller than a given $k$, one can do the following:

function Smaller(T, k):
if T is empty or T.k >= k:
return NOT_FOUND
ret = Smaller(T.r, k)
if ret is NOT_FOUND:
ret = Smaller(T.l, k)
if ret is NOT_FOUND:
ret = T
return ret


Finding the smallest key greater than or equal to a given $k$ is possible, albeit a little more complicated. The simplest way would be to also keep the maximum on the subtree. I will omit the actual implementation.

### Performance

The Merge function seems not too efficient at first glance. However, the amortized complexity of it is bounded by $O(N log(U))$, where $U$ is the size of the universe, and $N$ is the total number of nodes. In order to see why is that, we will have to look at the depths of each node in the tree.

Let's suppose $T1$ and $T2$ have distinct keys. Each non-trivial call to the Merge function increases the depth of at least one vertex. The reason that is true is because, after each call, the root node with the higher key will get "demoted" one level downwards, therefore increasing its depth by one. As depths of a node can never exceed $O(log(U))$, the total complexity cannot exceed $O(N log(U))$.

Follow-up 1: Prove that this still holds for non-distinct keys!

Follow-up 2: What about erase operations? How do they affect the amortized analysis?

Follow-up 3: What about (Treap) splitting operations? Can you split T into two trees, depending on some (monotonic) predicate? How does that affect complexity?

### Applications

One of the most standard applications of this is to improve the $O(N log^2(N))$ bound on various problems involving the small-to-large trick. It has the additional improvement of having $O(N)$ memory without making the implementation a lot harder.

Example problems:

Could you tell me about some other problems involving some form of sparse segment trees and other tasks where this could come handy, to add them to the blog? By retrograd, history, 2 months ago, Hello Codeforces!

For the past couple of years I have been developing a competitive programming platform that would aggregate solutions from different OJs. It was initially written for assigning tasks for my preparations (and some professors used it in our university for grading students in algorithmic courses).

Recently I have been developing a "ladders" feature, because I wanted to train and realized that this would be the best way to do it. Now, I am excited to say that I have decided to "go public" with this feature and invite you to try it out.

### How it works

Do the steps below:

• Create an account at https://competitive.herokuapp.com
• Go to ladders and start solving problems
• When you start a task, a 2-hour timer starts; you have to solve the task in this time limit
• Tasks that are solved successfully are marked green, tasks that were unsolved are marked red
• You can also see a leaderboard with the best performances for the ladders

I will have a strict policy against griefers. If you do one of the following, you will probably get banned:

• Add a Codeforces/Atcoder/etc. account that is not yours
• Try to mess with the website in any way that would harm the data inside it
• Create any scripts that would mass-create tasks/groups/etc
• Exploit bugs of any sorts
• Please don't lie to yourself and cheat

If I see many of such attempts, I will discontinue the website. If you see someone do this, or get affected by it, please report it by completing the feedback form.

### Other features of platform

I might come back here later to showcase some other nice features that I have been using on this platform. Until then, feel free to explore :). If you have ideas of interesting features, please let me know below :).

### Problems?

Please let me know if you find any problems by completing the feedback form on the website, or by writing in the comments. The website is still in development, and there will be a lot of changes in the future. By retrograd, history, 3 months ago, In a recent contest in Romania, there was a problem that was formulated as follows:

Given a convex polygon $P$ given by points $(x_i, y_i)$ in the 2D plane and a number $R$, construct a polygon $P'$ given by $(x'_i, y'_i)$, such that:

• the Euclidean distance between $(x_i, y_i)$ and $(x'_i, y'_i)$ is at most $R$
• the area of polygon $P'$ is as much as possible

It is guaranteed that any two points on the polygon are at distance at least $2R$ apart.

The problem was a bit awkwardly stated, as it required the area not to be the largest possible, but as large as the "model solution". In case you are interested, the task (in Romanian), can be found here. Keep in mind that the task at hand is a bit ill-posed and has some notable problems with floating point precision. However, I'm not as concerned about that, though.

It feels to me that the problem might actually be convex; however, I don't have the mathematical skills to (dis)prove it.

The problem can be formulated in terms of constrained optimization as follows:

max $x'_1 y'_2 + x'_2 y'_3 + ... + x'_n y'_1 - x'_2 y'_1 - x'_3 y'_2 - ... - x'_1 y'_n$

s.t. $(x'_i - x_i)^2 + (y'_i - y_i)^2 \leq R^2$

(here $x'_i, y'_i$ are the actual variables to optimize, excuse me for that)

The constrained space is convex. The objective function seems concave, but I'm not sure how to prove that. For three points, the hessian of the objective function looks like this.

The model solution is to iteratively fix all points apart from one and optimize for a single point (up to convergence). It can be proven rather easily that the best placement lies on the intersection between the perpendicular from $(x_i, y_i)$ to the vector given by $(x_{i - 1}, y_{i - 1})$ and $(x_{i + 1}, y_{i + 1})$ and the circle of radius $R$. Check it out.

• Is the constrained optimization convex?
• If yes/no, does the algorithm above produce the global maximum?
• How are these types of "iterative optimization" algorithms called in literature? Are there known bounds for convergence (in the convex case)? By retrograd, history, 4 months ago, Hello!

After seeing the recent hype towards debugging utils and code snippets usage and what not, and due to the fact that I had 30 minutes of free time to spend this afternoon, I decided to write a small Python script that pre-compiles multiple files into one big file for Codeforces submission.

The tool is here: https://pastebin.com/c4dS4Pik (Python 3 required)

Basically the tool does these steps:

• remove the #include <bla> lines from the code
• run the GCC preprocessor on the code
• add the #include <bla> lines back
• run some cleanup routine (optional)

In order to use this script, copy it somewhere (preferably in your PATH directory), and run it using: /path/to/scr.py file.cpp [ARGS] The ARGS are similar to the ones you would give to your g++ command.

For example, let's say we have three files:

FILE: debug.hpp
FILE: dsu.hpp
FILE: sol.cpp

Output of /path/to/scr.py sol.cpp:

OUTPUT

Output of /path/to/scr.py sol.cpp -DDEBUG:

OUTPUT

The main idea is that it merges all your #include "bla" files (not the #include <bla> ones, though), and replaces all the #defines and other preprocessor instructions.

Let me know what you think! The tool should work fine in UNIX-based systems (Mac OS X, Linux). I would be happy if someone could test/port this tool for Windows. I think one cool thing about this tool is that it pre-compiles all the #defines, so that most of the output code would look more standardized (C++-ish).

I would personally probably not use this tool too much, as my general approach is to copy-paste implementations and tweak them to the specific problem, but I know a lot of people prefer to use them as black boxes, so this might be useful. By retrograd, history, 4 months ago, ### https://github.com/bicsi/autotest

Hello!

For the last two days I have been working on an idea of mine that I had for quite some time but haven't had the time to implement until now. It is a framework for automatic test generation using optimization methods.

### The main point

I want to help people that are into problem-setting but might have problems writing generators (or might have little time to do so). I was thinking that, instead of coming up with complicated generators, one might be able to reuse some generic parametric generators for given structures (partitions, graphs, polygons, etc.) and generate tests by focusing on designing a "fitness" function for a given input case.

Not only that, but many times while preparing problems I found that I was writing some generators by giving them some free parameters and trying to optimize something for the test, while keeping some randomness (for example, making the output answer as big as possible s.t. the constraints, generating test cases that have a given number of candidate solutions, generating test cases where line 100 in my code gets called as much as possible, etc.)

Also, I think it's also useful to have some generic framework for easy hyperparameter optimization with as few distractions as possible (in contests like Hash Code, for example).

I've recently learned about automatic hyperparameter optimization using techniques suitable for fitness functions that take time to compute (e.g. programs), and I've experimented with the hyperopt python library for some university projects. And, to be fair, I was pretty impressed. This thing knows what's about when it comes to optimization.

### The framework

The framework should be more or less simple to use, if you go to the GitHub repository and read the readme file there. I focused my work in having an API that is as clean as it could be as a front-end and which requires as few extra libraries as possible (just clone/download the repository and install some python libraries).

## How to use it

https://github.com/bicsi/autotest

### More tehnical stuff (that's not mandatory to the library users)

Every generator compiled with the autotest framework will allow some under-the-hood extra interaction with the autotest.py script. Populating the autotest::Params is being done via command-line arguments. For example, if you want to feed $n = 5$ into a generator, you have to run it via ./gen -Pn 5. When the .get() method is called, the argument is asserted to have been passed to the executable, and its value is validated and converted to the expected type.

However, the autotest.py can't know about what parameters should be fed into the generator. That's why, the generator compiled with the autotest framework can be run in interactive mode (via --interactive command flag). The only difference here is that when a parameter isn't found as a command-line argument, instead of failing, the generator 'asks' the script via stdin/stdout what its value should be. This way, the autotest.py script "gains knowledge" dynamically about the generator at runtime. This is essential, because that means that you can implement generator libraries with "hidden parameters" that are transparent to the user, and which will be optimized automatically by the script.

Then the script optimizes for the sum of absolute differences between the goal metrics given by the model solution and the goal metrics sought in the tests config file. Some weighted sum might be useful in case of multiple goals, but this hasn't been implemented. It also has some L2 regularization implemented, which means that it penalizes parameters with high absolute value.

### Future work

For now, the framework does not provide a lot of features (but it works, so at least some credit is due :) ). I think a lot of work will be put into trying to create adapters for different random generator libraries for this autotest::Param format with proper modelling (I have some examples inside the lib/generators.hpp file illustrating that, but they are weak).

Integration with Polygon doesn't sound too bad either.

Probably an "as important" other aspect of improvement is on the stability. In this case, if you think the framework is useful and also prepare contests, try to use it for a contest and see how it works. However, don't expect it to work perfectly, as I've only tested it on happy paths.

This version is just the MVP

### Contribution

I feel like this can grow into a rather large project (if you think it deserves to be used), so let me know what your thoughts and ideas are. If you want to contribute, feel free to let me know, and potentially submit a PR (I'm a bit picky about coding style sometimes, so keep that in mind). By retrograd, history, 7 months ago, Hello!

Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.

The implementation is here:

struct LinkCut {
struct Node {
int p = 0, c = {0, 0}, pp = 0;
bool flip = 0;
int val = 0, dp = 0;
};
vector<Node> T;

LinkCut(int n) : T(n + 1) {}

// SPLAY TREE OPERATIONS START

int dir(int x, int y) { return T[x].c == y; }

void set(int x, int d, int y) {
if (x) T[x].c[d] = y, pull(x);
if (y) T[y].p = x;
}

void pull(int x) {
if (!x) return;
int &l = T[x].c, &r = T[x].c;
T[x].dp = max({T[x].val, T[l].dp, T[r].dp});
}

void push(int x) {
if (!x || !T[x].flip) return;
int &l = T[x].c, &r = T[x].c;
swap(l, r); T[l].flip ^= 1; T[r].flip ^= 1;
T[x].flip = 0;
}

void rotate(int x, int d) {
int y = T[x].p, z = T[y].p, w = T[x].c[d];
swap(T[x].pp, T[y].pp);
set(y, !d, w);
set(x, d, y);
set(z, dir(z, y), x);
}

void splay(int x) {
for (push(x); T[x].p;) {
int y = T[x].p, z = T[y].p;
push(z); push(y); push(x);
int dx = dir(y, x), dy = dir(z, y);
if (!z)
rotate(x, !dx);
else if (dx == dy)
rotate(y, !dx), rotate(x, !dx);
else
rotate(x, dy), rotate(x, dx);
}
}

// SPLAY TREE OPERATIONS END

void MakeRoot(int u) {
Access(u);
int l = T[u].c;
T[l].flip ^= 1;
swap(T[l].p, T[l].pp);
set(u, 0, 0);
}

void Access(int _u) {
for (int v = 0, u = _u; u; u = T[v = u].pp) {
splay(u); splay(v);
int r = T[u].c;
T[v].pp = 0;
swap(T[r].p, T[r].pp);
set(u, 1, v);
}
splay(_u);
}

void Link(int u, int v) {
assert(!Connected(u, v));
MakeRoot(v);
T[v].pp = u;
}

void Cut(int u, int v) {
MakeRoot(u); Access(u); splay(v);
assert(T[v].pp == u);
T[v].pp = 0;
}

bool Connected(int u, int v) {
if (u == v) return true;
MakeRoot(u); Access(v); splay(u);
return T[v].p == u || T[T[v].p].p == u;
}

int GetPath(int u, int v) {
MakeRoot(u); Access(v); return v;
}
};


It is around 100 lines long (which is not ideal), but it has some neat features. For example, if you call lc.GetPath(a, b), the implementation will return the root of a splay tree node which contains the whole path from a to b. Also, the function lc.Access(v) will make sure that node v's splay tree would contain the whole path from the root at that time to v.

I feel like there is no implementation with a very clean way of modifying it (for the people who don't know LCT), so I decided to adapt one myself (also, I don't like using raw pointers -- if you're like me, you might enjoy this implementation). Also, another thing that I like about this implementation is that the splay tree code is independent to the fact that it's used inside a link-cut tree (it's just plain splay tree code, which can be extracted away).

In order to adapt the implementation to path aggregates (updates/queries of any type), you would have to create some function that updates/queries the splay tree node GetPath(u, v) and to potentially modify the push and pull methods (push is lazy propagation, whereas pull is regular tree update from children).

The only thing I'm not happy about is that the Access method is pretty ugly. However, I don't want to change its behaviour (I feel it's useful to have v splayed after Access(v) is called). Please let me know if you can rewrite the code in a more beautiful way.

#### Also, here is a pastebin of a strees test code, in case you want to test the implementation.

Any thoughts on how to improve the implementation? What do you think about it overall? By retrograd, history, 7 months ago, Hello!

I will be continuing my "solving problems on first sight" series with another livestream on YouTube tomorrow. In case you missed my first post and don't know what it is about, please refer to my blog posts.

#### The stream is going to be at 5 PM EEST, on Sunday March 22 (note the time difference from my past streams)

Please suggest which problems I should solve by replying to this blog post. Also, let me know if this time doesn't work for you or if I announced it too late.

I hope to see you all tomorrow! By retrograd, history, 8 months ago, Hello!

I will be continuing my "solving problems on first sight" series with another livestream on YouTube this Sunday. In case you missed my first post and don't know what it is about, please refer to the following link:

https://codeforces.com/blog/entry/73212

#### The stream is going to be at 3 PM EEST

If there is a contest and there is a better time for the livestream that would not clash with it, please let me know by Friday and I might adjust the time. As before, you can vote suggestions for what I would solve on this link: https://poll.ly/#/G65O8lOL (please do your best to check that I haven't actually solved the tasks beforehand). I will also be looking for suggestions inside the comments section on this blog and the one before.

I hope to see you all on Sunday! By retrograd, history, 9 months ago, TL;DR I am thinking of holding a series of livestreams on youtube/twitch of me solving problems without having seen them beforehand. I want to highlight how to approach a medium-hard programming task when you are faced one. I want this to be a social and chill environment. Your ideas/feedback would be greatly appreciated.

## TS;WR

Hello guys! I have been doing competitive programming for a while, and lately I have been thinking about how I have developed myself during the past years, and what is different between how I used to approach problems in the beginning and how I do it nowadays. I was thinking that it would be a pretty nice idea to give back my thoughts to the community.

What I was thinking about is recording some videos or streaming myself solving some competitive programming tasks that I haven't seen before. The inspiration for this idea came from a friend (teammate) of mine who wanted to do this quite some time ago, in order to train for ICPC. The format would sound like this: you would propose tasks that you find interesting or that you had been challenged by when approaching them on first sight, and I would try to solve them during the stream (deciphering the statement, finding the solution, implementing the solution).

## Why I want to do this

I have been coaching some people for a while, and during this time I have the feeling that somehow explaining a problem/solution turns out to be very different when you have solved the problem beforehand as opposed to coming up with it when you are facing with the task for the very first time. Not only are there a lot of pitfalls that I tend to forget having made after I had solved a problem, but also it's that a lot of the times I don't recall the thought process that needed to happen in order to solve it. That's why it's sometimes hard for me to even give hints to people, if they're stuck on a task, for example.

With this format, I am hoping to capture and highlight the general thought process that happens between reading the statement of a problem and getting AC on it, in addition to the solution itself. It might also include tips on implementation and debugging along the way.

## Some more details (FAQ style)

So is this some sort of online coaching sessions?

Yes and no. While the main goal of this is me trying to highlight the thought process of solving the problem, I want to see it as more of a group where you and I both discover which ideas and approaches work on tasks, and which don't

What happens when you run out of ideas for a solution?

Some problems might pose difficult for me as well, and given that I would be live, there's a high chance that I might get stuck. At these times, I think I might move on to another problem (which is probably what I would do in a contest), or ask for a hint from you guys.

What I was thinking of is a simple poll where you could add options, and vote for the best ones. This website seems to provide a quite neat interface for creating exactly what I need. You could also post a comment, and whichever comments receive most upvotes will be chosen. This way, the post will be kept more alive until the actual stream.

Some people solve contests; why don't you just do that?

While I certainly don't want to restrict myself to this proposed format, the reason why I am thinking of solving problems "offline" as opposed to during the contest boils down to the fact that even though solving contests would yield a similar scenario, I am usually more stressed during contests, and that would relate to less talking and more thinking; for now, I think solving tasks offline would provide me with enough calm to more easily and succinctly describe my thoughts.

## When is it going to happen?

#### Vote your options here (you can also just comment down below)

Please only use links when adding options. I would pick the tasks that have most votes during the stream. For this session, please restrict yourselves to problems that are not too hard, so that I would be able to build up my courage :). Problems can be on any judge from Codeforces, Atcoder, CSAcademy, Kattis, Infoarena, and others. They can be either ICPC style (preferred) or IOI style. Difficuly level should be around Codeforces Div1 A/B/C (or Div2 C/D/E)

## Final words

I will be updating this post as the week progresses, but I was very eager to post this. I am very excited about this idea, and I can't wait to hear your feedback. Any ideas of yours are greatly appreciated.

I hope that I'll see you during the stream!

UPD: I have settled the stream date, and added a link to my channel.

UPD2: The stream is now on YouTube for whoever wants to watch it. Quick jumps are in the descriptions, for each specific problem. https://www.youtube.com/watch?v=fpxArbp3FLo By retrograd, history, 10 months ago, There seems to be a lot of encouragement for new people to learn segment trees, and in particular the lazy propagation technique, and it seems to me that most of the time it is not actually needed.

As a quick refresher (although I feel most of you would already know), lazy propagation is a technique in segment trees that lets you do updates on whole ranges of elements, by first only updating the smallest factoring of the update range in the tree. For example, in order to update range $[2, 5]$, what you do is you update only ranges $[2, 2], [3, 4], [5, 5]$ in the segment tree, and next time node $[3, 4]$ is accessed you "propagate" the updates downward into ranges $[3, 3]$ and $[4, 4]$. This allows you to effectively aggregate (combine) multiple updates on a given range, to save extra work.

Usually when people talk about lazy propagation, some tasks like "add on range" — "minimum on range" or "add on range" — "sum of range" naturally come to mind. However, I feel like these are poor examples of applications, as most of these can be solved without lazy propagation.

### OMG, how is that possible?

An alternative way one could approach these kind of problems is to keep an extra array $lazy$ with the usual segment tree. $lazy(node)$ is an aggregate of all the update operations done on $node$ until present time. In the above examples, $lazy(node)$ would be the sum of all the updates done on the node. Then the recurrence becomes $data(node) = lazy(node) + min(data(node * 2), data(node * 2 + 1))$ in the "minimum on range" case and $data(node) = data(node * 2) + data(node * 2 + 1) + lazy(node) * length(node)$ in the "sum on range" case (here $length(node)$ denotes the length of the range corresponding to $node$ in the tree.

The way to query is by having an extra parameter passed down in the traversal, which aggregates the operations inside $lazy$ while going down in the tree. The technique is similar to something called "upwards-downwards dynamic programming on trees" in Romania.

An example implementation is here.

### So, you still store lazy array, but you just don't propagate. Why should we care?

Honestly, firstly I would say that it's more simple and natural. A lot of data structure problems I've encountered need some sort of "lazy" value that holds an aggregate of operations that affect the whole structure (take a simple data structure problem, where you have to model adding a constant value to all elements of a collection, and pop the min element, which can be done by using a priority queue, along with an extra value that lazily aggregates all add operations).

Second of all, I think it's easier to debug a solution that does not propagate, as I feel that I can reason about the correctness of the segment tree values more easily with this approach. In contests like ACM ICPC, it is key to debug on paper as much as possible when applicable, and with this approach one could simulate the range updates and build expectations upon the data structure at different points in time easier.

Third of all (and maybe most importantly), it is way faster. I will probably make a full comparison if people are interested, but from my experience I found that lazy propagation yields a particularly slow solution (hidden constant is bigger), probably because it does a lot more mutations on the underlying array, and this approach reduces that constant very considerably.

### Ok, then, why ever propagate?

Well, it seems that not all problems can be solved via this method. For example, a "set to constant value on range" and "sum on range" type problem cannot be easily solved by this. What is particular about these scenarios is that the update operations are order-dependent (in other words, they are not commutative). However, in a lot of cases the update operations are commutative, and I don't see why any of these kind of problems would use lazy propagation instead of this technique.

I'm curious to hear your opinions on this. By retrograd, history, 12 months ago, I was recently trying to solve problem K. Kingdom of Ants on Kattis. However, my submission strangely receives a Memory Limit Exceeded verdict, and I can see no way of achieving that with my code.

Do you guys spot any reasons why the above code would give MLE? Maybe some weird C++ undefined behaviour, or maybe some compiler flaw?

UPDATE: After checking for the (very degenerate) case if there is only one y-coordinate (right between lines 119 and 120), the solution gets Accepted verdict. However, I still don't understand why the initial verdict was MLE, and it was very misleading.

By retrograd, history, 3 years ago, I wanted to showcase a simpler algorithm for the closest pair of points in 2D problem, and maybe to discuss its performance / countercases.

The problem is:

Given N distinct points in Euclidean 2D space, compute the minimum (squared) distance between any two distinct points.

The usual approach here is a divide-and-conquer algorithm, which can be found virtually anywhere, including on Wikipedia. The complexity of this algorithm is O(nlog(n)), but it is rather tricky to achieve this complexity.

The alternative approach (based on the same algorithm), is to do sweep-line. We sort the points based on the x-coordinate and we keep a set of the points in the region x - d, x, sorted by y coordinate. Here d is the smallest distance so far (we do that with the two-pointers technique). Now, for each new point x, y, we query the whole range y - d, y + d in this set and possibly update our answer.

Due to the proof of the D&C algorithm, at each time the quieried range should be of size O(1) on average, so total complexity would be O(nlog(n)). Code is below:

long long ClosestPair(vector<pair<int, int>> pts) {
int n = pts.size();
sort(pts.begin(), pts.end());
set<pair<int, int>> s;

long long best_dist = 1e18;
int j = 0;
for (int i = 0; i < n; ++i) {
int d = ceil(sqrt(best_dist));
while (pts[i].first - pts[j].first >= best_dist) {
s.erase({pts[j].second, pts[j].first});
j += 1;
}

auto it1 = s.lower_bound({pts[i].second - d, pts[i].first});
auto it2 = s.upper_bound({pts[i].second + d, pts[i].first});

for (auto it = it1; it != it2; ++it) {
int dx = pts[i].first - it->second;
int dy = pts[i].second - it->first;
best_dist = min(best_dist, 1LL * dx * dx + 1LL * dy * dy);
}
s.insert({pts[i].second, pts[i].first});
}
return best_dist;
}


What do you think? Are there any special cases (e.g. many points at the same x coordinate) that would break the solution? By retrograd, history, 3 years ago, This article will be presenting a rather classical problem that can be solved using deques, along with an extension that allows you to solve the problem in its more general multi-dimensional case. I have decided to write this article after this discussion on 2D range-minimum query.

The article will be mainly based on this following problem:

#### You are given an array of numbers A[] of size n and a number k ≤ n. Find the minimum value for each continuous subarray of size k.

We will be now focusing on the linear-time solution to this problem.

Solution:

Consider sweeping from left to right through the array. At every moment we keep a list of "candidates" for minimum values throughout the process. That means that at each moment, you have to add one element to the list and (potentially) remove one element from the list.

The key observation is that, during the sweep line process, we find two values A[i] and A[j] which have i < j and A[i] ≥ A[j], then we can safely discard A[i]. That is because, intuitively, A[j] will continue to "live" in our sweep line more than A[i], and we will never prefer A[i] instead of A[j].

We should now consider pruning all the "useless" values ("useless" as in the statement above). It is easy to see now that doing this will lead to a strictly increasing list of candidates (why?). In this case, the minimum will always be the first element (O(1) query).

In order to insert an element to the back of the pruned candidate list, we will do a stack-like approach of removing all elements that are greater than it, and to erase on element, we just pop the front of the list (if it is not already removed).

This is a well-known approach for finding minima over fixed-size continuous subarrays. I will now present an extensions that allows you to do the same trick in matrices and even multi-dimensional arrays.

## The multi-dimensional extension

Problem (2D):

#### You are given an matrix of numbers A[][] of size n × m and two numbers k ≤ n, l ≤ m. Find the minimum value for each continuous submatrix of size k × l.

Solution:

Consider the matrix as a list of rows. For each row vector of A, use the 1D algorithm to compute the minimum value over all l-length subarrays, and store them in ColMin[][] (obviously, ColMin[][] is now a n × (m - l + 1)-sized matrix).

Now, consider the new matrix as a list of columns. For each column vector of ColMin, use the algorithm to compute the minimum value over all k-length subarrays, and store them in Ans[][] (of size (n - k + 1) × (m - l + 1)).

The Ans[][] is the solution to our problem.

The following picture shows the intutition behind how it works for computing Ans for n = 5, m = 7, k = 3, l = 4 The pseudocode is as follows:

def solve_2d(M, k, l):
column_minima = {} # empty list
for each row in M.rows:
# We suppose we have the algorithm that solves
# the 1D problem
min_row = solve_1d(row, l)
column_minima.append_row(min_row)

ans = {}
for each col in column_minima.cols:
min_col = solve_1d(col, k)
ans.append_col(min_col)

return ans


Note that the pseudocode is (deliberately) hiding some extra complexity of extracting rows / columns and adapting the 1D algorithm to the 2D problem, in order to make the understanding of the solution clearer.

The total complexity of the algorithm can be easily deduced to be O(n * m)

#### Multi-dimensional case analysis

The solution can be extended to an arbitrary order of dimensions. For a d-dimensional matrix of size s1, s2, ..., sd, the time-complexity of the problem is O(d * s1 * ... * sd), and the memory complexity is O(s1 * ... * sd). This is much better than other algorithms that do the same thing on non-fixed size submatrices (e.g. multi-dimensional RMQ has O(s1 * ... * sd * log(s1) * ... * log(sd)) time and memory complexity).

## Finding the best k minima

The deque approach itself is limited in the sense that it allows you to find only the minimum value over the ranges. But what happens if you want to calculate more that one minimum? We will discuss an approach that I used during a national ACM-style contest where we were able to calculate the best 2 minima, and then argue that you can extend to an arbitrary number of minimum values.

In order to store the lowest 2 values, we will do the following:

Keep 2 deques, namely D1 and D2. Do a similar algorithm of "stack-like popping" on D1 when you add a new element, but instead of discarding elements from D1 when popping, transfer them down to D2 and "stack-like pop" it.

It is easy to see why the lowest 2 elements will always be in one of the two deques. Moreover, there are only 2 cases for the lowest two elements: they are either the first two elements of D1, or the first elements of D1 and D2 subsequently. Checking the case should be an easy thing to do.

The extension to an arbitrary number of minima is, however, not so great, in the sense that the complexity of this approach becomes O(n * k2) for a n-sized array, currently bottlenecked by the number of elements you have to consider in order to find the first k minima. [Maybe you can come up with a cleverer way of doing that?]

This is the problem I referred to above: http://www.infoarena.ro/problema/smax. I recommend trying to think it through and implementing it, and translating the statement via Google Translate or equivalent. rmq,
By retrograd, history, 5 years ago, Hello! I am a fairly advanced programmer (although I'm pretty new), and I know the basic algorithms and data structures used for most problems. However, I don't know how to get better from this state onwards.

I should say that my strength is mainly DS problems. Greedy, D&C, DP I do pretty well (once I recognize a specific-type problem), constructive algorithms seem very hard to me (for example link). For DS, I know pretty much all there is to know about segment trees, BIT, sqrt-decomposition (I call it a DS, don't blame me :D), BSTs, hash, etc (the basic ones), although problems that involve advanced tricks with these (e.g. persistent segment trees, lazy propagation) seem very appealing.

I want to prepare mysef for this year's ACM-ICPC contest, as it is my first year in Uni. I have been learning algo intensively since December.

I would be grateful if you know any good lists of problems that are really crucial and/or teach useful new techniques, as I am stuck momentarily. I have read the results on Google for ACM algorithms and such, so a personal response would be a lot more appreciated :).

I will also try to keep a list updated with interesting problems and techniques, in case other people struggle with the same issue. Maybe this tread will become a learning portal for more people :D.

### LIST:

• (http://e-maxx.ru/algo/) -> there are a lot of algorithmic problems greatly explained, as well as tricks and great algorithms -- the website is in Russian, although it can be translated using Google Translate -- great resource

Thank you a lot! list,