### 437A - The Child and Homework

We enumerate each choice *i*, and then enumerate another choice *j* (*j* ≠ *i*), let *cnt* = 0 at first, if choice *j* is twice longer than *i* let *cnt* = *cnt* + 1, if choice *j* is twice shorter than *i* let *cnt* = *cnt* - 1. So *i* is great if and only if *cnt* = 3 or *cnt* = - 3.

If there is exactly one great choice, output it, otherwise output C.

### 437B - The Child and Set

We could deal with this by digits.

Because *lowbit*(*x*) is taking out the lowest 1 of the number *x*, we can enumerate the number of the lowest zero.

Then, if we enumerate *x* as the number of zero, we enumerate *a* as well, which *a* × 2^{x} is no more than *limit* and *a* is odd. We can find out that *lowbit*(*a* × 2^{x}) = 2^{x}.

In this order, we would find out that the *lowbit*() we are considering is monotonically decresing.

Because for every two number *x*, *y*, *lowbit*(*x*) is a divisor of *lowbit*(*y*) or *lowbit*(*y*) is a divisor of *lowbit*(*x*).

We can solve it by greedy. When we enumerate *x* by descending order, we check whether 2^{x} is no more than *sum*, and check whether there is such *a*. We minus 2^{x} from *sum* if *x* and *a* exist.

If at last *sum* is not equal to 0, then it must be an impossible test.

Why? Because if we don't choose a number whose *lowbit* = 2^{x}, then we shouldn't choose two numbers whose *lowbit* = 2^{x - 1}. (Otherwise we can replace these two numbers with one number)

If we choose one number whose *lowbit* = 2^{x - 1}, then we can choose at most one number whose *lowbit* = 2^{x - 2}, at most one number whose *lowbit* = 2^{x - 3} and so on. So the total sum of them is less than 2^{x} and we can't merge them into *sum*.

If we don't choose one number whose *lowbit* = 2^{x - 1}, then it's just the same as we don't choose one number whose *lowbit* = 2^{x}.

So the total time complexity is *O*(*limit*).

### 437C - The Child and Toy

The best way to delete all n nodes is deleting them in decreasing order of their value.

Proof:

Consider each edge (*x*, *y*), it will contribute to the total cost *v*_{x} or *v*_{y} when it is deleted.

If we delete the vertices in decreasing order, then it will contribute only *min*(*v*_{x}, *v*_{y}), so the total costs is the lowest.

### 437D - The Child and Zoo

First, there is nothing in the graph. We sort all the areas of the original graph by their animal numbers in decreasing order, and then add them one by one.

When we add area *i*, we add all the roads (*i*, *j*), where *j* is some area that has been added.

After doing so, we have merged some connected components. If *p* and *q* are two areas in different connected components we have merged just then, *f*(*p*, *q*) must equals the *v*_{i}, because they are not connected until we add node *i*.

So we use Union-Find Set to do such procedure, and maintain the size of each connected component, then we can calculate the answer easily.

### 437E - The Child and Polygon

In this problem, you are asked to count the triangulations of a simple polygon.

First we label the vertex of polygon from 0 to *n* - 1.

Then we let *f*[*i*][*j*] be the number of triangulations from vertex *i* to vertex *j*. (Suppose there is no other vertices and there is an edge between *i* and *j*)

If the line segment (*i*, *j*) cross with the original polygon or is outside the polygon, *f*[*i*][*j*] is just 0. We can check it in *O*(*n*) time.

Otherwise, we have , which means we split the polygon into the triangulation from vertex *i* to vertex *k*, a triangle (*i*, *k*, *j*) and the triangulation from vertex *k* to vertex *j*. We can sum these terms in *O*(*n*) time.

Finally,the answer is *f*[0][*n* - 1]. It's obvious that we didn't miss some triangulation. And we use a triangle to split the polygon each time, so if the triangle is different then the triangulation must be different, too. So we didn't count some triangulation more than once.

So the total time complexity is *O*(*n*^{3}), which is sufficient for this problem.

### 438D - The Child and Sequence

The important idea of this problem is the property of .

Let .

So, .

If *k* = 0, remains to be *x*.

