Yeah, this is the first time I've seen a non-deterministic algorithm used on CF. I assumed that their problems were always deterministic, so I just thought the problem was impossible and stopped working on it lol. That being said, I didn't actually calculate the probability of success when choosing k random indices, and you could write a program to calculate that probability for you and find the optimal k, so I do actually think it's a cool problem in hindsight.

I think so. This problem was also solved by many using randomized algorithm. However, the editorial came out and I found out there was a deterministic solution. I was quite impressed. The belief that contest problems did not intend randomized algorithm was still intact.

I was also wondering what the deterministic solution could be for this problem and I must say I am somewhat disappointed :/ I found the randomized algorithm for this problem quite early but there was always a chance for this failing so I did not submit

364D - Ghd

I think it's for the bad English

It is not ready. We will finish it tomorrow.

Насчитаем изначальные расстояния обычной Дейкстрой, далее будем обрабатывать запросы в исходном порядке.

Пусть пришел запрос на увеличение ребер, пересчитаем расстояния. Введем потенциалы, равные dist_u, заменим веса ребер на w'_i = w_i + dist_ai - dist_bi. Очевидно, что в новом графе все веса неотрицательные (неравенство треугольника в графе), а расстояния до каждой вершины равны нулю.

Прибавим изменения к w'. Расстояние до каждой вершины не более количества изменений c, поэтому в новом графе можно пустить Дейкстру подсчетом за O(N + M + c).

Чтобы получить исходные расстояния, нужно прибавить к расстояниям в новом графе потенциал, т.е. newdist_u = dist'_u + dist_u. Итого получилось , где C — суммарное число изменений.

Let b₁, b₂, b₃, ..., b_n be the sorted version of a. Fix x, 1 ≤ x ≤ n. Let x' be such that b_x' = a_x. Using DSU, merge the two sets containing x' and x. Do this for all x, and then count the number of disjoint sets.

https://en.wikipedia.org/wiki/Set_(mathematics)

we need to convert each child of the centroid to star graphs hence i guess bamboo means chains and hedgehog means star graphs.
Bamboo makes sense for chains but how is hedgehog related to star graphs?

you can see any other user's code.

Let's suppose that we are following the approach of the editorial: we ask for the starting position plus 999 random points. Among all the answers to our queries, we get the greatest number less than or equal to x and we forward-iterate it 999 times.

For simplicity, fix n = 50000 and let's suppose that the answer is in a position such that it has at least 998 elements to its left (that is, there are at least 998 numbers less than the answer). We can see that if we have asked for at least one of the 998 numbers that are immediately previous to the answer or for the answer itself we are done, since we will iterate 999 times to the right and we will find the answer.

If we ask a question the probability of getting a number that is not the answer nor any of the 998 "good" numbers is . However, we are going to ask 1000 questions, and the probability that all of these 1000 questions are about "bad" numbers is 0.98002¹⁰⁰⁰ = 1.7 × 10^- 9, which is very small. The probability to answer correctly 200 tests is (1 - 1.7 × 10^- 9)²⁰⁰ ≈ 1, which is ultra-high. This probability can be even greater if you make sure that you never ask for the same point twice.

Finally, note two things: if the answer has less than 998 elements to its left then we will find it with probability 1 given that the first query is precisely the starting point. Also, the probability formula described above gives higher and higher probabilities as n becomes smaller, so you can be sure that this approach will work.

rand() is bounded by RAND_MAX which while it is guaranteed to be at least 32,767 on any standard library implementation, and a size of 2,147,483,647 or similar is relatively common it doesn't change the fact that the guaranteed maximum is 32,767 which is smaller than 50,000. If we were to place the solution in the ~17,000 where the random sampling would not reach, this would produce an WA.

Also, WA on tc 107 if you use random_shuffle once, and AC if you do it twice.

Centroid decomposition with FFT can be used to calculate count of each distance since maximum distance is n - 1 (cnt[i] is a number of pairs with distance between them equals to i). Then check .

You have to find all connected components in a graph, where edges are (original position in the array, position in sorted array). For example:

10

3 7 10 1 9 5 4 8 6 2

After sorting we have 1 2 3 4 5 6 7 8 9 10.

You have edges (4, 1), (1, 3), (3, 10), (10, 2), (2, 7), (7, 4); (5, 9), (9, 6), (6, 5); (8, 8). So we have 3 connected components, it's easy to see we can't have more than that. You can find the number of components using DFS.

Refer to my code for details 29740082

it is the same

Test 107 is a hack against random_shuffle, after adding a second random_shuffle right after the first one it gets AC.

Обозначим элементы как 1, 2, 3 и 4. Множества : (1), (2), (3), (4), (1, 2), (3, 4), (1, 3), (2, 4)

В функциях забыл ссылки(&). Вот исправленное решение: http://codeforces.net/contest/844/submission/29781100

Assume we have a subsequence containing the element in position i in the original sequence. Let j denote the position of this element in the sorted sequence. Then to sort the sequence this subsequence must also contain j since i has to be moved there. Now we repeat the reasoning for j and so on and we eventually get a cycle.

I think that there are graphs which cannot be changed into start. Degree of centroid in tree is unchangeable so if centroid don't have degree equal n-1 than we would never get a star.

I was wondering this problem too...Can someone give an answer please... If the tree has two centroids,if I change the edge between them,must the sum of squared distances between all pairs of vertices change to greater or it's not good enough...?(