NICENESS - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest
Problem

Author: Praveen Dhinwa
Tester: Kevin Atienza
Editorialist: Kevin Atienza

PREREQUISITES:

Greedy algorithms

PROBLEM:

Given a tree, a nice node is any node with degree \ge 3. The niceness of a tree is the maximum number of removals one can do to a tree before it gets emptied. A removal in a tree is the following procedure:

  • Identify all the nice nodes.
  • Remove all nodes such that there is a path to a leaf that does not pass through a nice node.

Given an N and \mu, is there a tree with exactly N nodes and exactly \mu niceness?

QUICK EXPLANATION:

If there’s a tree with N nodes and niceness \mu, then there is also a tree with N+1 nodes and niceness \mu (by just attaching a new node to a leaf). Therefore, we only need to find, for each \mu, the minimum number of nodes required to achieve a niceness of \mu. Let’s denote this by M(\mu).

It turns out that a greedy algorithm works:

  • For \mu = 1, the answer is a one-node tree.
  • To get an optimal tree with \mu niceness, first take an optimal tree with \mu-1 niceness and turn all leaves into nice nodes by attaching leaves to them. If \mu = 2, then you have to attach three leaves. If \mu > 2, you have to attach two leaves.

One can work out that M(\mu) = 3\cdot 2^{\mu-1}-2. Therefore, the answer is Yes if N \ge M(\mu), and No otherwise. Be careful with overflow!

EXPLANATION:

Removal

Let us first understand what a “removal” actually does. Let’s assume for simplicity that N > 1 (there is only one tree with N = 1 anyway). Therefore, we can assume that all nodes have at least one degree.

What does it mean to have a path to a leaf not passing through a nice node? Of course, the node must not be nice itself. Therefore, its degree is either 1 or 2. If the degree is 1, then the node is a leaf, so it will be removed during the removal. If the degree is 2, then there are two paths that can be followed. We find the first node along each path that is not of degree 2. If one of them meets a degree 1 node, then the path towards that node constitutes a “path to a leaf that does not pass through a nice node”, and thus the node is removed. If both paths arrive at degree > 2 nodes, then those nodes are nice nodes, and thus all paths to leaves must pass through a nice node, and the node is not removed

The above now describes completely which nodes will be removed at the current removal step:

  • If there are no nice nodes, then the whole tree is a simple path, and all nodes are removed.
  • If there is at least one nice node, then the nodes lying on “dangling” paths attached to nice nodes are removed.

Trees with a given niceness

Next, let’s try to answer whether there is a tree with N nodes and a niceness of \mu. The first thing we notice is that we can increase the number of nodes without changing the niceness: by attaching a new node to any leaf! Therefore, we have the property that:

If there is a tree with N nodes and a niceness of \mu, then there is also a tree with N+1 nodes and a niceness of \mu.

This means that there exists a tree with N nodes and niceness \mu if and only if N is not less than the size of the smallest tree with niceness \mu, and thus we only need to know for any fixed \mu the minimum number of nodes to achieve a niceness of \mu. Let M(\mu) be this minimum. We will now describe M(\mu) in the next section.

Calculating M(\mu)

One can probably try by hand (or with a bruteforcer) to get the following values:

\begin{array}{rr} \mu & M(\mu) \\ \hline 1 & 1 \\ 2 & 4 \\ 3 & 10 \\ 4 & 22 \\ 5 & 46 \\ \vdots & \vdots \end{array}

The corresponding trees are something like the following:

To extend this to larger trees, you get the idea: to get the optimal tree of niceness \mu, take the optimal tree of niceness \mu-1 and attach two leaves for every leaf! (In the case of \mu = 2, attach three.) This gives a somewhat small tree of niceness \mu with 3\cdot2^{\mu-1}-2 nodes. But are these trees really the smallest? Well, if you don’t have any formal proof yet, one important thing to remember during programming contests is to have a reasonable faith in your intuition. If you believed enough that this is optimal (which it seems intuitively) and submit this solution, you’ll get accepted!

However, it is still important to discuss whether this is really optimal. In the next section we will prove this.

Proof that optimal trees are optimal

