I recently asked a question on cs.stackexchange, but since I got no answers there, I figured I should ask here too :)

The problem is the following: We are given a set of intervals (if you want, make it empty in the beginning). Then we have $$$Q$$$ queries, which are of one of the following types:

1. Add a new interval to the set
2. For a given query interval $$$[l_i, r_i]$$$, find the length of the longest interval from the set which is contained entirely inside $$$[l_i, r_i]$$$.

As mentioned in the linked question, if we didn't have query type 1, we can do a persistent segment tree and handle the queries. I have also been thinking we can do SQRT decomposition and answer in $$$O(Q\sqrt Q)$$$. Is there a better algorithm? I would like to be able to do this in $$$O(Q \log Q)$$$ or $$$O(Q \log^2 Q)$$$

The steiner tree problem can be formulated this way:

We have a weighted connected graph (V, E) and a subset of its vertices(let's say it is Q). We have to find a subtree of this graph that has minimal weight and contains Q. Now, this is a "famous" NP problem, but I thought what if the graph was unweighted, or alternatively all edges have the same weight? Is this problem easier or has the same complexity?

Some time ago I stumbled upon the following problem: https://open.kattis.com/contests/g9yde4/problems/excellentengineers

In short: we are given a set of N people. They are ranked in 3 skills, each one has rank for the skills a natural number from 1 to N. A person is interesting iff there is no other person who has better rank in all three skills. Find the number of interesting people. N <= 100 000.

First I tried to solve the problem when each person has only 2 ranks. If this is the case, then the problem becomes easy — we first sort people in descending order of the first skill, then if a person is interesting then his second skill's rank must be better than that of all before him, so we can simply keep maximum. However, I can't think of a way to generalize this apart from keeping some sort of 2D segment tree which will be quite big to fit in memory and will be not so easy to code. So can anybody tell me a better/easier solution? Also additional question: can we generalize this in more than 3 dimensions(let's say K)?

The competition at AtCoder has ended, I participated but couldn't solve F. The editorial link on the website is in Japanese, which I don't understand. Google translate doesn't give me a good translation or at least I cannot understand it. So can anyone share his/her solution to the problem or the solution from the editorial in english. Here is the problem for those that haven't seen it:

Suppose we have a line and N(N <= 10,000) pairs of points on it with coordinates (x_i, y_i). For each pair we can choose the first or the second point. We are to maximize the minimum distance between two consecutive points from the chosen(e.g when they are sorted on the line) which we can obtain by using different choices (whether to use x_i or y_i).

Link to japanese editorial

I recently thought of the following problem: Given a set of N points in the plane(static), we have Q queries. In each query we are given a point with its coordinates and we have to output the point in the set which has maximal distance to the queried point. What is the most efficient algorithm for solving the task(which is not too long/complex to be used in competitions)? Also, what if we could add/remove points from the set? I couldn't think of anything else that bruteforcing every possible point in our set, but I'm looking for something faster(maybe O(logN) per query?).

I encountered the following problem (from last years' zhautikov olympiad). You're given a rooted tree, representing a structure of volunteers. There are Q queries. Each query is the following: you are given a node and a number Ai of tasks. If the node(a volunteer) has no subordinates(children in the tree) then he does the tasks. If he has K subordinates, then there are two cases: if K divides Ai, then the Ai tasks are distributed evenly across all the children, e.g each subordinate receives Ai/K tasks. If K doesn't divide Ai, then the tasks are discarded. The question is, given the tree and the Q queries, consisting of which volunteer receives tasks first, and how many tasks he receives, print the number of discarded tasks for each query. Constraints: Number of nodes in the tree and number of queries is <= 100,000, number of tasks for each query is max. 1,000,000. Can anyone give me a solution to this problem? I've been thinking awhile and I feel stuck.

The title says it all. Is there any online judge which has problems from previous years from the IZhO?

Hello!

I've recently read about persistent segment trees and I found some good resources on the internet. I then remembered a problem I've seen earlier, which is requires algorithm for the following task:

You're given an array A1, A2, A3, ... An (n <= 100000) and lets say that this array is in version 1. Then m <= 100000 queries follow. For each query, we create a new "version" of the array, which is copied from some previous version v, then we increment all elements in the range [l, r] in this new version. Then we must say what is the sum of the elements in the range [i, j] for the new version.

This problem clearly resembles persistent segment tree (sum of ranges). Problem is, changes made aren't linear(if we draw a diagram of the versions, it will be a tree). I think this can be done using the following algorithm (in C++). For representing nodes of segment tree, we create a structure with pointers for left and right and we use lazy propagation. In some array we keep references to the roots of all versions up to now. When we have to build the new version, we take the tree of the old version, we create a new root for the new version. As we do the first step (updating the range [l, r]) we just create new nodes when a modification is needed and reuse those from the old version if they are not used. The problem is, I think that this approach would give correct answer, but I'm not sure about complexity of the algorithm (I need O(nlog(n))). Can somebody tell me whether my idea would work and if yes, what complexity would it have? Thank you in advance. I'll also appreciate if there is some other, easier way to create non-linear persistent segment tree.

After reading the solution to problem D from last CF round, I decided to implement it(the idea with 2D segment tree). I know that there are other(faster) ways to implement segment tree as needed for RMQ, but I wanted to implement it with standard(check my code for what I call standard) implementation of 2D seg tree. Unfortunately, I got TL on test 16. So I wanted to ask whether there is some way to optimise my solution(without using the other faster way to implement segment tree). Link to my code: http://codeforces.me/contest/677/submission/18295468

After getting TLE on test 132 for problem C on CF #350, I tried to optimise. I was surprised when I got AC, because the only thing I needed to change was to replace std::unordered_map with std::map. Does anyone have ideas what causes the different performance? I expected that unordered_map should be faster that map, but it is not the case. And also, is there a way to speed up unordered_map? Here are both submissions:

AC — map: http://codeforces.me/contest/670/submission/17757996

TLE — unordered_map: http://codeforces.me/contest/670/submission/17730894

Does somebody know the reason for the unusual time of CF #325? It's in the middle of the day and students in the morning shift won't be able to participate without being absent from school? It would be great if the round was at 2 or 3 pm so that we can go home before the contest.