# TESTERS - Editorial

**URL:** <https://discuss.codechef.com/t/testers-editorial/1578>\
**Category:** editorial\
**Tags:** editorial, feb13, hard, testers, trees\
**Created:** [February 13, 2013, 10:08pm UTC](https://discuss.codechef.com/t/testers-editorial/1578 "2013-02-13T22:08:17Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![pragrame](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pragrame/32/24644_2.png) [@pragrame](https://discuss.codechef.com/u/pragrame)\
**Post date:** [February 13, 2013, 10:08pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/1 "2013-02-13T22:08:17Z")

</div>

# Problem Link:

[Practice](http://www.codechef.com/problems/TESTERS)

[Contest](http://www.codechef.com/FEB13/problems/TESTERS)

# Difficulty:

Hard

# Pre-requisites:

Divide And Conquer, Number Theory

# Problem:

Define a beautiful number as one whose sum of divisors squared is odd. You are given a tree, in which each node has a number. A path from node X to node Y is beautiful iff the number of beautiful nodes is atleast the number of ugly (non-beautiful) nodes along the path. The length of a path is the number of nodes on the path. Find the total length of all beautiful paths over all pairs (X, Y) of nodes. Do not consider (X, Y) distinct from (Y, X) in this count.

# Explanation:

## Determining whether a number is beautiful or not

Let us first find out how to determine whether a number is beautiful or not. So, given the number n, what is the value of the sum of its divisors squared? Generally, most functions that are sums of functions of the divisors are arithmetic functions (i.e. f(mn) = f(m)f(n) when m and n are coprime). You could make this guess for this function too, and then prove it.

So, if n = pk, then its divisors are 1, p, p2, . . ., pk. The sum of its divisors squared is now 1 + p2 + p4 + … + p2k. If p == 2, then this the sum of these numbers is definitely odd. If p was an odd prime, then the sum of these numbers is odd iff k is even.

Now, when n = ∏(piai). The sum of squares of piai is ∑j=0ai (pi2j). Product of all these when expanded gives you exactly one square term for each divisor. Hence, f(n) = prod(f(piai)).

Now, f(n) is odd iff f(piai) is odd. This means that for every odd divisor of n, its exponent must be even for n to be beautiful.

By prime factorizing numbers upto 1.5 \* 10^6, one can check in O(1) time whether a given number is beautiful or not.

## Finding the total length of all beautiful paths

Now, we are left with finding the total length of all beautiful paths.

Since this is a tree, let us pick a “root” vertex **R** and check what is the total length of beautiful paths passing through **R**. We then apply Divide and Conquer: by removing R and considering the subproblems of each remaining connected component separately, and add all the answers up.

So, we have now rooted the tree at **R** , and each node is either beautiful or not. Let **R** ’s children be **x1, x2, …, xk.**

Now, suppose you are at a node **y** in the tree. Ask yourself what is the sum of lengths of beautiful paths which start at **y** , and pass through **R**?

It is easy to find the beauty of the path from **R** to each node in the tree (inclusive of both). You are currently at **y** , which has a path-beauty of **b(y)**. Let us say the child of **R** which is **y** ’s ancestor is **xi**. You need to ask, what all nodes are there in the subtrees rooted at **x1, x2, …, xi-1** , whose path-beauty value is **\>= -b(y)+b(R)**. This is because, any path from **y** to such a node would go through **R** , and would have a total beauty of **b(y) + b(other-node) - b(R)**.

What you really need is sum of the lengths, and the number of such nodes, not quite “which nodes”. Therefore, let us keep an abstract array len in which we wish len[b] = length of paths “seen so far” whose beauty = b. By “seen so far”, I mean that if you are node y which is a descendant of **xi** , then the values stored only correspond to nodes whose ancestors are **x1, x2, …, xi-1**. Now, you are at node **y** whose beauty is **b(y)**, and you need to ask, what is sum len[j] for j \>= -b(y) + b(R). We similarly have an abstract array cnt where cnt[b] = the number of nodes whose beauty is b.

The answer to the question “what is the sum of lengths of beautiful paths which start at **y** , and pass through **R**?” is “sum len[j] for j \>= -b(y)+b(R)” + (length of path from y to R, exclusive of R) \* “sum cnt[j] for j \>= -b(y)+b(R)”. What I have done is just counted the length of each path by breaking it up as a path from R to the other node + a path from y to R.

This can easily be accomplished by constructing a BIT over the abstract arrays len and cnt. Thus, so far we get the following algorithm. Assume that when you are at a node which is a child of **x1** , that **R** ’s beauty value is already seen.

```auto

ans = 0
Root the tree at R	// at this step, compute depths and beauties of all nodes
BITLen.increment(-b(R), 1)
BITCnt.increment(-b(R), 1)
if(b(R) == 1) ans++	// the path (R, R) is beautiful, of length 1
for i from 1 to k
	ans += do(k)
return ans

do(xi)
ret = 0
For each node y in subtree at xi, 
	ret += BITLen.query(-b(y) + b(R)) + (len(y)-1)*(BITCnt.query(-b(y) + b(R))
// Now, insert all the y's values into BITLen and BITCnt.
For each node y in subtree at xi,
	BITLen.increment(b(y), len(y))
	BITCnt.increment(b(y), 1)
return ret

```

We are now nearly done. After we have solved the problem for **R** , we now remove **R** and solve the problem for each of the remaining connected components.

If we were to analyze the time complexity of a single one of these runs, we would get O(n log n). If we were to arbitrarily choose **R** however, then for cases like the tree being a path, if we may end up taking time nlogn + (n-1)log(n-1) + (n-2)log(n-2) + … Which is atleast as bad as O(n^2).

The problem is at each step, the subtree size is very large. If we run a dfs to count the size of subtrees, then we can choose the vertex **R** intelligently. This approach has been used by the setter.

The overall time complexity is now O(N log^2 N)

# Setter’s Solution:

Can be found [here](http://www.codechef.com/download/Solutions/2013/February/Setter/TESTERS.pas)

# Tester’s Solution:

Can be found [here](http://www.codechef.com/download/Solutions/2013/February/Tester/TESTERS.cpp)

---

<div class="post-metadata">

**Author:** ![anton\_lunyov](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anton\_lunyov](https://discuss.codechef.com/u/anton_lunyov)\
**Post date:** [February 13, 2013, 10:40pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/2 "2013-02-13T22:40:09Z")

</div>

Actually beautiful numbers are exactly squares and double squares, which can be seen from the above formula for sum of the squares of divisors by analyzing parities of prime factors and exponents. So numbers at the vertexes could be made up to 10^18 easily 🙂

Also it should be noted that DFS here fails due to stack overflow error (at least at C++) because of quite large bound on N. So to get AC I runs BFS to order vertexes by their depth.

BTW, I have completely different solution. I will update this answer in a while.

---

<div class="post-metadata">

**Author:** ![aircube](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aircube/32/416_2.png) [@aircube](https://discuss.codechef.com/u/aircube)\
**Post date:** [February 13, 2013, 11:45pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/3 "2013-02-13T23:45:00Z")

</div>

Actually, there is O(NlogN) solution, but it`s so hard to explain =).

**Upd.**

Alright, solve problem using divide and conquer. Called function that caclulate answer for some tree with root **x** – **F(x)**. See on tree with root **v** , this sons are **u1** , **u2** , …, **uk**.  
Then **F(v) = F(u1) +F(u2) + … + F(uk) + something else.** Generaly, something else are paths that starts in some vertex **p** from subtree with root **ui** , and ends in some vertex **q** from subtree with root **uj** **(i != j)**.

Lets vertex number 1 - is **R**.

Lets **dq(v)** - count of ones subtract count of zeros on path from **v** to R.

Lets **umax** - some of **ui** , with maximum depth.

In the end of function **F(v)**, also return Treap, that contains information about all paths from **R** to some vertex in subtree of **v**.  
Element of Treap contains following fields:

1. dq - balance of path
2. cnt - count of paths with balance dq
3. summary length of paths

This information give us to calculate “something else”.

We do following in the vertex v:

1. Make Treap of **umax** is Treap of **v**
2. foreach **ui** ( **ui != umax** ) do
  1. iterate on all elements Treap of **ui** and do query to Treap of **v** ,
  2. add all elements Treap of **ui** to Treap of **v**

It`s possible to proof, this algorithm makes O(N) iterations, and one iteration takes O(logN) because of Treap.  
Main idea is

1. Number of elements of Treap of **v** is no more than _2(Height of subtree + 1)_\* with root **v**.
2. Proof by induction.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 14, 2013, 3:59am UTC](https://discuss.codechef.com/t/testers-editorial/1578/4 "2013-02-14T03:59:31Z")

</div>

The fact that “we can choose the vertex R intelligently” (mentioned at the end of the editorial) is actually called **centroid decomposition** and is a standard technique for many problems on trees. The centroid is that node for which the size of the largest subtree connected to it is minimum.

I also have a very different solution (however it has the same time complexity as the official one - O(N\*log^2(N))), based on the concept of heavy paths (actually, only heavy children - the heavy paths themselves are not used). I will try to post it soon (when I find some time) in a separate comment.

I would be very interested in knowing aircube’s O(N\*log(N)) solution.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 14, 2013, 6:15pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/5 "2013-02-14T18:15:51Z")

</div>

Here is the general idea of my **O(N \* log^2(N))** solution. First, let’s pick a root (say vertex number 1) - then the tree is rooted. Afterwards, we will traverse the tree bottom-up. For each node _i_ we will store all the paths starting at that node - and for each path we will have its length and its beauty (we add +1 for a beautiful node and -1 for a non-beautiful node on the path): let’s call this set of paths _Paths(i)_.

When we reach a node _i_ we already have the sets _Paths(j)_ computed for each child _j_ of _i_. We are interested in computing the set _Paths(i)_ and the total length of the beautiful paths passing through the node _i_. First we have a new path consisting of the node _i_ itself (which may be beautiful or not). Then, we will choose the child _j_ of _i_ with the largest number of nodes in its subtree (this will be the _heavy child_ of _i_). _Paths(i)_ will actually be initialized to _Paths(j)_ (as a pointer, not by copying the elements), which will later be updated.

In order to update _Paths(i)_ properly we will need to increase by 1 the length of each path in it and we will need to increase the beauty of each path in it by the beauty of node _i_. This will be achieved as follows: for each set _Paths(k)_ we will also have two extra values: _extralen(k)_ and _extrabeauty(k)_ which are values added to each of the paths in the set (besides that, each path also has its own length and beauty within the set).

Then we will insert the single-node path consisting of the node _i_ into _Paths(i)_. Afterwards we will consider all the other children of the node _i_ (except the heavy child _j_). Let’s assume that we now reached the child _k_. We will consider every path from the set _Paths(k)_, will compute its current length and beauty (considering that the path was extended up to node _i_) and then we will compute the sum of the lengths of all the paths from _Paths(i)_ which can be extended with the current path in order to form a beautiful path (this is simply a range query over the set _Paths(i)_, in order to consider the paths having a beauty larger than a given threshold).

After considering all the paths from _Paths(k)_ we will insert all these paths into _Paths(i)_.

Let’s analyze the time complexity of this solution, assuming that the sets _Paths(i)_ are implemented as balanced binary trees (I used treaps in my implementation). Inserting and searching in such a tree takes **O(log(N))** time. Traversing all the elements of such a tree can be performed in linear time (proportional to the number of elements in the tree).

All that is left is to see how many times insertions and searches are performed on these sets. For each node _i_ we perform an insertion and a search operation for each path starting at _i_ and having its other endpoint **NOT** in the heavy child. It’s not difficult to see that the total number of such operations is **O(N \* log(N))**. Whenever we reach a node _i_ all the interesting paths are defined by their other endpoint _p_. Whenever a path with the other endpoint _p_ is moved to the heavy child of the current node _i_, the size of the subtree at least doubles (compared to the previous node _i’_ when it was considered). Thus, a path with the other endpoint at a node _p_ is moved at most **log(N)** times (at the other times it is already in the set of paths of the heavy child and, thus, it is not moved at all).

---

<div class="post-metadata">

**Author:** ![gabber12](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@gabber12](https://discuss.codechef.com/u/gabber12)\
**Post date:** [August 28, 2013, 6:05pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/6 "2013-08-28T18:05:21Z")

</div>

Can anybody please explain that how setters solution is O(n\*log(n)).

To my understanding he is basically applying dfs on first the root, and then recursively on each of its child.

Even after centroid decomposition only the height of the tree is converted to log(n) but still the complexity seems to be nlogn(n) + (n-1)log(n-1)…

Even in balanced binary tree first the routine is applied on the root and then on each of its childs.

---

<div class="post-metadata">

**Author:** ![anton\_lunyov](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anton\_lunyov](https://discuss.codechef.com/u/anton_lunyov)\
**Post date:** [February 13, 2013, 10:51pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/7 "2013-02-13T22:51:34Z")

</div>

Both solutions are not available.

---

<div class="post-metadata">

**Author:** ![lutyj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/lutyj/32/3653_2.png) [@lutyj](https://discuss.codechef.com/u/lutyj)\
**Post date:** [February 14, 2013, 3:16am UTC](https://discuss.codechef.com/t/testers-editorial/1578/8 "2013-02-14T03:16:04Z")

</div>

I used setrlimit from \<sys/resource.h\> to increase stack size.

---

<div class="post-metadata">

**Author:** ![rubanenko](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rubanenko/32/310_2.png) [@rubanenko](https://discuss.codechef.com/u/rubanenko)\
**Post date:** [February 14, 2013, 3:24am UTC](https://discuss.codechef.com/t/testers-editorial/1578/9 "2013-02-14T03:24:24Z")

</div>

We would be very thankful if you try)

---

<div class="post-metadata">

**Author:** ![aircube](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aircube/32/416_2.png) [@aircube](https://discuss.codechef.com/u/aircube)\
**Post date:** [February 14, 2013, 5:31am UTC](https://discuss.codechef.com/t/testers-editorial/1578/10 "2013-02-14T05:31:29Z")

</div>

Firstly, i try to understand author`s solution, maybe it is also O(NlogN).

---

<div class="post-metadata">

**Author:** ![evandrix](https://discuss.codechef.com/user_avatar/discuss.codechef.com/evandrix/32/76299_2.png) [@evandrix](https://discuss.codechef.com/u/evandrix)\
**Post date:** [February 14, 2013, 7:55am UTC](https://discuss.codechef.com/t/testers-editorial/1578/11 "2013-02-14T07:55:13Z")

</div>

[sample](http://www.codechef.com/viewplaintext/1832104)

---

<div class="post-metadata">

**Author:** ![rubanenko](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rubanenko/32/310_2.png) [@rubanenko](https://discuss.codechef.com/u/rubanenko)\
**Post date:** [February 14, 2013, 5:20pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/12 "2013-02-14T17:20:45Z")

</div>

Unfortunetly, it is not O(NlogN). My solution will work exactly O(Nlog^2(N)) on chain of length N, for example.

---

<div class="post-metadata">

**Author:** ![pragrame](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pragrame/32/24644_2.png) [@pragrame](https://discuss.codechef.com/u/pragrame)\
**Post date:** [February 14, 2013, 7:06pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/13 "2013-02-14T19:06:38Z")

</div>

Links have been fixed.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 14, 2013, 9:33pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/14 "2013-02-14T21:33:06Z")

</div>

@aircube: I don’t see any divide-and-conquer in your solution. Anyway, apart from that, your solution seems quite similar to mine (try to have a look at it), except that for me _umax_ is the vertex with the largest number of nodes in its subtree (not the one with the maximum depth). If the treap you compute for every node _v_ contains the paths from _v_ to every node in _v_’s subtree then for sure there aren’t just **O(N)** iterations (there would be **O(N\*log(N))** iterations if you choose umax=the vertex with maximum subtree size and **O(N\*sqrt(N))** if umax=the vertex with maximum depth).

---

<div class="post-metadata">

**Author:** ![aircube](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aircube/32/416_2.png) [@aircube](https://discuss.codechef.com/u/aircube)\
**Post date:** [February 14, 2013, 9:53pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/15 "2013-02-14T21:53:55Z")

</div>

@mugurelionut: Do you know structure of the test where will be **O(N\*sqrt(N))** iterations for my solution? Btw, I added assert in my code, and there was no more than 1,500,000 iterations on tests.

---

<div class="post-metadata">

**Author:** ![aircube](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aircube/32/416_2.png) [@aircube](https://discuss.codechef.com/u/aircube)\
**Post date:** [February 14, 2013, 9:59pm UTC](https://discuss.codechef.com/t/testers-editorial/1578/16 "2013-02-14T21:59:56Z")

</div>

@mugurelionut: **O(N)** is simply to see on following problem: you are given a tree, and you are calculate number of paths of length **K**. I claim that it can be solved **O(N)** time with array, or **O(NlogN)** with balanced search tree.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 15, 2013, 12:21am UTC](https://discuss.codechef.com/t/testers-editorial/1578/17 "2013-02-15T00:21:44Z")

</div>

@aircube: 1,500,000 iterations seems closer to **O(NlogN)** than **O(N)**, right?(is that the maximum number of operations with treaps in your solution?). It’s still possible that I did not fully understand your solution (because it’s not clear to me how many elements you may have in each treap). My observations only referred to the case when for each node _v_ you may end up having in _v_’s treap one element for each node _w_ located in _v_’s subtree (corresponding to the path from _v_ to _w_)-that’s the case in my solution and I kind of automatically assumed that was the case with yours, too.

---

<div class="post-metadata">

**Author:** ![aircube](https://discuss.codechef.com/user_avatar/discuss.codechef.com/aircube/32/416_2.png) [@aircube](https://discuss.codechef.com/u/aircube)\
**Post date:** [February 15, 2013, 12:27am UTC](https://discuss.codechef.com/t/testers-editorial/1578/18 "2013-02-15T00:27:34Z")

</div>

@mugurelionut “Number of elements of Treap of v is no more than 2\*(Height of subtree + 1) with root v.” It depends only of height of subtree. I agree that number of iterations will be O(N \* logN) if we keep in Treap elements for each vertex in subtree, and don`t merge vertex with equal **dq**.

“is that the maximum number of operations with treaps in your solution?”

It`s maximum number of operations on codechef’s tests.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 15, 2013, 12:34am UTC](https://discuss.codechef.com/t/testers-editorial/1578/19 "2013-02-15T00:34:52Z")

</div>

@aircube: The **O(N \* sqrt(N))** case that I was referring may occur for a tree with the following structure. Let’s say that we have **K** vertices on a path, numbered from **1** to **K** and say vertex **1** is the root. Add a path of **2 \* (K-i)** vertices below each vertex **i** (from **1** to **K** ). Thus: node **K** will have depth **0** , node **K-1** will have depth **2** , node **K-2** will have depth **4** , …, node **1** will have depth **2 \* (K-1)**. The idea is that whenever you get to node **i** (between **1** and **K-1** ) the maximum depth child will **NOT** be **i+1**.

---

<div class="post-metadata">

**Author:** ![mugurelionut](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@mugurelionut](https://discuss.codechef.com/u/mugurelionut)\
**Post date:** [February 15, 2013, 12:54am UTC](https://discuss.codechef.com/t/testers-editorial/1578/20 "2013-02-15T00:54:42Z")

</div>

@aircube: OK, I finally understood your solution. My treaps actually contain pretty much the same information as yours. And I think you’re right: there are only **O(N)** iterations in your solution, as you said. That’s because the balance of a path starting at a node **v** and going down in its subtree can only take values between **-depth(v)** and **+depth(v)** (i.e. **O(depth(v))** different values). My previous observations would be correct if the balance of a path could take arbitrary values (e.g. if the beauty of a node was not just -1 or +1, but would be given as part of the input).

[Next page](https://discuss.codechef.com/t/testers-editorial/1578.md?page=2)