If *k* ≠ 0, .

We realize every time a change happening on *x*, *x* will be reduced by at least a half.

So let the energy of *x* become . Every time when we modify *x*, it may take at least 1 energy.

The initial energy of the sequence is .

We use a segment tree to support the query to the maximum among an interval. When we need to deal with the operation 2, we modify the maximum of the segment until it is less than *x*.

Now let's face with the operation 3.

Every time we modify an element on the segment tree, we'll charge a element with power.

So the total time complexity is : .

By the way, we can extend the operation 3 to assign all the elements in the interval to the same number in the same time complexity. This is an interesting idea also, but a bit harder. You can think of it.

### 438E - The Child and Binary Tree

Let *f*[*s*] be the number of good vertex-weighted rooted binary trees whose weight exactly equal to *s*, then we have:

*f*[0] = 1

Let F(z) be the generating function of f. That is,

And then let

So we have:

*F*(*z*) = *C*(*z*)*F*(*z*)^{2} + 1

`` + 1'' is for *f*[0] = 1.

Solve this equation we have:

So the remaining question is: how to calculate the multiplication inverse of a power series and the square root of a power series?

There is an interesting algorithm which calculate the inverse of a power series *F*(*z*):

We use *f*(*z*) ≡ *g*(*z*) (*mod* *z*^{n}) to denote that the first *n* terms of *f*(*z*) and *g*(*z*) are the same.

We can simply calculate a formal power series *R*_{1}(*z*) which satisfies *R*_{1}(*z*)*F*(*z*) ≡ 1 (*mod* *z*^{1})

Next, if we have *R*_{n}(*z*) which satisfies *R*_{n}(*z*)*F*(*z*) ≡ 1 (*mod* *z*^{n}), we will get:

(*R*_{n}(*z*)*F*(*z*) - 1)^{2} ≡ 0 (*mod* *z*^{2n})

*R*_{n}(*z*)^{2}*F*(*z*)^{2} - 2*R*_{n}(*z*)*F*(*z*) + 1 ≡ 0 (*mod* *z*^{2n})

1 ≡ 2*R*_{n}(*z*)*F*(*z*) - *R*_{n}(*z*)^{2}*F*(*z*)^{2} (*mod* *z*^{2n})

*R*_{2n}(*z*) ≡ 2*R*_{n}(*z*) - *R*_{n}(*z*)^{2}*F*(*z*) (*mod* *z*^{2n})

We can simplely use Fast Fourier Transform to deal with multiplication. Note the unusual mod 998244353 (7 × 17 × 2^{23} + 1), thus we can use Number Theoretic Transform.

By doubling *n* repeatedly, we can get the first *n* terms of the inverse of *F*(*z*) in time. It's because that

We can just use the idea of this algorithm to calculate the square root of a power series *F*(*z*):

We can simply calculate a power series *S*_{1}(*z*) which satisfies *S*_{1}(*z*)^{2} ≡ *F*(*z*) (*mod* *z*^{2n})

Next, if we have *S*_{n}(*z*) which satisfies *S*_{n}(*z*)^{2} ≡ *F*(*z*) (*mod* *z*^{n}), we will get:

(*S*_{n}(*z*)^{2} - *F*(*z*))^{2} ≡ 0 (*mod* *z*^{2n})

*S*_{n}(*z*)^{4} - 2*S*_{n}(*z*)^{2}*F*(*z*) + *F*(*z*)^{2} ≡ 0 (*mod* *z*^{2n})

*S*_{n}(*z*)^{2} - 2*F*(*z*) + *F*(*z*)^{2}*S*_{n}(*z*)^{ - 2} ≡ 0 (*mod* *z*^{2n})

4*F*(*z*) ≡ *S*_{n}(*z*)^{2} + 2*F*(*z*) + *F*(*z*)^{2}*S*_{n}(*z*)^{ - 2} (*mod* *z*^{2n})

4*F*(*z*) ≡ (*S*_{n}(*z*) + *F*(*z*)*S*_{n}(*z*)^{ - 1})^{2} (*mod* *z*^{2n})

So,

