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.

I've already done it in C++ and got TLE.

I treat this problem as the shortest path problem. At first I got TLE when x is small and y is large, that's because the distances of the nodes are updated quite frequently. Then I set the initial distance of the i-th node as i*x, so the distances won't be updated too frequently. Then I got AC.

You can also see my submission for details 20059443

It can be solved with Dijkstra after a few observations.

• First of all, make a list of relevant states. N is relevant. Then, if x is relevant, x - 1 and x + 1 are relevant if x is odd, and x / 2 is relevant if x is even.
• If we're gonna do many add operations in a row, it makes sense to do it only before our first copy operation, otherwise we could just replace two of them for only one before the last copy operation. So we set D[i] = X * i for all relevant positions x.

Once we're done, we push all relevant states with their initial distances to the Dijkstra's queue and run it. It runs instantly. See here -> 20087826

Yes. But since we only need to output the position of the optimal point so it doesn't matter.

We can assume that b1 <= b2 (otherwise let's just swap(a1, a2) and swap(b1, b2))

Sequence 1: b1, b1+a1, b1+2*a1, b1+3*a1, ...

Sequence 2: b2, b2+a2, b2+2*a2, b2+3*a2, ...

1) Let's find minimum K>=0 such that b2+K*a2 belongs to the sequence 1.

b2+K*a2-b1 must be divisible by a1. It's enough since b2+K*a2-b1 >= 0.

K*a2 = b1-b2 (modulo a1)

Let's denote GCD(a1,a2) = a_gcd

1.1) If (b1 — b2) is not divisible by a_gcd, there is no solution to this. The sequences do not have any common numbers, thus the answer to the problem is 0.

1.2) If (b1 — b2) is divisible by a_gcd:

K*(a2/a_gcd) = (b1-b2)/a_gcd (modulo a1/a_gcd)

We can use any algorithm to find "modular multiplicative inverse": https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

2) The first common element of Sequence 1 and Sequence 2 is A = b2+K*a2

Next elements will be A+LCM(a1,a2), A+2*LCM(a1,a2), ...

If you know A and LCM(a1,a2), it's easy to find how many of these numbers belong to interval [L, R]

I solve it with 2 brute force solutions.

0) if a1 < a2 swap a1/a2 and b1/b2

Brute force #1: a1 > 1000 iterate first sequence and check if point in second.

Brute force #2 a1 <= 1000, if b1 < b2, required increase b1 to be >= b2 Scan b1, b1+1, b1+2*a1, ... b1+1000*a1 to find a first common point, if not exists answer will be 0 As we know first common point and also need know a step it will be lcm(a1,a2) Now we have one progression and need know count of points in interval [l,r] it possible done in O(1).

That's all.

Validator was fixed. Tests 84 and 126 were removed. Solutions that failed on 84th test were rejudged and got Accepted. There were no solutions failed on test 126.

Sorry for the late translation. It's ready now.

Yeah my friend I agree with you .., eagerly waiting for education Round 17