suppose the best gift ever will be the invitation from a good company)))

You better create a blog post to invite to your channel instead of irrelevant comment here.

I just visited your channel. You should have mentioned that your videos are in Arabic language.

It always is, unless stated otherwise.

If you will get any help. Please share with me!

Participating in a programming contest is better than watching a 'fixed match'. I think.

Reloading the page is helpful

And me.

I have just installed a plug-in that has to be an alternative of adobe flash player, but no response.

Why it's not as the Educational rounds? I'm talking about the way of displaying the source code for hacking.

Please MikeMirzayanov, do something for this.

I used to face this problem on Google Chrome. Now I use Firefox for hacking, works all the time!

I stored an array of shifts for each level. When type 1 query comes, increase the shift for that level by K. When type 2 query comes, increase the shift for that level by K, and also the shift for the level after by 2k, and after that 4k... to the end of the array (which will be size 63 or something to get max number of elements). When type 3 query comes, find where that node is and go up by dividing by 2. Then you just need to subtract the shifts on each level as you go up. Sample: http://mirror.codeforces.com/contest/960/submission/37077181

If instead of keeping ai and bi, we keep ci= | ai — bi|, then our task is to use k1+k2 operations to reduce the cost. So you'll go through the array, find the maximum and decrease the value by 1. If all the elements are 0 it means that you are in an optimal point and the way to go from here is to add 1 and then decrease 1 to the same position up until you don't have any operations left.

Make a priority queue of the biggest differences between a and b. You can use the greedy approach then : just reduce 1 from the biggest difference that exist (i.e. remove biggest element from pq, reduce it by 1, and add the reduced number to the priority queue)

If the priority queue becomes empty while you still have attempts, the minimum result will just be number of remaining attempts modulo 2.

If you keep a sequence that is all 1's (ie 1 1 1 1 .. 1) the cost is 2^(no of 1's)-1. So you're going to find the largest k so that x>= 2^k -1 and then decrease x by 2^k -1 and add k equal values to your solution. You just have to be careful because the last k values should be larger than the others by at least D.

1000000000 1 is possible

268435356 1

1000000000 1

Centroid Decomposition

Yep. Just one improvised DFS will do the trick, and I would have done it, if not for the electricity going off...

the sequence of length n contains 2^n-1 sequences. Hence, the number X can be decomposed into powers of two minus 1. The degrees of the twos in this decomposition are the lengths of the sequences to be used. The degrees of the twos in this decomposition are the lengths of the sequences to be used. Collect on parts. The final sequence will look like:

1,1,1,....,1+(d+1),1+(d+1),....,1+(2*d+1),1+(2*d+1),...where the number of identical terms is equal to the powers of the twos to which we decomposed X.

If the number X cannot be completely decomposed into (2^i-1), then at the end of the answer it is necessary to add Another f distinct numbers, each of which will increase from the previous one by d+1.

Do not forget to take into account that the length of the answer should not exceed 10000

Consider case

2 100000

1 2 1

2 1 2

1 2 3

and so on. The simple dfs checks 50000 edges 50000 times, making it .

Surely it is better to put hard cases in the pretests than real tests... would you rather fail and not be able to fix it??

Holy shit, I added 2 * sum of the values to the answer. RIP good place

I found some pattern. Which included Pascal triangle and Stirling number of the first kind. I generated the required Stirling number with FFT but got WA :/ I think I should have used NTT or maybe there's a lot simpler solution or something.

I am very thankful that this did not change my rank! :P

I think it is large numbers or something, I got a run time error that I fixed by increasing the size of my array :P

There is a work around to do FFT under large Modulo. But in this problem it might be risky, as it is time consuming. The idea is -
Lets take C = 30000. Now partition each number A(x) as Ca_1i + a_2i, and B(x) as C_b1i + b_2i. Then convolute P = a₁ × b₁, Q = a₁ × b₂, R = a₂ × b₁, S = a₂ × b₂.
You can get the final result as (A × B)_i ≡ C²p_i + C(q_i + r_i) + s_i (mod M). It works because no number while doing fft corsses NC² and fits into precision. But you can't do fft directly into the main polynomial, then a number can be atmost NM², and that will overflow.