By doubling *n* repeatedly, we can get the first *n* terms of the square root of *F*(*z*) in time.

That's all. What I want to share with others is this beautiful doubling algorithm.

So the total time complexity of the solution to the original problem is .

There is an algorithm solving this problem using divide and conquer and Fast Fourier Transform, which runs in . See the C++ code and the Java code for details.

Can someone please explain the solution for 437C —

The Child and Toy. In the question it's given that the child can remove one part at a time. Does that mean he can remove one vertex at a time? If yes, then how is it equal to removing the edges as given in the solution of the editorial?if you remove a vertex you will break all connections with this vertex, and the cost as given will be sum of costs of all vertices connected to the removed vertex.

If you remove all the edges connected to a vertex at one time, then answer for the first test case will be 50 not 40. 40 will be the answer when the edges are removed one at a time. But in the question it is given that vertices are to be removed one at a time.

I too have the same doubt...can someone please explain!

why is it 50?

Remove an edge implies removing the vertices connected to it.

In the first test case

u_{23}with costv_{2}u_{12}with costv_{1}u_{14}with costv_{1}total

v_{2}+v_{1}+v_{1}= 20 + 10 + 10 = 40then you didn't choose the right order of verticesز

in the first case, you can remove the first vertex, and this will break its connection with the second and the fourth vertex, and the cost will be 60, instead you can remove vertex 4 and 2 and break there connection with vertex 1 and the cost will be 10 + 10 = 20 and since you removed vertex 2 this will also break the connection with vertex 3 and then the total cost will be 50, but this is also not the ideal solution.

First, remove part 3, cost of the action is 20. Then, remove part 2, cost of the action is 10. Next, remove part 4, cost of the action is 10. At last, remove part 1, cost of the action is 0.

The doubling algorithm is

trulybeautiful! I know that these equations aren't very encouraging, but after understanding the trick I realised 438E is awesome! :PThanks for the task (and all the other ones, too)!

I think for this problem 437A - The Child and Homework , it's a good idea to save the lengthes of the four inputs in an array and then sort the array . And check if the conditions are true for a[3] or a[0] ....

my solutions executed faster then solutions of people who used sorting of array matter. Although I used 1 extra unnecessary loop.

Can somebody please explain

437B The Child and Set: why that greedy solution (in a decreasing order) works? I could not understand the editorial due to poor english and presentation (didnt expect this from codeforces tutorials ).What is 'a' here ? What is this -> Because for every two number x, y, that lowbit(x) | lowbit, 2014 - 06 - 01(y) or lowbit(y) | lowbit, 2014 - 06 - 01(x).

Also, if we don't choose a number whose lowbit = 2^x, then we shouldn't choose two numbers whose lowbit = 2^x - 1 but we can choose four such numbers....so what is he trying to say ?

Please somebody explain in detail...this bit thing always eludes me

I can't understand the explanation either

During the contest I thought of creating an array of size

`limit`

. Then`array[i-1]`

will store the number`2^k`

where`k`

is the index of the first`1`

bit (from right to left) of number`i`

.Then the problem basically asks to find a subset of the values stored in this array, whose total summation is equal to

`sum`

. However I couldn't figure out how to solve this part efficiently.A simpler explanation of the solution to this problem would be appreciated.

It's similar to the Coin Change problem but with (possibly) many denominations.

Since the low bit of an odd number is always 1 we have

`ceil(limit / 2)`

coins with value 1.We know that every number can be obtained as a sum of 1's. Let's denote the number of coins with value 1 as

ones.If

`sum <= ones`

then problem solved, use as many 1's as needed.Else try to decrease

`sum`

as much as possible using coins with value greater than 1. If we can make`sum <= ones`

then problem solved (1).Unlike the Coin Change problem we don't need to minimize the number of coins, so the best way to decrease

`sum`

is to start with the biggest denominations.Maybe not the best analogy but it can help :).

Good idea, I didn't figure this out in the contest. I will try your idea soon. Thx

That is a very good explanation indeed, rendon. thank you very much.... now understood it very nicely. If u cant make the sum to be zero even after subtracting all the possible lowbit values (which consists of lot of ones) in a decreasing order, that means it is impossible to get the requires sum ... perfect..... :)

