Hello all guys:
I tried to convert some arbitray trees( T ) to binary trees( T* ),
then I found for any case tested, the answer for T is equal to T* 's
deepest path's length.
can anybody give a proof? or, if it' s wrong, a counterexample?
--~--~-~--~~~---~--~~
Y
@milochen Your approach is not correct. I am giving a counter examplesay our input is 423, so by ur approach the solution is 243 or 234but the correct answer is 342.The approach given by dhyanesh and dazi is correct.
On 2/28/06, milochen <[EMAIL PROTECTED]> wrote:
Does it always have the solution?
Does it always have the solution?
What about that 123456789 ?
I think that it doesn't always have solution for all case.
I am sorry that I couldn't give you a C++ code ,
since I have no complier,so I couldn't ensure whether
the code will be compile successful.
Assume X=(x_1,x_2,x_3, ...,x_(n-2
I am sorry about that my English is not good
and did not do a good definition for my way.
To choice the direct-subordinate that
the direct-subordinate is deepest subtree for his
superior officer is the greedy choice for the view
of dynamic programming.
So, Padmanabhan Natarajan say that Gene's
s
Yet, I had the common sence with you. so I know we focus on the
same thing, since you have a precisely nice way to say
the following in your article.
"
Define function M(T) to be the minimum number of rounds needed to
notify all the subordinates of T after T herself is notified. If T has
no sub
@kool_guy :
use recursion.
map min_map;
// p is a node of the tree;
// get_child_count(p) returns count of p's child;
// p[i] is its (i+1)th child, 0 <= i <= get_child_count(p)-1;
int minStep( p )
{
if( min_map.key_exist(p) ) return min_map[p];
min_map[p] = 0;
int child_count = ge
@milochen
I think your guessing is incorrect.
suppose a tree like this:
Root
/ | \
/ | \
c1 c2 c3
|
c4
in this case, the deepest subtree( root->c1->c4 ) need 2 step to walk
through, but the minimum step to broadcast for the entire tree is 3:
1. root-
@kool_guy :
use recursion.
map min_map;
// p is a node of the tree;
// get_child_count(p) returns count of p's child;
// p[i] is its (i+1)th child, 0 <= i <= get_child_count(p)-1;
int minStep( p )
{
if( min_map.key_exist(p) ) return min_map[p];
min_map[p] = 0;
int child_count = get_
@milochen
I think your guessing is incorrect.
suppose a tree like this:
Root
/ | \
/ | \
c1 c2 c3
|
c4
in this case, the deepest subtree( root->c1->c4 ) need 2 step to walk
through, but the minimum step to broadcast for the entire tree is 3:
1. root-
Hi everyone,
Please continue this discussions and I want to see the best algorithm
for sorting in the world today. If possible, give some performance
index.
Thank you.
Weng
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google
I do not have to necessarily find the shortest paths in the graph.
Essentially, I have to get rid of the internal nodes and find all
possible paths from input to output by adding the weights of the edges
and possibly constructing new edges in the graph to represent the new
connections.
Would All
Hi
The function I used is previous permutation of STL.
#include
#include
using namespace std;
char buff[100];
int main(void)
{
int no = 23245;
sprintf(buff,"%d",no);
if ( prev_permutation(buff, buff+strlen(buff) ) ) {
printf("%s",buff);
}
else
printf("You have
To daizi sheng:
great solution.both shorter and faster than mine.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsu
how about this shorter solution,:)
int go(unsigned int n)
{
int c[10] = {0},i,d,cur;
for(cur = 1;cur <= n;cur *= 10) {
d = n / cur % 10;
c[d]++;
for(i = d - 1;i >= 0;i--) if(c[i]) {
d = n / (cur * 10);
@Juvexp
Thats the perfect solution (I think).
I missed the sorting part when I worked on it.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@g
//this code seems works well
int f(int input)
{
int ret = -1;
char p[ 16 ];
memset(p,0,16);
itoa( input, p, 10 );
int len = strlen( p );
char *end = p + len;
char *start = end - 1;
char flag = (char)('0' - 1);
while ( start
16 matches
Mail list logo