What Mo's algorithm essentially does is this:

Given a set of q points in the plane, where the i-th point is (x_i, y_i) and 1 ≤ x_i ≤ y_i ≤ n, find a permutation of those points such that is minimized. So, the first question is this:
Does Mo's algorithm give us the optimal solution for this problem, or just an approximation of the optimal solution? The first problem is somewhat similar to the rectilinear (Manhattan distance) travelling salesman problem.
The second question is this: If Mo's algorithm actually gives us an approximation of the optimal solution (which seems to be the case), how much better is the optimal solution? (i.e. let's assume that the total distance in Mo's algorithm is x, and the total distance in the optimal solution for some set of points is y. What is the greatest value of y - x or ?) Also, what are some interesting observations about the optimal solution?
Question 3: What's the best algorithm that gives an exact solution to the first problem?

Hello everyone, I came up with this problem and I can't figure a solution out. I don't know if it has appeared before.
You are given a matrix of size n × m. Answer two types of queries:
- 1 k i₁ i₂ ... i_k: Set the active set to {i₁, i₂, ..., i_k}.
- 2 x: What is the value of a_i1, x + a_i2, x + ... + a_ik, x, where i₁, i₂, ..., i_k are the current elements in the active set?
There are less than n queries of type 1, and less than m queries of type 2 between a pair of queries of type 1.
1 ≤ n, m ≤ 2000, however solutions with any reasonable complexity are welcome.
Also, if a query of type 1 appears for the i-th time, 1 ≤ k ≤ i, and all the indices in the query do not exceed i.

Hello everyone, I found this problem a while ago and I'm still stuck on it (there's no OJ to submit it as far as I know):
You are given a permutation of the integers from 1 to N. In this case, moving an element from i to j is defined as removing the element from position i, and inserting it at position j. For example, in this array: [4,5,2,1,3], moving the element from 2 to 5 gives us the array [4,2,1,3,5]. The cost of moving an element from i to j is defined as i + j (1-indexed).
What is the minimum total cost needed to sort the permutation?
Example:
[1,3,4,5,2] → [1,2,3,4,5] with total cost 5 + 2 = 7.
1 ≤ N ≤ 1000, however solutions with any reasonable complexity are welcome.

Hello everyone, I thought of this problem yesterday: Given a matrix of length N and width M, answer Q queries of this form:
- x₁ y₁ x₂ y₂: Count the number of distinct elements in the submatrix with corners (x₁, y₁) and (x₂, y₂).
There is a version of this problem on Codechef, however the bounds for A_i, j are very small. Is there a way to solve this for e.g. A_i, j ≤ 10⁵? I don't have any particular time complexity in mind.

UPD: It turns out that this problem is named "colored orthogonal range counting". It has been solved in "Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization" and "Efficient Colored Orthogonal Range Counting".

This article is about a solution to a variation of 894D - Ralph And His Tour in Binary Country, with (almost) complete binary trees replaced by arbitrary trees. The solution turned out to be more complicated than I thought, so I decided to post it as a separate blog.
The main idea is to fix the LCA, just like the original problem.
Note: We are calculating the sum of all H_i - L, such that

where x is any destination vertex and d_v is the distance from the root to the v-th vertex.
Therefore, we could calculate the answer using the following functions:

// dist[v] = sorted list of d_x, where x is any node in v's subtree
// prefsum[v] = prefix sum array of dist[v]
typedef long long i64;
i64 helper(int v, i64 val) {
	if(v == 0) return 0;
	auto x = std::upper_bound(dist[v].begin(), dist[v].end(), val);
	if(x == dist[v].begin()) return 0;
	i64 cnt = std::distance(dist[v].begin(), x);
	return cnt * val - prefsum[v][cnt - 1];
}
i64 solve(int v, int c, i64 happiness, int start) { // par[root] = 0
	if(v == 0) return 0;
	i64 val = happiness - d[start] + 2 * d[v];
	return helper(v, val) - helper(c, val) + solve(par[v], v, happiness, start);
}
i64 query(int v, i64 happiness) {
	return solve(v, 0, happiness, v);
}

We could use this code to calculate the answer for an arbitrary tree, however queries would take time.
We can speed this algorithm up by using centroid decomposition. We will create a "centroid tree", and create a vector for each node that stores the distances from each node to the nodes in its subtree.
Let d(x, y) be the distance from node x to node y. Then, we need to calculate the sum of all H_i - L such that , where v is an ancestor of A_i in the centroid tree, and x is a node in v's subtree, but not in the subtree containing A_i.
Note that we can use the exact same helper function to calculate the answer for a single vertex, however we also need to find a way to subtract the answer for v's children. We can reduce subtree queries to range queries on an array using the Euler tour technique.
We also need a data structure that supports the following operations:
1. count(l, r, x): count the number of elements in [l, r] such that a_i ≤ x.
2. sum(l, r, x): calculate the sum of elements in [l, r] such that a_i ≤ x.
We can use a wavelet tree/persistent segment tree/simple segment tree (offline).
In the following code, let idx[v] be the index of vertex v in the DFS order, and sz[v] be the size of v's subtree in the centroid tree. Then, the code can be adapted for the centroid tree like this:

// we build a separate data structure for every vertex
data_structure DS[MAXN];
i64 helper(int v, int l, int r, int val) {
	if(l > r) return 0;
	return DS[v].count(l, r, val) * val - DS[v].sum(l, r, val);
}
i64 solve(int v, int c, int happiness, int start) {
	if(v == 0) return 0;
	int x = idx[c] - idx[v] + 1;
	int y = x + sz[c] - 1;
	i64 val = happiness - d[v][idx[start] - idx[v] + 1];
	return (c == 0 ? helper(v, 1, sz[v], val) : helper(v, 1, x - 1, val) + helper(v, y + 1, sz[v], val)) + solve(par[v], v, happiness, start);
}
i64 query(int v, i64 happiness) {
	return solve(v, 0, happiness, v);
}

This solution takes time per query. (solve is called times per query, and every helper query takes time.)
Disclaimer: This is the first time I have used centroid decomposition. Feel free to point out any flaws in this approach. I will try to post a full solution later. Update: The initial version stated that this was a solution for arbitrary binary trees. It is actually a solution for any tree.

Hello everyone, I thought of this problem after reading 875D - High Cry and I can't figure out a solution.
Let's call an integer y a subset of an integer x, if x | y == x.

You have to answer q queries of two types:

• 1 x Add the integer x to the set S. (initially, the set S is empty)
• 2 x Of all the integers currently in S, how many is x a subset of?

1 ≤ x ≤ 10⁹, 1 ≤ q ≤ 10⁵.

When is it possible to color the vertices of a hypercube graph Q_k with k colors, such that for every vertex v, the colors of its adjacent vertices are pairwise distinct?
Example for Q₂: We can color any two adjacent vertices with the same color, and color the other two vertices with another color. Then for every vertex, its neighbors will be colored differently.

In C, it's possible to use the bsearch() function to perform binary search on a 'hidden' array. e.g. for IOI 2015 practice — Search (part of task description below):

You may call a function compare(i, val) that compares number A_i and integer number val. This function returns:
-  - 1: if A_i > val
- 1 if A_i < val
- 0 if A_i = val.

Now, bsearch() can be used like this:

int values[1000];
int cmp(const int * a, const int * b)
{
   int id = b - values;
   return compare(id, *a); 
}
int find(int sub, int N, int X) {
    int* ptr = bsearch(&X, values, N, sizeof(int), cmp);
    return ptr == NULL ? -1 : ptr - values;
}

Is something like this possible using std::lower_bound?