kisskiya
BAN USER 0of 0 votes
AnswersYou are given a tree with N nodes. Every node in the tree has a given weight. Your goal is to divide the given tree in two trees by removing exactly one edge such that the difference of sum of weights in the new trees is minimum.
 kisskiya in India
Input
First line contains integer T, the number of test cases. First line of each test case contains integer N, the number of nodes. Next line contains the N integers, weight of node 0, 1 .. N  1. The next N  1 line contain two space separated integers x and y, describing an edge, where x and y are 0 based indices for nodes in the tree.
Constraints
T <= 100, N <= 1000
Output
Output a single line for each test case, which contains the min absolute difference between the sum of the nodes of the two trees.
Example
Input:
2
3
8 7 8
1 0
2 1
9
5 5 4 1 8 8 3 5 2
1 0
2 0
3 1
4 1
5 3
6 0
7 5
8 1
Output:
7
13
Author: xyler
Date Added: 15072012
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.08, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC Report Duplicate  Flag  PURGE
Directi Software Engineer / Developer Algorithm  0of 0 votes
AnswersTwo numbers are called friendly if they share a digit. For example 1239 and 9760 are friendly where as 1234 and 9876 are not. You are given N numbers and you have to calculate the count of pairs of numbers that are friendly.
 kisskiya in India
Input
First line of input contains an integer T, the number of test cases. For each test case, the first line contains N, the number of integers given. The next N lines contain N integers.
Constraint
T <= 10, N <= 10 ** 4, Each given number is between 1 and 10 ** 18
Output
For each test case, print a line containing the count of pairs of number that are friendly.
Example
Input:
2
5
2837 2818 654 35 931
5
183 665 908 774 362
Output:
6
3
Author: xyler
Date Added: 15072012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.08, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC Report Duplicate  Flag  PURGE
Directi Software Engineer / Developer Algorithm
#include<stdio.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* consbst(int pre[],int k,int l)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
if(l==k)
{
tmp>data=pre[k];
tmp>left=NULL;
tmp>right=NULL;
return tmp;
}
int i=k+1;
while(pre[k]>pre[i]&&i<l)
i++;
i;
tmp>data=pre[k];
tmp>left=consbst(pre,k+1,i);
tmp>right=consbst(pre,i+1,l);
return tmp;
}
void printinorder(struct node* head)
{
if(head==NULL)
return;
printinorder(head>left);
printf("%d",head>data);
printinorder(head>right);
}
int main()
{
struct node* tree;
int pre[]={6,2,1,4,3,5,8,7,9};
tree=consbst(pre,0,8);
printinorder(tree);
getch();
}

kisskiya
July 27, 2012 consider n=5, then no. of ways to select nos. from 1 to 5 are
{5},{4,1},{3,2} => no. of ways=3.
similarly for n=10
{10},{9,1},{8,2},{7,3},{7,2,1},{6,4},{6,3,1},{5,3,2},{5,4,1} => no. of ways=9
similarly for n=11,
{11},{10,1},{9,2},{8,3},{8,2,1},{7,4},{7,3,1},{6,5},{6,3,2},{6,4,1},{5,4,2},{5,3,2,1} => no. of ways=12.
Note no number between 1 to n must be repeated
source code
#include<stdio.h>
int ways(int n)
{
int wayn=0;
if(n<3)return 1;
int i;
int way[n+1];
way[1]=1;
way[2]=1;
for(i=1;i<=(n+1)/2;i++)
{
wayn+=ways(i);
}
if(n%2&& n>=5)
way[n]=wayn1;
else
way[n]=wayn;
return way[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",ways(n));
getch();
return 0;
}

kisskiya
July 15, 2012
Repleancpuryear, Data Scientist at Adjetter Media Network Pvt Ltd.
Hi guys!! My name is Lean C Puryear and I love fashion, I hope to some day get into the ...
Open Chat in New Window
complexity of the method seems as O(4^n)..
 kisskiya July 27, 2012is there any better way??