TL 12 107676717 -- unordered_map<int, int> cnt (TL = 2s)
TL 18 107676732 -- unordered_map<int, int> cnt(n) (works 46ms on 12th test)
OK 107676952 -- sort (works 77ms and 66ms on 12th and 18th tests)

What's going on?) I have no access to tests and can not repeat this effect locally (both windows:g++, linux:g++)

UPD:
107679200 rehash(100 + gen() % 10000) gives OK in 670 ms, which is still too slow
107679288 rehash(100 + gen() % 10000) + reserve gives OK in 100 ms, which is strange but acceptable.

PS:
This comment says "anti-hash test". I also have only this idea.
This comment gives more precise answer.
In future of course i will just use my own hash-table with no such faults.

PPS:

Both constructor(x) and rehash(x) seems to set bucket_count to minimal prime $$$\ge$$$ x, so we can still use unordered_map in one of two following ways:

mt19937 gen(time(NULL));
unordered_map<int, int> cnt;
cnt.rehash(n + gen() % n);

mt19937 gen(time(NULL));
unordered_map<int, int> cnt(n + gen() % n);

I'd like to know, how to launch dfs on java, to make it work pretty fast. $$$n = 2\,300\,000$$$.

Submit 54911336, says that on codeforces (windows, java32 1.8.0_162) time in dfs = 126ms.

Locally (windows, java64 11.0.1) i have time in dfs = 13913ms. The difference is 100 times!

Petr (windows, java 1.8.0_181) gets 15 seconds.

Command line options are java -XX:NewRatio=5 -Xms8M -Xmx512M -Xss64M. Taken from here.

How long it works for whom? (i'm interested in time, os/processor, java version, command line options)

How to reach 126ms locally?

UPD:
Locally if i add -XX:TieredStopAtLevel=1 (help) i get 387ms.
Command line options "exactly as on codeforces" locally on java64 give me the same time 13913ms $$$\pm\varepsilon$$$. So it's important to use java32.

Hello!

I'm sure, you heard about AVL trees.

Let consider node v of the tree. Let denote "big rotation" our behavior in case v.l.h ≥ v.r.h + 2 and v.l.r.h = v.l.l.h + 1. And denote "small rotation" our behavior in case v.l.h ≥ v.r.h + 2 and v.l.r.h = v.l.l.h - 1. Of course, big rotation is just two small rotations.

Let consider almost-AVL-tree, which in both cases does small rotation.

My question: is there any test-data, that almost-AVL-tree has height at least "height of correct-AVL-tree plus 3"? Or almost-AVL-tree always works correctly and never has height more than ? =)

Here you may find code in C++, where
function void add( node* &t, int x ); is correct insertion to AVL, and
function void add_slow( node* &t, int x ); does small rotation in both cases.

P.S. Neither by hands, nor using programming, I can obtain difference of heights more than two.

UPD: Somebody had troubles with downloading/reading the code, so not pastebin, short version

Hello everyone!

Today, 8-th of April, the third round of the VK Cup 2012 will take place. It's the last selection round. Let me remind you that the registration for this round is also required and it’s closed five minutes before the start.

It's rated round. It's allowed to participate out of competiotion. For all such participators it's also rated round. If you participate out of competition, you may play in the second division.

The problemset has been developed by various authors from VK, Codeforces and Saratov State University.

We worked hard to make problems more hard than usually but solvable in two hours. We hope, participation in the round will be interesting for you and only best of the best will pass to the Final Round.

This round will be run according to Codeforces rules: with room assignments, hacks and usual score decrease. It will be rated for you either if you participate in VK Cup or just solve it as a normal round.

Top 50 competitors will advance to the Final Round. VK Cup Final will occur in July in Saint-Petersburg.

Please, to make the round even more interesting for you, read the statements of ALL problems.

Good luck and try to win!

UPD1:

In Div. 2 Edition it will be used dynamic problem costs http://codeforces.me/blog/entry/4172. The problems will be ordered by increasing of expected difficulties, but their max scores will be determined according to the number of participants solved them.

** UPD: Formulas are already fixed. **

163A - Substring and Subsequence

Solution summary: dynamic programming.

Sample jury solution: 1415300 (author = levlam)

The problem could be solved with the following dynamic programming. Let f[i, j] be the number of distinct pairs ("substring starting at position i" and "subsequence of the substring t[j... |t|]")

Then:

f[i, j] = f[i, j + 1];
if (s[i] == t[j])
  add(f[i, j], f[i + 1, j + 1] + 1)

Answer = f[i,0]

163B - Lemmings

Solution summary: sorting + binary search.

Sample jury solution: 1415306 (author: Burunduk1)

We need to find the minimal time T. Let us find it using binary search.

Once the time is fixed, one can arrange lemmings using greedy approach starting either from the top or from the bottom. In this solution we consider the way to start from the bottom. Among all lemmings, that can get on the first ledge, let's choose the lemming with the minimal weight (and among all such lemmings the one with the minimal speed). Why is it correct? Assume that we used some heavier lemming, then we can't use any lighter lemming anywhere, so we could replace it. Among all lemmings with the minimal weight we choose the slowest, as the faster ones can climb higher.

