Are Um_nik and Huyum_nik step brothers?

We can see here that default container for stack is deque. The same for queue. So stack and queue are actually deque and probably that's the reason why they're not faster

That's why they're "almost retired". It's the last year when then they can take part in ICPC I guess.

I think that is not what I need :D

Thank you anyway!

Thank you for keeping us informed!

What is ncr?

How to solve problem COUNTIT? The problem was to calculate number of certain sequences

I'm sure every heathy person won't solve this problem using Ferrari's formula

$$$a + b ^ 2 = n$$$, so $$$a = n - b ^ 2$$$, so $$$a ^ 2 + b = (n - b ^ 2) ^ 2 + b = b ^ 4 - 2 * n * b ^ 2 + n ^ 2 + b = m$$$.

The last equation can be solved in $$$O(1)$$$. If you don't like math, don't open this link

And it seem like Mike supports him

Can we see the closing ceremony at least?

If you use lazy propagation you should clone children before pushing.

Try to follow the rule not to change any values :D

The easiest way to do this is to move to Iran. 1$ equals 42105 Iranian rials.

I know one way but it needs much time :D

As you may know, some time ago you was a master if your rating was higher than 2200 (perhaps 2300). So probably you can wait until for being master it is enough to have about 1600

I think, I know who'll beat tourist one day :D

In this problem distance between two sells is equal to Euclidean distance ( +  smth). not Manhattan distance. So usual BFS does not work

At first, let's notice that it isn't worth taking 3 times or more [x, x + 1, x + 2], we can take [x, x, x], [x + 1, x + 1, x + 1], [x + 2, x + 2, x + 2] instead.

Now let's compute how many times number x is present for any valid x. Denote the value by cnt[x].

Now let's calculate dp[i][j][k] (in this dp we consider all numbers from the given array that are less than i - 1, cnt[i - 1]  -  k (k is up to 3) numbers which are equals to i  -  1 and j numbers which are equal to i (j is up to cnt[i]), dp[i][j][k] is the answer for these numbers)

How to calculate it? As we know, there is no point in taking 3 times [x, x + 1, x + 2], so dp[i][j][k] = max(dp[i - 1][cnt[i] - l][l] + (j - l) / 3), l < 3. That's because we can take [i - 2, i - 1, i] 0, 1 or 2 times. If we take it l times, than we have (j - l) numbers that are equals to i and we have to divide them into groups of the type [i, i, i]. Also we have to divide the other numbers, but we know that the answer, it is dp[i — 1][cnt[i] — l][l]

Hope, my answer will help you. Ask me if you have any questions :D

I didn't get, why if n is odd and m is even the second player wins. For example, if n = 3 and m = 4 then the first player can put X in cell (2, 2) (we suppose lines are numbered from 1 to 3 and columns from 1 to 4). Then the second player has to put in cell (2, 3), doesn't he? If he does, so the first player will win

Clashes with Educational 59

Represent the number X as sequence of zeroes and ones. Denote by a₁ ... a_m the representation. Let's think that we know X1 + X2 and we want to recover X1. We know that if a_i is equal 0 than the i-th bits of X1 and X2 are equal and we know the value. If a_i is equal 1 we don't know the i-th bit of X1.

Let's recover bits one by one. We've already recovered the first i - 1 bits and also we recovered the j-th bit if a_j is 0. So we want to understand how to recover the i-th bit. If a_i is 0 we know the answer, otherwise we want to try to put the i-th bit equal 0. How to check if we can do it? Let's represent our given numbers as vectors v₁ ... v_k. The length of the vectors is equal to number of known bits, i.e if X1  =  010??1? then we just skip unknown bits and length of the vectors is 7 - 3 = 4. So we want to know whether there exits such numbers alpha₁ ... alpha_k such that v₁  *  alpha_k  +  ... = X1' (X1' is X1 with skipped bits) or not. It can be checked with Gaussian algorithm. We want to find the solution of AX = B, where X = alpha, a_ij = v_ji, b_i = x_i

Hope, my comment will help help. Feel free to ask any questions :D

Do you know why almost everyone thanks Mike for the polygon platform? :) The reason is they prepared contests on it.

There're some blogs on Codeforces which can help you understand how to use validators, checkers

You can also stress your solution on polygon to check if it's correct

Let me guess, Radewoosh is still enjoying the New Year, so he hasn't uploaded the editorial yet

If we rearrange our vertexes in topological order then every edge will be directed from left to right. Some edges before removal were directed from left to right, we won't change their direction, but if an edge was directed from right to left we'll change its direction.

We know that there are no cycles, so we can find a topological ordering. After that we can direct our edges, which were removed, the right way

Let's solve it with a binary search. We want to check that the answer is at least k. Let's remove all edges with weight less than k (we can choose any direction on this edges). Notice that if our graph contains any cycles then the answer is more than k, otherwise the answer isn't greater than k.

Yes, you're right, I get it.

Thank you very much!

But exactly this code outputs  - 1

Some of them check it.

example

What is hack for B?

I can't understand why some greedy solutions get WA. All solutions a kind of let's find the first "[" and the first ": ". Afterwards let's find the last "]" and the last ": " before the last "]". And finally let's calculate number of "|" between ": ". The answer is the number of "|" + 4

*Top 4

Cool! I've been waiting for the editorial for a long lime!

Thank you very much!

vintage_Vlad_Makeev (he is also well known as vintage_Vlad_Makeev) wasn't so good in 2018: 2723 -> 1690

If I want to find square root of number a and abs(x - sqrt(a)) = O(eps) then abs(y - sqrt(a)) = O(eps²) where y = (x + a / x) / 2. The number of correct digits is multiplied by 2, so you need to do O(logn) steps to find the answer.

If you use binary search you need to do O(n) steps

Although my submission status is updated I press F5 every second or more often)

What doesn't kill us makes us stronger!

Let's solve another problem: you are given an array, for each pair of indexes you compute a[j] ^ a[i] and you need to find the k-th element among computed values. You can find the solution here, problem F.

How, how to solve our problem? Let's compute auxiliary array b. b[j] = a[0] ^ a[1] ^ ... ^ a[j]. Notice that now we need to solve previous problem

Let's find answer for all n <= 10 ^ 7 = M, it can be done with simple dp. Then how to solve it for n > M? As we know ans[n] = min(ans[n / 2], ans[n / 3], ans[n — 1]) Well, let's run recursion, if n <= M: return dp[n]; else: we use our formula

But is still does not work fast, because we will find answer for n, n — 1, n — 2, ... M + 1. Notice that there is no point in decreasing n by 1 3 or more times because instead n -> n — 1 -> n — 2 -> (n — 2) / 2 we do n -> n / 2 -> n / 2 — 1, case when we divide n by 3 after several decreasing by 1 is the similar

Now let's run our recursion again, but in recursion we will check that we don't substract 1 3 or more times. And this solution should works fast

Are you sure? If a lot of new users take part in round then, probably, everyone will increase his rating

can you write a link on this ploblem, please

I think that it can be solved using divide and conguer. The complexity will be O(nlogn)

Maybe Aho-corasick

Jubilee for codeforces, the first for me)

Good luck :D