Hacking also.

Educational Rounds are never rated.

So much against. So sad.

Yes.

Your'e asking this question while you replied Maybe. Ask Mike. !

This is a good opportunity to train your skills. And you have to train in order to get nice rating anyway. Here you still can compete with passion and without any risk to your rating. What else?

Our goal is to improve ourselves,

google it "goemetry median"!

All, you have to do it`s sort array and print middle element.

there are dots in a line the x are the dots you have to choose one of the dots and then, you should find the dot that as the smallest sum of distance to other dot example 4 1 2 3 4

if you choose 1st -> dis=1+2+3=6; else if you choose 2st -> dis=1+1+2=4; else if you choose 3rd -> dis=1+1+2=4; else if you choose 4th -> dis=1+2+3=6;

therefore, the ans is the left one, 2

For each point with coordinate x you calculate sum S of the distances to other points, namely S = sum{|x - x_i|}. Then choose the point with the smallest S.

The most straightforward solution is O(N^2) — N times you calculate the sum of N integers. You can improve complexity if you first sort all points by coordinate. Then if you move from point i to point i + 1, the difference between S_i+1 and S_i is (2*i - n) * |x_i+1 - x_i|. Then you can calculate all S_i in O(N).

I just did :P

http://www.codeforces.com/contest/710/submission/20066011

It`s simple dynamic programming. Create an array of positions,and then use this method to calculate next position.

dp[1]=x; dp[i] = min(dp[i — 1] + x, dp[(i + 1) / 2] + y + (i % 2) * x);

hacking is open...

Damn, I could google it!

Sample test case helped in finding pattern xD. And then it was easy to prove why the pattern works.

Can someone post any link to understand the pattern for C or explain it here. I still dont get how to generate it. Some people have implemented very nicely. like this and this

No, the answer doesn't require to be exist in the array, but you can prove that the minimum answer always exist in the array.

It doesn't follow from the task, but this can be proved.

if N is odd then there is only one answer and it is in the input.

if N is even there can be many answers but there have to be at least one of them in the input.

that's because the left most answer is always one of the given points

You mean F?

В чем ошибка?

Well, you can always look at mine's to feel smart :)

I think it can't be hacked. Because count1 will always equal to count2, so it doesn't matter whether they overflow or not. And the code will always output coords[N/2 — 1] if N is even, and that's the correct answer.

B* xD xD

You could also try out all the points and pick the best one.

http://mirror.codeforces.com/contest/710/submission/20051324

The sum on the main diagonal for n = 3 is 8 + 9 + 7 = 24 which is even.

My approach is SQRT decomposition. Lets have a constant B equal to about 2000.

If a query of 3rd type has length less than B we can simply check all substrings and get the answer. The complexity is , where L is the length of the text.

If a query of 3rd type has length greater than B we can make an O(N) or O(L) approach, because there are at most such queries. We can build a tree of the suffix links (if we use suffix automaton) or failure links (if we use Aho Corasick). The edges are of form "link[u] -> u". Then to for every such query we will build such a tree. Now for every string in the set D, we update its end state's subtree with 1. Now to get the answer to the current string, we go through all of its prefix states and query them (vertex query). So the problem becomes subtree update and vertex query. The whole query can be done in time.

The overall complexity is . We want to have almost the same complexity for the 2 types of queries of 3rd type. Thats why we pick B about 2000.

I solved the problem with a generalized suffix automaton during the contest but it can be easily replaced with an Aho Corasick. Link to submission: 20062687.

Another interesting way to solve it is to keep logM automata. When adding a string, you create an automaton of size 1, consisting of that string. While you have two automata of the same size, merge them, obtaining one of double the size. The merge can be done using the typical Aho Corasick build procedure. To handle the erase operation, we can keep another logM automata, composed of the erased strings. We will handle these the same way we did for the above. Therefore, the answer of a query will be query(all) - query(erased). This achieves a complexity of O(sum_lengths * logM). This idea was discussed here. 20053668 implements it, to some extent.

If you prefer not to use SAM or Aho Corasick, you can insert the strings of length < SQRT into a trie, and for each of the rest you build the KMP automaton. This method achieves O(sum_lengths * sqrt(M)). You can check out 20058436 for more details.