If you make a new graph so that the edges are the nodes and the nodes are the edges, you'll have exactly the same problem but you'll have to find the longest path of increasing nodes. This is done by going through the nodes in the order of their values and updating a dp[node]=longest increasing sequence ending in node.

It seems like dp and maintaining array of sets(couldn't implement it in time though).

Let's loop over the edges in reversed order and assume that the current edge will be the beginning of the path. This way we kinda eliminate the condition about indices being increasing and only have to worry about weights.

Define f(node)(w) as the maximum length of a path if we start at node with an edge of weight w. Let's say the current edge goes from A to B and has weight C. Now we have to update the value of f(A)(B) with the maximum value of f(B)(i) + 1 for i > C. Obviously keeping f(node) in the form of a segment tree, in which the indices are the weights of outgoing edges from node, does the job.

That's not how you read the arrays :P

ans should be long long imo

I don't understand that. "At least one 'a' and one 'b' exist" mean that there must at least one 'A' or one 'B' in the string. Then why not handling the case when there's no 'a' or 'b' will fail?

Did you use FFT or NTT? If FFT, then how did you handle the mod?

Can you explaine please, what is the complexity of your F and how it fit in time?

37057703

Because, I can see you use Divide&Concuer, but at each step use have sort()

And you should have: T(n) = 2*T(n/2) + O(nlogn)

Haha, I worked out the formula with one (1) Stirling number using the generating function of Stirling numbers (u generates A or B, z generates N).

We want to compute the convolution of sequences \sum_n \left[n, K\right] / n!

Unable to parse markup [type=CF_TEX]

Since , f_K is the K-th coefficient of the Taylor series of g with respect to u. We can get it as

Hey, the product $f_{A-1}(x) f_{B-1}(x)$ is proportional to f_{A + B - 2}(x)... and we can extract the N - 1-th coefficient by differentiating again:

Alternatively, we can use the definition of f_{A + B - 2} to write it as

There is nothing wrong with the code. The idea is just wrong. The right solution is to minimize the max difference, but you just use all your moves to completely remove a difference or two.

Instead, find the max difference, remove or add 1 to it, repeat... Sometimes you'll need to add because you must use all the moves.

since x is int, x*x can overflow. It should 1ll*x*x.

1 0 0
1000000
0

Maybe when sum of all vi's is not zero. So that you will have to consider zero length paths.. not sure though

they intentionally put the sum of vi = 0 in the first 17 cases so that if you are counting A(u,u) 2 times your code passes pretests but fails system testing...

Nice I had written ans=0 and then added numbers in vertexes earlier in the code, very good descent CF one love

What's wrong with it?

The same here. Realized it during the contest and resubmitted. Facepalm

Get your code Accepted then, sir.

I think the major issue is in CF server, which runs in 32bit environment (Thus being very slow on 64bit integer operations)

Your NTT code is slow. Example, when multipling two small polynomials, you still need a inversion function. O(NlogN) may be found at here: https://discuss.codechef.com/problems/CHEFKNN.

And this submit in last 5 sec of contest threw me out of top 15 =(

You misinterpreted the question. It means that the string has to have at least one a and b to be valid.

In such a test case, you're suppossed to output NO.

You can't print a variable of data type size using printf and %lld, you should cast it to long long first or use cout

With printf you need to be very careful about types. If you give the function a parameter of the wrong type, it will print garbage.

And here is the problem. The size of the type of v.size() is not standardized. It doesn't have to be a 64 bit integer (although g++ will usually use 64 bit). However Codeforces uses a g++ compiler where v.size() is only 32 bit.

Solutions: cast the variable to a long long, or simply use cout << v.size() << '\n'; :-P

true, the tests were weak, i dont get why they didnt reevaluate the solutions