But sadly it was stated that K <= N. That was really tricky. What a sad story!

The time is rarely suitable for coders in China. :) PS. The College Entrance Examination will start tomorrow morning. Good luck! God bless us!

I think the idea of converting the problem used in solution 2 to Div1.C is great because it avoids the waste of height decreased. I would like to share my thoughts on why it can be converted to such a new problem.

We just need to consider the case where there is only one bamboo. Consider any scheme in the original problem. When you waste for the first time, which corresponds to a segment intersecting with the horizontal line y = 0, you can just move the footprints in the past upwards to make them all above or on y = 0. Notice that this guarantees that all the footprints are not below y = 0, and you move footprints only upwards. Besides, it is obvious that when you are about to make the (i + 1)st footprint, it is sure that the i-th footprint is at the correct position. That suggests the final point, which is required to be below y = k, is finally at its correct position in spite of the moving operation. So we can see that every scheme in the original problem corresponds to a scheme in the new problem.

Now consider a scheme in the new problem. If the position of the first footprint is (0, x), then x ≥ h must be satisfied. Let d = x - h. Then try to move the footprints downwards by d. When they have moved by d' < d, and there are footprints on y = 0, just find the leftmost one, say chronologically the i-th, and iteratively try to lower the footprints from 0 to i — 1 by d - d'. Finally we can see the first footprint becomes (0, h), and the last footprint is still not above y = k. Thus every scheme in the new problem corresponds to a scheme in the original problem.

Then we know the two problems are equivalent.

It should be noticed that this editorial has so far been really detailedly written. So no wonder we have to wait for long to see the complete version.

The contest is prepared by Chinese but I really don't think it is prepared for Chinese because it will start at 1:00 am UTC+8.

Could somebody please tell me what 'the left part' and 'the right part' respectively mean in Div1.D? I feel it hard to understand. Thanks in advance.

I think that g(x) should be instead of in div1.C, or it will not satisfy

But there can be two different X(x)s which satisfy X(x)² = S(x). So which one does refer to? In the editorial above refers to the one starting with 1, so does it mean that should always contain a non-negative constant?

Thanks to the explanations, I have understood this algorithm. Actually there can be two different square roots but only one of them could keep the inverse exist. By the way, I do not know clearly the defination of the notation for a formal power series S(x), but I guess it should be unique. Can someone please answer this question? How is it defined?

I am sorry that I still don't understand. Could you please give a more detailed explanation? Thank you!

Could someone please tell me why the equation F(z) = C(z)F(z)² + 1 in 438E has only one solution?

I think that there is a mistake in the solution described above to Div1 E. In my opinion, the value of p should be

Look at the figures below to see why.

The two types of situations will simultaneously lead two triangles to be illegal .

And the two situations below will only lead one triangle to be illegal.

So the coefficients should be 2 2 1 1 instead of 1 1 1 1.

I think it is just a careless mistake made by the author.

Should I call the process of analyzing the complexity in 438D potential analysis?

That solution is easy to understand. Thank you!