To arrange lemmings fast, we can sort them beforehand, comparing first the weight and then the speed. After if, we consider all the lemmings in that order and either choose the current one, if it can get in time, or leave it. It is useless to consider one lemming twice, as we won't be able to use it anyway.

So, the solution consists of sorting and a binary search with a linear search inside. The time is .

However, that was not enough. One also had to deal with precision problems. Let us evaluate the number of binary search iterations.

0 ≤ T ≤ H * K (the maximal time does not exceed 10⁹). We need to understand how the times can differ. In the case of "N = K = 10⁵, H = 10⁴, V about 10⁹" the times needed for two lemmings to get on some ledges, can differ by 10^- 18, as the times are fractions like , where X and Y are about 10⁹.

So we need to make log₂10²⁷ = 90 iterations. In fact, jury solution made 75 and that was enough, however 70 was not. The idea above shows that 90 will be definitely enough.

163C - Conveyor

Solution summary: events along the circle or binary search.

Sample solution: 1415310 (author: Burunduk1)

Sample solution: 1415316 (author: arseny30)

Wherever Anton starts, he will run along the conveyor a segment of length . Consider one candy. To eat it, he needs to get on the conveyor in any moment of the segment [a_i - D..a_i]. Consider all points like a_i - D and a_i (add 2l if that is negative). Also add points 0 and 2l.

Sort these points. Consider two neighboring points: x[i] и x[i+1]. If Anton starts at any moment between them, he will eat the same amount of candies.

From now on, we can create one of the solving solutions:

1. Start from every middle of the segment M = (x[i]+x[i+1]) / 2 and use binary search to find the number of candies on the segment [M..M + D].

2. Consider events along a circle like (a[i] — D, +1) and (a[i], -1). One needs to move twice along the circle and use the second run to add the current length to the answer for the current number of candies.

The both solutions require time.

163D - Large Refrigerator

Solution summary: backtracking + boundaries evalutaion.

Sample solution: 1415320 (author: Burunduk1)

The solution consists of three main ideas:

1. V = ABC, A ≤ B ≤ C тогда A ≤ N^1 / 3, B ≤ (N / A)^1 / 2.

2. A and B are divisors of V, as we are already given the factorization of V, we can run only through the divisors

3. Given fixed A, the optimal real B and C are (N / A)^1 / 2 (denote this values as X). I.e. the square will always be greater than  ≥ 2(2AX + X²). So we can use this value as a boundary for the answer.

If that still was not enough, one could optimize using the following ideas:

1. Border evaluation will be more useful while running through possible values of A in descending order

2. A and B are 32-bit integers.

3. Once we have calculated the answer for V, memoize it (this one makes possible maximal test a bit smaller).

If anyone needs any theoretical base, here's some statistical information:

1. The maximal number of divisors of numbers from 1 through 10¹⁸ is 103860 (the number 897612484786617600 = 2⁸3⁴5²7²11 ...)

2. Using only first two optimizations, the number of numbers A, found by our solution, is 10 471 (in the case of the number with maximal number of divisors)

3. Using only first two optimizations, the number of pairs of A and B, found by our solution, is 128 264 (in the case of the number with maximal number of divisors)

163E - e-Government

Solution summary: Aho-Corasick and finding the sum along a way in a tree of suffix links

Sample solution: 1415345 (author: arseny30)

We assume that the reader is familiar with the Aho-Corasick algorithm (http://en.wikipedia.org/wiki/Aho-Corasick)

Consider a trie of names and suffix links over it. For every vertex v one can calculate the number of names, ending in that vertex (end[v]).

Then, the "add name i" operation is end[v[i]] += 1, where v[i] is ending vertex of i-th name.

Similarly, "remove name i": end[v[i]] -= 1.

To answer a request "calculate how politicized the text is", one needs to know, that the suffix links form a tree. Once we move though the text and simultaneously through the trie with suffix links, we add the sum of all end[v[i]] along the path to the root of the tree of suffix links the politicization of the text.

Now, there's another problem: we need to calculate the sum of weights along a way to the root, the weights may change.

One can do it in the following way:

1. Move the weights from vertices to corresponding edges to vertices' parents

2. Build the Eulerian traversal of the tree, where the down-move will store positive weight of the edge and up-move will store its negation.

3. The sum along a path to the root if the sum on a segment of the Eulerian traversal (the endpoints are any entries of the vertices in the traversal).

A fast and short way to calculate the sum on a segment is Fenwick's tree.

Here's a solution running in O(|SumLen| * log) time and 26 * |SumLen| memory (the trie will not be compressed).

Hello everyone!

It’s time for the second round of the VK Cup 2012. Let me remind you that the registration for this round is also required and it’s closed five minutes before the start.

The problemset has been developed by various authors from VK, Codeforces and Saratov State University. We worked hard to make this time interesting for competitors and to have the best ones in the next round.

This round will be run according to Codeforces rules: with room assignments, hacks and usual score decrease. It will be rated for you either if you participate in VK Cup or just solve it as a normal round.

Top 175 competitors will advance to the second round immediately. 25 more competitors will advance to the second round via the second unusual rules wildcard round on March 28. This round will consist of only one problem with inexact solution.

Please, to make the round even more interesting for you, read the statements of ALL problems.

Good luck and try to win!