perhaps i thought like this

@rendon But coin greedy doesn't work for coin change, not getting how is that working here.

in coin change we have to minimise the number of coins but here we don"t have to minimise so greedy works here.

@chypsd

A variation of coin change, say you have to just check whether you can you can form a change of given amount using the provided coins or not. Here you don't care about minimising the coins.

Greed doesn't work with this as well.

My fault...I possibly had written some escape character by mistake T_T...

If there are two numbers whose

lowbit= 2^{x - 1}we chose and we have a number whoselowbit= 2^{x}, then we can replace that two numbers with a single number whoselowbit= 2^{x}, remaining the sum unchanged. So we should choose at most one number whoselowbit= 2^{x - 1}.Can someone please tell me why in "Child and the Zoo" we sort them in increasing way? For me it is the decreasing way that works: when we add new area that has smaller number than areas that it connects then it creates the biggest minimum on the road that has just been created. And that is what we are looking for, isn't it?

You're absolutely right. It's not easy to make a flawless editorial. :)

Yes , I solved it sorting in decreasing way.

It's my fault...sad...Sorry...T_T...

I have corrected it.

Couldn't understand 437E. What's the final solution? F[0][n-1]? If so, is there a proof that you won't count a triangulation twice when choosing K? I tried to come up with some sort of divide and conquer technique similar to this, but couldn't come up with anything that would prevent the overlapping solutions to be counted twice..

Yes, it's just

f[0][n- 1].Once we choose

k, we also choose a triangle. So for differentk, the triangulations are different.Ahh, got it now! At least I was somewhat close to the correct approach, lol.

Just a minor feedback: when you say "...which means we split the polygon into the triangulation from vertex i to vertex j, a triangle (i, j, k) and the triangulation from vertex j to vertex k."

Shouldn't it be "...which means we split the polygon into the triangulation from vertex i to vertex

k, a triangle (i, j, k) and the triangulation from vertexkto vertexj."?Sorry... It's my fault again. I have corrected it. T_T....

I need more carefulness when writing the editorial. T_T...

Still one of the best editorials around here!

why is the date displayed randomly in some portion of the editorial of 437B - The Child and Set

the line that contains "Because for every two number

x, $y$, that ..."Something must be wrong with the MathJax rendering

Can somebody please elaborate 437C — The Child and Toy. Please.

This was my reasoning to solve this problem:

For each edge

econnecting nodesuandv, the cost to removeecan bef(u) if removed with nodeuorf(v) if removed with nodev. Since we want to minimize the total cost we should removeewith the minimum cost. How?Indeed my idea was not to disconnect the graph but to construct it, we start with an empty graph, then add the nodes one by one in ascending order of

f(node), the new node should be connected only with the existing nodes.Problem B is a nice problem, the algo is amazing~

My straightforward solution 6770869 for problem 437E - The Child and Polygon with an intended complexity

O(N^{3}) got TLE. After a bit optimization (just by a constant factor) it has passed 6774608. I am a bit disappointed, why there was such a tight time limit? In a competition like this (where we don't get a full feedback) authors usually let even unoptimized solution with the correct complexity pass. Why this wasn't the case? Have any of you experienced a similar problem?Even with this tight TL my O(N^4) solution passed with triple gap:) 6769384

Thank you for your response. The mistake probably wasn't in the time limit, but in my memoization ;-) I expected that the number of ways is always nonzero and used that value as "not calculated yet". But it can be zero for a collinear points subproblem. It makes me feel much better about the problem!

I have: 5430175, when my

`deque<>`

experienced too many reallocations due to being declared in a loop. Solutions with worse complexity and better constant factor passed, my optimal solution didn't.For the first problem 437A Can someone explain why the answer for testcase 30 A.h B.asdf C.asqw D.qwertasdfg

is

Cinstead ofD? I assumed that since D is twice longer than all other options?Both A and D are the great choices. So the child choose C.

in this test case, you have two possible choices, A and D

because D is twice longer than all, and A is twice smaller than all

and the problem statement says:

so the answer is C

i hacked 9 contestants with a case Like this one :D

Thanks for the explanation.

