Right? Like, across US, India, China, and Russia, any time is going to be bad for somebody. What's the point in complaining?

I wasn't complaining. I am just sad to miss the round by such good author & also this contest is after a long time from previous one. Neither I upvoted any comments who asked to shift the contest.

I wasn't aware "work" and "school" are specific countries, since that's going to be the main reason to skip this round for people in Europe, Africa and almost all of Asia. Then we have the Americas, where it's night. Ok, I guess it's a good time for New Zealand and Oceania.

This comment actually has more upvotes than the post itself.

If you cannot understand, it's IMO logo

Sorry, you are on the wrong platform. Switch to Codeforc.

Upd:- Comment edited.

Is this a joke?)

4:20 is much better

On seeing AC solutions, the idea is the answer should be a total of n terms.Also we know only a l can reduce a r or vice versa. So now we take max l (assuming max l is morethan max r) and it should reduce max r ,anything other is suboptimal. Now we have two people combined so we can solve the problem further similarly.

D was pretty neat. Basically, imagine everyone is at their own table originally. it is clear that the number of chairs used for a particular person i is max(l_i, r_i) + 1. Imagine if we put two people at the same table, and say their values are (a, b) and (c, d) respectively. Through some inspection, we can see that this is equivalent to two people (a, d) and (c, b) sitting at their own individual tables*. This implies that we can permute the r values for all the pairs. From there it should be clear that we can minimize the chairs by sorting both the l and r arrays individually and calculating the number of chairs needed if these new sorted people were all at their own individual tables.

*To be more precise here, combining (a, b) and (c, d) results in 2 + max(a, d) + max(b, c) chairs, and leaving them alone results in 2 + max(a, b) + max(c, d) chairs. So the former case is equivalent to having two people of values (a, d) and (b, c).

You can say that answer is where p_i is a person sitting next to i. Note that p_i might be arbitrary permutation. Turns out, the best way to choose this permutation is make it so that l_pi and r_i are sorted in the same way.

We iterate over every root and solve N problems independently. Let us call fixed root as r, and subtree of v as T_v.

DP[$v$][$k$]: Probability of survival of r, subject to the last contracted edge between r and v is contracted between k-th and k + 1-th contracted edge in T_v

We can calculate it by another DP. Total complexity seems O(N⁵), but like many tree DP, it is O(N⁴).

You don't get penalty if only your program is wrong on pretest1

1) sum(b[i],i=1..n) <= n * max(b[i]) ~~ 2000*2000 = 4*10^6 ,

2) let sb[z] — max( y2-y1+1), where sum(b[i], i = y1...y2) <= z. Precalc O(N^2)

3) answer = max( (x2-x1+1) * sb[X / sum(a[i],i=x1..x2) ] ), x1=1..n, x2=x1..n. O(N^2)

total complixity: O(N^2). with O(N^2) memory.

Is possible to solve C with binary search?

The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum.

Pre-calculate the minimum sum continuous subarray of array A of each size from 1 to N. For all those minimum sum subarray of size from 1 to N, find the largest subarray in B which satisfies the above condition. It can be done using two pointers. Code: 43769883

As JustAni pointed out: "The question can be converted into finding a subarray each from A and B such that product of sum of elements of those subarrays is less than or equal to x and the product of their size is maximum."

Now, for both arrays we can calculate in O(n^2) the minimum sum achievable for interval sizes i=1..n, i.e. for array "a" we can calculate "a_min" as a_min[i] = min( sum(a[l]..a[r]) where r-l+1 = i), and the same can be done for array "b".

Now simply try all possibilities, track the current maximum and try to update it to i*j when a_min[i] * b_min[j] <= x. The time complexity of this step is sufficient, as it takes O(n*m), and the previous step took O(n^2) + O(m^2).

I believe it is 13.

F

Could you please explain your solution?

I wasted 2 hours try to fit, from DP to Segment tree, through many other stuff, to C.

So how do you solve it?

If you have path between two nodes in tree (a, b) equal to len, after adding extra edges in the tree it will be . So, for even paths it will be same as , for odd paths it will be for 1 bigger, i.e (). So, final answer will be , where s is the sum of paths in the tree and o is the amount of odd paths in the tree.

I don't know what was the pretest, but after five WA at 9th pretest this is what I did and I passed it. "If you can take sum=10 with X ways then you can take every sum more than 10 with X ways as well. This means that you need to update your array like this arr[i] = max(arr[i], arr[i — 1])"

With whom? And how you got this info??

Maybe the time is good for Chinese?

It was because of the timing. The contest started at 15:00 in China during the National Day vacation, when almost everyone can participate with full energy.

