[algogeeks] Re: check Similar array
1st of all Happy New Year to All :) Must be both have same length also test some other test cases, :) Let me share things striking in mind , if you calculate the sum of power of 1st array by taking any number as base , remaining all the numbers as exponent so if take 3 as base calculate the for i =0 to n sum1+=3^a[i]; whats the complexity it will be O(nlogn) , becoz pow(a,b) can be done in O(logb) we doing for n number so why its O(nlogn) Now sort the 2nd array O(mlogm) , find the number which we have taken as base in 1st array , it will take O(logm) binary search now calculate the sum of all the remaining elements with base we found (base has to be same) as 2nd array has 3 , we found base as 3 here as well. for j=0 to m sum2+=3^b[j] finally compare sum1==sum2 ??? approach may be sounds naive , but think over complexity O(nogn) + O(mlogm) where m=n , we are not using any extra space as well . some of you may wondering why it will work , try to find out simple math behind it . Let me know if anything wrong or missed something ? comments are welcome :) Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fg4qEJf3v_AJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the path in two nodes of a binary search tree
@top coder , if its given that that you have to nodes as input , 1st find the two nodes , store their address then do any traversal to get the path between them , inorder will good . i ams assuming you wants to print the path between two such nodes. hope it suffices :) let me know if approach it not clear or i missed something . Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0jnGdn-_vZgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Best way to rank sentences based on similarity from a set of Documents
HI Anantha , I had similer discussion long time back , although its not full final but similer ,i hope it will gives you some idea . http://www.linkedin.com/groups/Detecting-Duplicate-Documents-1210167%2ES%2E55684470?qid=eb015784-36a3-498d-8441-558ace3b4038trk=group_items_see_more-0-b-ttl Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/8k-5tziIwLIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find even length palindrome.
@atul , its should be the either 1st even length palindrome or largest even length palindrome in question , so here we go while making problem more generic ,* given a string find the largest palindrome in that string * So As I Coded it Some Times Back , Have a Look http://shashank7s.blogspot.com/2011/06/wap-to-find-largest-palindrome-in.html also check* http://stevekrenzel.com/articles/longest-palnidrome* Let me me know guys if anything wrong or test case mising . Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/GPl_52gNxRYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find even length palindrome.
you can use Suffix Tree for more better efficiency Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/iAVCTYSPckMJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding all combination
@atul ,FYI, another naive approach will to generate the all subset of given set , thats the power set , has complexity O(n*2^n) , obviously not better then upper one , but still you can try to figure out the sum problem , you will get some relation to DP. Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Di1eSEnE8XQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Best way to rank sentences based on similarity from a set of Documents
You are given 'n' strings w1, w2, .., wn. Let Si denote the set of
strings formed by considering all unique substrings of the string wi. A
substring is defined as a contiguous sequence of one or more characters in
the string. More information on substrings can be found
herehttp://en.wikipedia.org/wiki/Substring.
Let 'S' = {S1 U S2 U Sn} .i.e 'S' is a set of strings formed by
considering all the unique strings in all sets S1, S2, . Sn. You will
be given many queries and for each query, you will be given an integer 'k'.
Your task is to output the lexicographically kth smallest string from the
set 'S'.
*Input:*
**The first line of input contains a single integer 'n', denoting the
number of strings. Each of the next 'n' lines consists of a string. The
string on the ith line (1=i=n) is denoted by wi and has a length mi. The
next line consists of a single integer 'q', denoting the number of queries.
Each of the next 'q' lines consists of a single integer 'k'.
Note: The input strings consist only of lowercase english alphabets 'a' -
'z'.
*Output:*
Output 'q' lines, where the ith line consists of a string which is the
answer to the ith query. If the input is invalid ('k' |S|), output
INVALID (quotes for clarity) for that case.
*
*
*Constraints:*
1=n=50
1=mi=2000
1=q=500
1=k=10*
*
*Sample Input:*
2
aab
aac
3
3
8
23
*Sample Output:*
aab
c
INVALID
*Explanation:*
For the sample test case, we have 2 strings aab and aac.
S1 = {a, aa, aab, ab, b} . These are the 5 unique substrings of
aab.
S2 = {a, aa, aac, ac, c } . These are the 5 unique substrings of
aac.
Now, S = {S1 U S2} = {a, aa, aab, aac, ab, ac, b, c}.
Totally, 8 unique strings are present in the set 'S'.
The lexicographically 3rd smallest string in 'S' is aab and the
lexicographically 8th smallest string in 'S' is c. Since there are only 8
distinct substrings, the answer to the last query is INVALID.
On Thu, Jan 5, 2012 at 3:59 PM, WgpShashank shashank7andr...@gmail.comwrote:
HI Anantha , I had similer discussion long time back , although its not
full final but similer ,i hope it will gives you some idea .
http://www.linkedin.com/groups/Detecting-Duplicate-Documents-1210167%2ES%2E55684470?qid=eb015784-36a3-498d-8441-558ace3b4038trk=group_items_see_more-0-b-ttl
Thanks
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
*http://shashank7s.blogspot.com*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/8k-5tziIwLIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
@shashank : i am not sure if i am getting it right but are you saying save address of 2 nodes. now do inorder traversal considering node1 as the starting point , during traversal if we find node2 then return. if that so , then i dont think so it will work for all the cases. please correct me if i am wrong. On Thu, Jan 5, 2012 at 3:55 PM, WgpShashank shashank7andr...@gmail.comwrote: @top coder , if its given that that you have to nodes as input , 1st find the two nodes , store their address then do any traversal to get the path between them , inorder will good . i ams assuming you wants to print the path between two such nodes. hope it suffices :) let me know if approach it not clear or i missed something . Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0jnGdn-_vZgJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
@atul ,, why it won;t work , any clarification ? Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra *http://shashank7s.blogspot.com* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/MAy1c62BN9cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find the path in two nodes of a binary search tree
1) suppose node1 is at level = 4 of the tree and node2 is at level = 3 of the tree if you do inorder traversal from node1 i.e calling function inorder(node1); now it will search form level 4 to the max depth of the tree it will never reach node2 because it is at level = 3. 2) suppose root of the tree is X node1 lies of the left subtree of the root and node2 lies on the right subtree of the root. now after saving address of node1 and node2 , you start inorder traversal at node1 or at node2. suppose if you call inorder(node1); it will search node2 in the left subtree of the root X...taking node2 as a root of the traversal , but node2 lies on the right subtree of root X. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: check Similar array
@Shashank : as i have mentioned in the question , no sorting allowed. if question would have allowed sorting then why not sort both array and compare it would be much simpler and no need of doing costlier operation like finding power. complexity = O(nogn) + O(mlogm) + O(n) -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] find point lies in side circle
you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: check Similar array
Some very nice approaches have been presented but I still feels for practical situations its better to sort and compare..All other algorithms presented above restricts the max value for an element in the array.In case the maximum value is small,we can simply count sort,and the algorithm will still be O(N) (Much simpler and immune to problems such as finite word size) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, Jan 5, 2012 at 5:17 PM, atul anand atul.87fri...@gmail.com wrote: @Shashank : as i have mentioned in the question , no sorting allowed. if question would have allowed sorting then why not sort both array and compare it would be much simpler and no need of doing costlier operation like finding power. complexity = O(nogn) + O(mlogm) + O(n) -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find point lies in side circle
Assuming that the N points on the graph are represented in the form of (x,y) i.e. cartesian coordinates.. Then say, A = ( a1, a2); The equation of the circle centered at A would be (x - a1)^2 + (y-a2)^2 = R^2... Now, to find the points that lie within the range R, u need to check the following for all points: Say, current point is (X1, Y1), then the point lies within range R, if (X1 - a1)^2 + (Y1-a2)^2 - R^2 0 All the points satisfying the above condition will constitute the answer... On Jan 5, 5:17 pm, dabbcomputers dabbcomput...@gmail.com wrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find point lies in side circle
@ all Ignore my previous post On Jan 5, 5:58 pm, Lucifer sourabhd2...@gmail.com wrote: Assuming that the N points on the graph are represented in the form of (x,y) i.e. cartesian coordinates.. Then say, A = ( a1, a2); The equation of the circle centered at A would be (x - a1)^2 + (y-a2)^2 = R^2... Now, to find the points that lie within the range R, u need to check the following for all points: Say, current point is (X1, Y1), then the point lies within range R, if (X1 - a1)^2 + (Y1-a2)^2 - R^2 0 All the points satisfying the above condition will constitute the answer... On Jan 5, 5:17 pm, dabbcomputers dabbcomput...@gmail.com wrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: check Similar array
@atul..no need to sorting , complexity will be O(nlogn) only , sorting makes searching easy so said to sort , u can linearly search that elemnt in 2nd array it will take O(m) in above case . finally complexity will be O(nlogn) only Let me know if anything wrong or missed something ? Thanks Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HSFJVUWYg1EJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] A graph problem
This problem is taken from www.codeforces.com.What can be the possible approaches?? A smile house is created to raise the mood. It has *n* rooms. Some of the rooms are connected by doors. For each two rooms (number *i*and *j*), which are connected by a door, Petya knows their value *c**ij* — the value which is being added to his mood when he moves from room *i* to room *j*. Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle? Input The first line contains two positive integers *n* and *m* (), where *n* is the number of rooms, and *m* is the number of doors in the Smile House. Then follows the description of the doors: *m* lines each containing four integers *i*, *j*, *c**ij* и *c**ji* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*, - 104≤ *c**ij*, *c**ji* ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself. Output Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number 0. Sample test(s) input 4 4 1 2 -10 3 1 3 1 -10 2 4 -10 -1 3 4 0 -3 output 4 Note Cycle is such a sequence of rooms *a*1, *a*2, ..., *a**k*, that *a*1 is connected with *a*2, *a*2 is connected with *a*3, ..., *a**k* - 1 is connected with *a**k*,*a**k* is connected with *a*1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as *k*, the sequence's length. Note that the minimum possible length equals two. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: A graph problem
@Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/El6uttSxuA0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] C output????
depends on compiler i think..but most probably it compares the
addresses.
On Wed, Jan 4, 2012 at 12:20 PM, saurabh singh saurab...@gmail.com wrote:
@all.Your explanations work because probably all of you are using a
compiler that's behaving in the same way.Don't conclude from what you
see...The compiler is free to store the constant strings the way it
wants.
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com
On Wed, Jan 4, 2012 at 12:13 PM, Rahul raikra...@gmail.com wrote:
it's near to a common mis conception that string liberals are in data
sections of THE PROGRAM
PLEASE READ THE FILE
a.out.h
and find the difference between initialized data and non initialized data
On 9/6/11, Sandy sandy.wad...@gmail.com wrote:
String constants (literals) are saved into the .data section of the
program,
Here is the sample program to show that. if() is essentially
comparing the
addresses of two pointers which is same.
int main()
{
char *p=persons;
char *q=persons;
char *r=persons;
char *s=persons;
printf(%x %x %x %x\n,p,q,r,s);
if(p==persons)
printf(technical %s,p);
else
printf(true %s,p);
return 0;
}
-
Output:
403021 403021 403021 403021
technical persons
On Tue, Sep 6, 2011 at 9:04 PM, sivaviknesh s sivavikne...@gmail.com
wrote:
main()
{
char *p=persons;
clrscr();
if(p==persons)
printf(technical %s,p);
else
printf(true %s,p);
return 0;
}
..op : technical persons ..plz explain .. how come it works like an
strcmp
operation???
--
Regards,
$iva
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Sandeep Kumar,*
( Mobile +91-9866507368
*“I believe in smart work, Believe Me”*
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A graph problem
find the size of smallest cycle in the given graph ... tarjan should do the trick.. dfs basically ... :) On Thu, Jan 5, 2012 at 7:02 PM, WgpShashank shashank7andr...@gmail.comwrote: @Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/El6uttSxuA0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A graph problem
Yes I also initially thought soBut how do we take into consideration the edge weights??The cycle can include such edges whose total cost may come negative. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Thu, Jan 5, 2012 at 10:01 PM, karthikeyan muthu keyankarthi1...@gmail.com wrote: find the size of smallest cycle in the given graph ... tarjan should do the trick.. dfs basically ... :) On Thu, Jan 5, 2012 at 7:02 PM, WgpShashank shashank7andr...@gmail.comwrote: @Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/El6uttSxuA0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: find point lies in side circle
Cut out the circle from the graph. The points on the cut-out circle are the answer. Don On Jan 5, 6:17 am, dabbcomputers dabbcomput...@gmail.com wrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Longest sequence of numbers with atmost diff K
@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH and MaxH is designed based on the element values
i.e A[i], but we will store only the index of the element i.e. 'i'.
// The above app will work as given the index we can always retrieve
the actual value i.e. A[i]..
*/
i guess i wrote it wrongly , but was considering it as mentioned by you.
it would be great if we discuss on the given sequence instead of
considering different one.
let considering below example
please check it and comment if i am doing it wrong.
INPUT
6
10
8
5
9
7
1
4
INDEX
0
1
2
3
4
5
6
7
K=8;
Heap formed so far , when j reaches at index position j=6
Min_heap formed (containing indexed of the elements)
6
3
0
5
2
4
1
Max_Heap formed(containing indexed of the elements)
1
4
2
5
0
3
6
A[Top(MaxH)] - A[Top(MinH)] K // (A[1] - A[6] 8)
//we are in else part of your logic
A[j] = A[Top(MinH)]; // A[6]==A[Top(MinH)] where
j=6 and Top(MinH)=6
currentStrInd = Top(MaxH) +1; // currentStrInd= 1+1 = 2 where
Top(MaxH) = 1
pop(Top(MaxH)); // removing index 1 from MaxH
so new MaxH will be :-
4
2
5
0
3
6
while(MaxH is not empty)
{
if (Top(MaxH) currentStrInd)// 4 2 here Top(MaxH) = 4 and
currentStrInd=2
// condition fail
move to else if
pop(Top(MaxH)) ; // *no pop operation taking place bcozz
condition fails*
else if (A[Top(MaxH)] - A[Top(MinH)] = K) // A[4] - A[6] = K i.e (9
- 1 =8 )
//
here Top(MaxH)=4 and Top(MinH)=1
break; //* condition satisfy so break this loop*
}
Heap after loop breaks:-
Min_heap
6
3
0
5
2
4
1
Max_heap
4
2
5
0
3
6
please check this example and let me know where i am getting it wrong.
thanks
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: A graph problem
The problem with the proposed depth first search is that it can try many very long paths, requiring exponential time, before it ever finds the correct cycle, even if the cycle is very short. A breadth-first search will avoid this, and using dynamic programming principles can accomplish the equivalent of a breadth-first search without excessively large memory requirements. Use an nxn table H[n][n] to represent the possible states after t moves. H[i][j] is the possible happiness at time t for a person starting at room i and now in room j. Start with the table initialized to min, a very large negative value, and the diagonal set to zero. This indicates that at t=0, you could start in any room with zero happiness. Then increment t and compute the new H, where H[i][j] is the maximum value of H[i][k]+Ckj for all values of k. As soon as you have a positive value in the diagonal, t is the length of the shortest cycle. Don On Jan 5, 7:07 am, saurabh singh saurab...@gmail.com wrote: This problem is taken fromwww.codeforces.com.Whatcan be the possible approaches?? A smile house is created to raise the mood. It has *n* rooms. Some of the rooms are connected by doors. For each two rooms (number *i*and *j*), which are connected by a door, Petya knows their value *c**ij* — the value which is being added to his mood when he moves from room *i* to room *j*. Petya wondered whether he can raise his mood infinitely, moving along some cycle? And if he can, then what minimum number of rooms he will need to visit during one period of a cycle? Input The first line contains two positive integers *n* and *m* (), where *n* is the number of rooms, and *m* is the number of doors in the Smile House. Then follows the description of the doors: *m* lines each containing four integers *i*, *j*, *c**ij* и *c**ji* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*, - 104≤ *c**ij*, *c**ji* ≤ 104). It is guaranteed that no more than one door connects any two rooms. No door connects the room with itself. Output Print the minimum number of rooms that one needs to visit during one traverse of the cycle that can raise mood infinitely. If such cycle does not exist, print number 0. Sample test(s) input 4 4 1 2 -10 3 1 3 1 -10 2 4 -10 -1 3 4 0 -3 output 4 Note Cycle is such a sequence of rooms *a*1, *a*2, ..., *a**k*, that *a*1 is connected with *a*2, *a*2 is connected with *a*3, ..., *a**k* - 1 is connected with *a**k*,*a**k* is connected with *a*1. Some elements of the sequence can coincide, that is, the cycle should not necessarily be simple. The number of rooms in the cycle is considered as *k*, the sequence's length. Note that the minimum possible length equals two. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Longest sequence of numbers with atmost diff K
@atul..
you are not getting it wrong.. Its absolutely correct
On Jan 5, 11:28 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH and MaxH is designed based on the element values
i.e A[i], but we will store only the index of the element i.e. 'i'.
// The above app will work as given the index we can always retrieve
the actual value i.e. A[i]..
*/
i guess i wrote it wrongly , but was considering it as mentioned by you.
it would be great if we discuss on the given sequence instead of
considering different one.
let considering below example
please check it and comment if i am doing it wrong.
INPUT
6
10
8
5
9
7
1
4
INDEX
0
1
2
3
4
5
6
7
K=8;
Heap formed so far , when j reaches at index position j=6
Min_heap formed (containing indexed of the elements)
6
3
0
5
2
4
1
Max_Heap formed(containing indexed of the elements)
1
4
2
5
0
3
6
A[Top(MaxH)] - A[Top(MinH)] K // (A[1] - A[6] 8)
//we are in else part of your logic
A[j] = A[Top(MinH)]; // A[6]==A[Top(MinH)] where
j=6 and Top(MinH)=6
currentStrInd = Top(MaxH) +1; // currentStrInd= 1+1 = 2 where
Top(MaxH) = 1
pop(Top(MaxH)); // removing index 1 from MaxH
so new MaxH will be :-
4
2
5
0
3
6
while(MaxH is not empty)
{
if (Top(MaxH) currentStrInd) // 4 2 here Top(MaxH) = 4 and
currentStrInd=2
// condition fail
move to else if
pop(Top(MaxH)) ; // *no pop operation taking place bcozz
condition fails*
else if (A[Top(MaxH)] - A[Top(MinH)] = K) // A[4] - A[6] = K i.e (9
- 1 =8 )
//
here Top(MaxH)=4 and Top(MinH)=1
break; //* condition satisfy so break this loop*
}
Heap after loop breaks:-
Min_heap
6
3
0
5
2
4
1
Max_heap
4
2
5
0
3
6
please check this example and let me know where i am getting it wrong.
thanks
--
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 unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] find point lies in side circle
we can do bfs. from the point A do bfs until distance = R On Fri, Jan 6, 2012 at 12:47 AM, shady sinv...@gmail.com wrote: problem link ? On Thu, Jan 5, 2012 at 5:47 PM, dabbcomputers dabbcomput...@gmail.comwrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] find point lies in side circle
@shady this problem is not from the online contest. i need this in my project @utkarsh please elloborate your idea in more detail On Fri, Jan 6, 2012 at 9:40 AM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: we can do bfs. from the point A do bfs until distance = R On Fri, Jan 6, 2012 at 12:47 AM, shady sinv...@gmail.com wrote: problem link ? On Thu, Jan 5, 2012 at 5:47 PM, dabbcomputers dabbcomput...@gmail.comwrote: you are given with N points on graph. and a point A on graph and range R you have to find the points that lies within the radius of R from point A. with complexity less than O(N). -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find point lies in side circle
i also think so data must be represent in some special form i heard about K-D trees but not yet studied about it On Fri, Jan 6, 2012 at 12:26 PM, Lucifer sourabhd2...@gmail.com wrote: @all.. To decide which points are within the range R, we need to look a each point..Hence the lower bound would be O(N).. Now, for doing it in O(N) we need to have the input being given in a particular order, basically the datastructure which stores the graph projects some releationship b/w all the points.. @utkarsh.. Say, the graph is represented as an adjancency matrix or list with edges showing the connection and weights defined the distance b/w the points...and assuming that this datastructure is given to u.. then its as good as applying dijikstra's to find the shortest path from A to all other vertices... and check which shortest paths are smaller than R... Basically it all depends on how the data is being represented.. @dabbcomputer Correct me if i m wrong.. On Jan 6, 11:48 am, shady sinv...@gmail.com wrote: how will one come to know which points are cut-out from the circle ? i fail to understand how can it be less than O(n) unless you store the given N points in a data structure ... where preprocessing itself involves O(N)... -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find point lies in side circle
the reason i asked you about problem link is because the solution to your problem depends on the way you want to use it... 1. if each time there are new N points and radius R, and only one query for it...then it just can't be O(n) 2. if N points are fixed and there are like 1+ queries then you can store it in some dataset and retrieve the result for that in O(logn) On Fri, Jan 6, 2012 at 12:29 PM, amrit harry dabbcomput...@gmail.comwrote: i also think so data must be represent in some special form i heard about K-D trees but not yet studied about it On Fri, Jan 6, 2012 at 12:26 PM, Lucifer sourabhd2...@gmail.com wrote: @all.. To decide which points are within the range R, we need to look a each point..Hence the lower bound would be O(N).. Now, for doing it in O(N) we need to have the input being given in a particular order, basically the datastructure which stores the graph projects some releationship b/w all the points.. @utkarsh.. Say, the graph is represented as an adjancency matrix or list with edges showing the connection and weights defined the distance b/w the points...and assuming that this datastructure is given to u.. then its as good as applying dijikstra's to find the shortest path from A to all other vertices... and check which shortest paths are smaller than R... Basically it all depends on how the data is being represented.. @dabbcomputer Correct me if i m wrong.. On Jan 6, 11:48 am, shady sinv...@gmail.com wrote: how will one come to know which points are cut-out from the circle ? i fail to understand how can it be less than O(n) unless you store the given N points in a data structure ... where preprocessing itself involves O(N)... -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: find point lies in side circle
@shady the N is same we just have to query the data again and again On Fri, Jan 6, 2012 at 12:47 PM, shady sinv...@gmail.com wrote: the reason i asked you about problem link is because the solution to your problem depends on the way you want to use it... 1. if each time there are new N points and radius R, and only one query for it...then it just can't be O(n) 2. if N points are fixed and there are like 1+ queries then you can store it in some dataset and retrieve the result for that in O(logn) On Fri, Jan 6, 2012 at 12:29 PM, amrit harry dabbcomput...@gmail.comwrote: i also think so data must be represent in some special form i heard about K-D trees but not yet studied about it On Fri, Jan 6, 2012 at 12:26 PM, Lucifer sourabhd2...@gmail.com wrote: @all.. To decide which points are within the range R, we need to look a each point..Hence the lower bound would be O(N).. Now, for doing it in O(N) we need to have the input being given in a particular order, basically the datastructure which stores the graph projects some releationship b/w all the points.. @utkarsh.. Say, the graph is represented as an adjancency matrix or list with edges showing the connection and weights defined the distance b/w the points...and assuming that this datastructure is given to u.. then its as good as applying dijikstra's to find the shortest path from A to all other vertices... and check which shortest paths are smaller than R... Basically it all depends on how the data is being represented.. @dabbcomputer Correct me if i m wrong.. On Jan 6, 11:48 am, shady sinv...@gmail.com wrote: how will one come to know which points are cut-out from the circle ? i fail to understand how can it be less than O(n) unless you store the given N points in a data structure ... where preprocessing itself involves O(N)... -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