... and I hacked 15 :D

Hi all can anybody explain problem 437D - The Child and Zoo with more details ? Thanks

Does anyone know a fast way to calculate the square root of a number by prime (or not prime) modulo?

Cipolla's algorithm is waiting for you.

Hi may someone explain

`438D - The Child and Sequence`

better?, thanks.http://codeforces.com/blog/entry/12490#comment-171961 Xellos explained it well, too.

thanks.

Need help with div 2 B The Child and Set

This is the approach I took to solve it:

Iterate over all numbers from 1 to limit and decrease lowbit of each number from the sum (if it is not possible, then just continue to next number)

But, for some reason, the order in which I consider the numbers matters. If I try all numbers from 1 to limit, I get wrong answer (6785689). But, if I try numbers in the reverse order i.e. from limit down to 1, I get Accepted (6785709).

Can anyone explain why this happened?

I think it is because that when you try numbers from limit down to 1, you'll have many numbers whose lowbit = 1 to make the sum equal to the sum this problem required.

Just like there is a bottle, if you put big stones first and then put small stones will possibly fill the bottle. But if you put small stones first and then put big stones will possibly remain much empty room in the bottle.

I don't know your later algorithm is right or wrong. Maybe my data is too weak......? >_<...

I am not completely convinced about my algorithm, too. I don't know if it can be proved.

Your algorithm is surprisingly correct, with a rather convoluted proof. I'm not sure about the details, but basically you prove that your algorithm is correct for small values of

limit, then you can also prove that for large values oflimit, thesumwill diminish quickly enough to reduce to a proven result or otherwise is too large that even with the algorithm in the editorial it's impossible. Probably the thing that saves you is that the small cases are indeed true:lowbit(1) = 1,lowbit(2) = 2, so you can prove forlimit≤ 2 andsum≤ 3 either your algorithm solves it or your algorithm correctly states it's impossible.I'm still looking for a better proof. Let's see...

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

Yes, of course.

Can someone elaborate on how to solve 437D - The Child and Zoo? I don't understand the editorial.

Begin by sorting all the vertices (areas) according to the number of animals in it, in decreasing order. Also begin with an empty graph.

Now add the vertices one by one into the graph in our new order, along with the edges (roads) connected to it.

Whenever we add a vertex

v, we introduce a new component in the graph, namely that single vertex. Whenever we add an edgevifor some existing vertexito the graph, we might join two components, the component containingv(denoteA) and the component containingi(denoteB). If this is the case, then any path fromAtoBmust necessarily passes edgevi, and therefore passes the vertexv. Due to our sorting of the vertices,vmust have the least cost among all vertices present, and so the value offof this path isa_{v}, the number of animals inv.For example, take the first test case:

Sorting the vertices, we have the order 40, 30, 20, 10. So first we introduce the fourth vertex. Clearly there's no edge added here, as the graph only contains one vertex.

Next, we introduce the third vertex. Now we have vertices 4 and 3, and we also have the edge 4 - 3. We add the edge 4 - 3 to the graph, which apparently joins two components together. Denote the component with 3 as

A, and the component with 4 asB. (Note thatAonly contains the vertex 3, andBonly contains the vertex 4.) Thus any path connectingAandBmust visit vertex 3, and hence has a minimum animal ofa_{3}= 30. There is |A||B| = 1·1 = 1 such path, namely 3 - 4. This givesf(3, 4) = 30.Introduce the second vertex and the edge 2 - 3. Now, again, the component with 2 is now connected to the component with 3 (namely 3 and 4). Denote again

A,Baccordingly. Any path joiningAandBmust visit vertex 2 and has minimum animal ofa_{2}= 20. There are |A||B| = 1·2 = 2 such paths, namely 2 - 3 and 2 - 4. Sof(2, 3) =f(2, 4) = 20.The same can be said for vertex 1, giving

f(1, 2) =f(1, 3) =f(1, 4) = 10, hence the result.In the second test case, there will be a road that connects two vertices in the same component (if you process the edges from top to bottom, this is edge 3 - 1). We ignore such edges.