The only thing is this round was held in the afternoon in UTC+8 and others were mostly at midnight.

I'll just post this good old meme here.

Because they accepted thousands of hard problems.

You are just a Specialist. YOU ARE NOT EVEN QUALIFIED TO JUDGE IT!

Any digit (except for the first one and any nines that may appear) in the number n can result either from simple addition (d₁ + d₂ = d_n) or addition with "carrying" (d₁ + d₂ = 10 + d_n. So one possible solution is to check all bitmasks from 00...00 to 11...11 where 0 denotes that a certain digit is produced by simple addition and 1 that it was produced by "carrying" with taking care to discard masks that have 1 in a position where there''s a 9 followed by a 0.

However, simply adding to seems to work.

For a,b what matters is the sum of digits (and not the number itself) and for max sum have as many 9's in a as possible.

So number of number that a can be 10 * (number of digits in n).

Permute through all a's such that a < n and b = n-a and the find max(S(a)+S(b)).

Link to my solution:43764388

Though there were easy number theories for this problem, don't know why the idea of digit dp hit my mind. My solution using digit dp was not very complex though. Just construct every number a less than n and store maximum s(a)+s(n-a) in the dp table.
My solution: 43766071

First sort l[] and r[]. Then iterate from reverse direction — if(l_i and r_i are of different person) then add max of them to answer because we can place them on adjacent places and left of one will be right of other. if(l_i & r_i are of same person) then form new group and add max of l_i and r_i to answer.

I have been refreshing this blog page since last two hours to check for Tutorial update. Don't tell me there will be no tutorial.

It seems that if you could not solve D quickly, then it would be really difficlt... I solved A to E except D :( For me, the algorithm for C is more familiar.

Not a formal proof but it's how I visualized it and maybe you can at least convince yourself:

Imagine at the start, every person's a bead with a LHS end and a RHS end, and that we're linking the people together, one link at a time, into chains (that eventually links its ends together into cycles). From now, we MUST perform exactly N links to join all the unpaired ends and minimize the cost.

Let's take the guy with the highest unpaired RHS or LHS cost. Let's say that it was a RHS cost that was larger than everything else, and let's call the cost V (if it was LHS it will be symmetrical). This person's RHS MUST be linked with somebody's LHS (maybe even his own). He can be linked with any available LHS, but who should he be linked with? Since V is >= any LHS cost, any linking is going to cost V anyway. So, you might as well pick the guy with the highest LHS cost, to "absorb" the biggest cost possible. It's the best choice, since if we picked a different LHS, the remaining links we must do would be EXACTLY the same except now one of the LHS elements is more costly, which is clearly less desirable. Now again consider the largest RHS or LHS cost of the remaining unpaired ends, and repeat the linking process.

If you visualize this, you will see multiple chains that start growing and joining, and sometimes the chains close into cycles when the RHS of a chain links with the LHS of itself.

Clearly, to implement this method, you will just iterate through the sorted lists of RHS and LHS costs one by one, linking them.

To think of it another way, the final result is a permutation, P(i) = j where the i'th person has the j'th person on the right hand side. Look at what happens when you start at a person and go left to right, following the permutation — the circles of the seating are the cycles of the permutation.

A few different solutions for problems E and H:

E: Each path of length d becomes a path of length . This means the total sum of paths is equal to (sum of all path lengths + # of paths of odd length) / 2.

Sum of all path lengths can be computed quickly by noting that each edge is crossed exactly size_left * size_right times, where size_left and size_right are the sizes of the two subtrees on either side of the edge. Number of paths of odd length can be computed similarly -- it's just n_odd * n_even where n_odd and n_even are the number of nodes with odd and even depth from the root, respectively.

H: Consider the polynomial (a₁ + a₂ + ... + a_D)^D. It contains the term D!a₁a₂...a_D as well as lots of other extraneous terms. Inclusion-exclusion on the D-th powers of each subset sum of a_i leaves just this D!a₁a₂...a_D term (since it's the only term that encompasses all D elements a_i). Now apply this idea with a₁ = x, a₂ = y, a₃ = a₄ = ... = a_D = 1 and you're done :)

Really interesting to see this strategy in H of obtaining x² from x. From looking at a few other contestants' solutions it looks like most people followed this route -- curious how you all thought of the idea!

How to proof that the coefficients of x^d, (x + 1)^d, ..., (x + d)^d are linearly independent under modulo p?

It's dead .

Where is it ? Has it been released ?

BSTs are usually asked in Interview questions rather than competitive programming.

I think Hackerrank here has a really good collection of BST questions.

Well I have waited the editorial for four whole days.