Let’s try to prove that M(\mu) = 3\cdot 2^{\mu-1} - 2. Clearly, we know that M(\mu) \le 3\cdot 2^{\mu-1} - 2, because we have examples of such trees using the construction above. It remains to show that M(\mu) \ge 3\cdot 2^{\mu-1} - 2. For \mu = 1, this is clear, so we will only focus on \mu \ge 2. We will prove this by induction; specifically we will prove the following statement:

For any \mu \ge 2, any tree with niceness \mu has at least 3\cdot 2^{\mu-1} - 2 nodes and 3\cdot 2^{\mu-2} leaves.

For the base case \mu = 2, there cannot be only two leaves, because a tree with two leaves is just a path, and it only has a niceness of 1. Therefore there must be at least 3 = 3\cdot 2^{\mu-2} leaves. Next, any graph with < 4 nodes only has at most two leaves, therefore our tree must have at least 4 = 3\cdot 2^{\mu-1} - 2 nodes.

For the inductive case, assume that we have proven the statement for \mu, and we want to prove it for \mu + 1. Suppose we have a tree of niceness \mu + 1. If we perform a single removal step, then we will end up with a graph with niceness \mu, and by induction it has at least 3\cdot 2^{\mu-1} - 2 nodes and 3\cdot 2^{\mu-2} leaves. However, all of these leaves must have been nice nodes before the removal step, otherwise they should have been removed. Therefore, there must be at least two other branches attached to each leaf before, and each of these branches had at least one leaf, so our original graph must have had at least (3\cdot 2^{\mu-2})\cdot 2 = 3\cdot 2^{\mu-1} leaves. Thus the number of nodes must have been at least (3\cdot 2^{\mu-1} - 2) + (3\cdot2^{\mu-1}) = 3\cdot 2^{\mu} - 2, which proves the inductive case :slight_smile:

Time Complexity:

O(\log \mu)

AUTHOR’S AND TESTER’S SOLUTIONS:

Will be uploaded soon.

2

What is the problem with my solution?
It showed WA.

Solution-Link

1 Like
3

as tester and author’s solution is not updated…here is my code

Time Complexity : O(logn) (approx…)
space complexity : O(1)

         #include<bits/stdc++.h>
         using namespace std;

          int main(){

              long long int t;
                  cin>>t;

                long long int prev=0,P,i,N,sum=0;
             while(t--){

                        		cin>>N>>P;
	                        sum=0;

                                     if(P==1){
                                              // one node tree is required
                                              //constraint : N>=1
		                             cout<<"Yes"<<endl;
	                        }
                      		else if(P==2){
                                                 //here is simple image 
                                                ![alt text][1]
	                                   if(N>=4) cout<<"Yes"<<endl;
	                                   else cout<<"No"<<endl;
	                        }
                    		else{

		                        i=2;
	                                prev=3;
	                                sum=4;

                                              //leaf node 3 
                                              //now every time just cover leaf node only
                                             //every leaf node require only two node more

	                                   while(i<P  &&sum<=N){

	                                         sum+=2*prev;
	                                           prev*=2;
	                                            i++;
	                                       }
                               		    if(i==P && N>=sum) cout<<"Yes"<<endl;
	                                    else cout<<"No"<<endl;
	                                }
                               	}
                    	return 0;
                    }

***happy coding ***

like my group…https://www.facebook.com/groups/951379418217632/?fref=ts

4

@prrateekk

hi…prrateekk…

    because of ***overflow*** it is happening WA

       ***try your code with input
       1
        100 52

        print sum value 
         your program show
            sum=-2(some garbage value)...***

this happening because sum is increasing rapidly…(very high rate every time increment by double of previous addition)…
just check one more condition in your for loop

         for(i=1;i<mu-1 && sum<N;i++)
             {
                f*=2;
                  sum+=f;
              }
              if(i==mu-1 && N>=sum) printf("Yes\n");
               else printf("No\n);

here is your corrected code got AC…http://www.codechef.com/viewsolution/7291693

provide me feedback [email protected]
for more conversation like join my group…
https://www.facebook.com/groups/951379418217632/?fref=ts

5

So,the sum becomes so large that we can’t even store it in long long int.
Got the problem.I made a silly mistake.Thanks for helping.
I sent a request for joining your facebook group.

6

@prrateekk
your most welcome