In the third test case, when you introduce vertex 5, you will connect it with two components, component 1, 2, 4 and component 6, 7. This is why I keep saying

Ato be the component containing the current vertex as opposed to only the current vertex alone; after you process edge 4 - 5, you will now have the component 1, 2, 4, 5, thus when you process edge 5 - 6, you will connect |A||B| = 4·2 = 8 such paths connecting 1, 2, 4, 5 to 6, 7.I hope this is clearer, but just ask if you still don't understand.

Thank you, I understand the solution now. It seems a bit harder than the typical Div2D/Div1B problem though.

Could someone please tell me why the equation

F(z) =C(z)F(z)^{2}+ 1 in 438E has only one solution?starts with either 1 or - 1. If you use the latter root, for some power series P; and inverse doesn't exist.

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

Let's consider power series

Let's assume

G(z) =b_{0}+b_{1}*z+b_{2}*z^{2}+b_{3}*z^{3}+ ...It's easy to find that

b_{0}is either 1 or -1.If

b_{0}is -1.then 1 +G(z) =b_{1}*z+b_{2}*z^{2}+b_{3}*z^{3}+ ... =z(b_{1}+b_{2}*z+b_{3}*z^{2}+ ...)So we can find a power series

P(z),for whichzP(z) =G(z)It's easy to find that we can never find a Q(z), for whick

zP(z)Q(z) = 1i.e.when

b_{0}= - 1 the inverse of doesn't existFor example, if

C(z) = 2z- 4z^{2}then is either 1 - 4zor - 1 + 4z. If we choose - 1 + 4zthen , which doesn't exist. If we choose 1 - 4zthen .Also, quadratic equations usually have two solutions.

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?It's defined as follow:

Let .

Then

X(x)^{2}=S(x).Modulo

x^{n}, it becomesBut there can be two different

X(x)s which satisfyX(x)^{2}=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?In this problem, it's .

So must be non-negative.

Due to this, we must take - .

Let all the coefficient be negative, then you can get another root which satisfy the equation

X(x)^{2}=S(x)For 437B — The Child and Set, I think you need to prove why all the numbers chosen are distinct. If the numbers are not distinct, the solution does not fulfill the problem statement. Here is the prove:

Let

a× 2^{x}=cfor some positive odd integersaand some positive integersxandcIf

b× 2^{x - y}=cfor some positive odd integersbandy≥ 1,$a \times 2^y = b$ can be true only when

y= 0. So, this is always false. So, the number chosen are always distinct.(Sorry, I am not familiar to the latex function in Codeforces. I do not know how to use align and why the formula in the bottom left hand corner does not show correctly.)

why we assume that a is odd ?? and I_ didn't get why only true when y = 0

For Div2B (The Child and the Set), I came up with a different solution which runs pretty efficiently. The idea is to continuously "split" numbers that have either already been used or are larger than the limit. We take all the 1 bits in sum and make them numbers (so a sum of 100101 would become 100000, 100, and 1), and split the numbers that don't satisfy the limit.

When splitting a number whose lowbit is x, we create two new numbers with lowbit (x — 1). So by splitting 100, we create numbers 10 and 110 or 1010 or 1110, etc, such that by using any two of these numbers with lowbit (x — 1) we can sum to a number of lowbit (x). Take two of these two numbers and split them again if necessary (above limit or already used). If the number isn't used and is below the limit, we mark it as used, and move on to split the next number.

The case where we can't split anymore (lowbit = 1, numbers like 111, 11, or 1) ends up becoming the case where we can't reach the sum. If we run out of numbers to split, then that means we have finished the problem, because all numbers satisfy the limit and are unique.

Code: 6792767

would you like to tell me the complexity of your solution..?

I believe it's O(limit) because we split each number under the limit at most once, though it varies a lot depending on the bits in the sum.

Can anyone link me his code for problem 437D — The Child and Zoo please ?

Can someone help me ?6850625 i keep getting WA , on test 7 from 437D - The Child and Zoo

Can anyone please explain the solution to 438D : Child and Sequence. I cannot understand it fully. I do understand that there cannot be more than

log_{2}xchangesonx. But I don't get the things after that.Thanks ! :D

i think it's the true div2