[algogeeks] Re: Online Job Directory
Report this profile as spam: http://groups.google.com/groups/abuse?url=http%3A%2F%2Fgroups.google.com%2Fgroups%2Fprofile%3Fenc_user%3DGblPpxBBT4-MvI5XR0ZYoR4i_V9C%26_done=%2Fgroups%2Fprofile%3Fenc_user%3DGblPpxBBT4-MvI5XR0ZYoR4i_V9C%26; On 11/3/07, maithili [EMAIL PROTECTED] wrote: Tired of joining program after program looking for a Real Home Based Job? Look no further! Our Work at home job directory is loaded with over 1000 Work at Home Employment Opportunities Offered by Real Employers. Visit us today for your free sample job guide (http://www.typeinternational.com/affil/ti12247.htm) select work from home employment --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Spiral number
Use the property that one of the diagonals has squares of odd numbers. So given a co-ordinate in that diagonal you know the number at that position. For positions not on that diagonal you can add/subtract appropriately and obtain the number you need. -Dhyanesh On 10/18/07, mukesh tiwari [EMAIL PROTECTED] wrote: Hello everybody , i am trying to solve this(http://online- judge.uva.es/ p/v9/903.html) problem and input constrants are such that it is not possible to store the the numbers in the array and print those numbers. So i use the algorithm 1)get the number and return its coordinate 2) take the input all adjacent coordiantes and return the number belonging to that coordinate . i am facing the problem in second part that is if i have given coordiante how to get the number belonging to that coordinate, lets consider the spiral 21 22 23 24 25 26 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 let the coordinate of 1 is (0,0) ie origin then coordinate of 11 will be (2,0) and so on . now my problem is if i give coordiante (2,-1) then my program should return 12 . thnkx in advance --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem with conditional statement
It says If there is more than one solution print the pair with smaller X value. Also I believe for a value of X only one of the 2 Y values might work, not sure though. -Dhyanesh On 6/18/07, mukesh tiwari [EMAIL PROTECTED] wrote: Hi everybody i am trying to solve problem http://acm.uva.es/p/v105/10512.html. my solution is (x+y)y=P(1) (x-y)x=Q (2) (1+(y/x))xy=P (1)//taking x outside (1-(y/x))x^2=Q (2) dividing 1 and 2 and let (y/x)=k (1+k)k/(1-k)=P/Q; solving for k k=-(P+Q) +-sqrt((P+Q)^2+4PQ)/2Q; since x=y so we can not take -ve sign as it will make |k|1 which is not possible so i take only +ve sign ; solution is possible only when (P+Q)^2+4PQ is perfect square . after determining k we can find out x and y so my values are x=+-sqrt(Q/(1-k)); and y=+-sqrt(Pk/(1+k)); now my problem is based on for each value of x we have two values of y so we have 4 pair of values .So which value to output . thnkx in advance . --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A cycle with minimum length
Hi You can solve this by dynamic programming/memoization. Start off from the left and maintain two lists of points, one for forward traversal and one for reverse traversal. Each point would be in any one of the lists. When you encounter a point try putting it in each of the lists turn by turn and call the function recursively. You just need to maintain the heads of each of the lists. Once you memoize, the complexity would be O(n^3). The signature of the function would be: int least_path( int current_position, int head_of_list1, int head_of_list2) -Dhyanesh On 3/30/07, Mahdi [EMAIL PROTECTED] wrote: Hello everyone! We have n points in a chart that none of them have the same length(I mean their 'x' parameter). We want to find a cycle with MINIMUM length with these assumptions : We start from the point with minimum length, meeting all of the points and finally return to the starting point. We are allowed to change our direction of moving only one time. I mean we go through more positive points seeing some of them, and when we arrive to the rightest point, we change our direction to the left, and seeing reminding points, return to the starting point. Let me give an example: We have 3 points a,b,c : a : x=2y=0 b: x=10 y=8 c: x=17 y=0 one possible cycle is : a--b--c--a another : a--c--b--a One of them is shorter than the another. 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem 4.2 from Introduction to algorithms
1) Scan through the array counting number of 0s and 1s in MSB, as well as separating the 0s into an array arr0 and 1s into an array arr1 (if you do not want to use extra space you can use splitting around pivot pass of quicksort). 2) You would know how many 0s and 1s should be present in MSB for the number 1 ... n (this would be n/2 and n/2 if n is a power of 2). 3) Either the 0s or 1s would be less, so the missing number has that digit as MSB. 4) Take that bucket i.e. arr0 or arr1 and repeat steps 1 to 3. The complexity of this is n + n/2 + n/4 ... = 2n = O(n). -Dhyanesh On 11/17/06, Arun [EMAIL PROTECTED] wrote: the original problem if the array is unsorted, u can do it, by counting the number of 1's (and hence 0's), in each bit position. (i.e vertically scan thru all the numbers once for each bit position). given any n, u know how many 1's shud be present in msb,2nd msb and so-on. based on this u can find the missing number but this is O(n . (number of bit positions - which is atmost lg(n)) ) still too slow. There is an O(n) solution :) to make the problem easier I have made the assumption that array is sorted :-) since the array is sorted , u know that there will be 2 ^(n-1) 0's followed by 2 ^(n-1) 1's in the MSB(most significatn bit) and 2 ^(n-2) 0's and followed by 2^(n-1) 1's repeated twice. So in general, u have for ith significant bit (i=1 means msb), 2^(n-i) 0s then 2^(n-i) 1s repeated i times. Now just do a binary search. Starting with the msb, extract(i,n/2) . if its 1(supposed to be 0), the missing number is in first half(and msb of missing number is 0). do the same for second msb and so on... comlpexity = O(lg n) , for n=2^k. On 11/17/06, Norbert [EMAIL PROTECTED] wrote: extract(i, n) - i'th bit from position n in an array A - i'th bit of A[n] On 11/17/06, Idris [EMAIL PROTECTED] wrote: Is this extracting i'th bit from a[X] or just extracting Integer from i th index of an array??? if its the later, then get the number and sum up by using OR operation not sure:-) then subtract it from n(n+1)/2=missing Number --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Proving Waring hypothesis...
I have a slight improvement O ( n^2 log (n ) )Say you have a^2 + b^2 + c^2 = d.Keep a sorted list of all possible a^2 + b ^ 2 ... this would take n^2 time to generate and n^2 log n to sort. Now loop over all possible 'd' and 'c' and compute d - c ^ 2. Use binary search to determine whether that number is in the list ... if it is then 'd' is a number which CAN be represented otherwise try for the next 'c'. There might be a better solution ... still thinking-DhyaneshOn 10/31/06, Karthik Rathinavelu [EMAIL PROTECTED] wrote:Question: Given n, find the numbers in the range of 0...n which CAN'T be represented in the form of sum of squares of 3 non-negative numbers. If anyone could possibly give a solution better than O(n^3), it will be good. Thanks,R.Karthik --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
Djikstra's or any other single-source shortest path algorithm should be good enough I guess.-DhyaneshOn 10/30/06, vijay [EMAIL PROTECTED] wrote:Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502...I thk its a toughie... --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
Why not .. it is a graph with edge weights = 1. In fact we can even just use BFS to solve this problem. I will try and submit a solution and see if what I am thinking is right.-Dhyanesh On 10/30/06, Pradeep Muthukrishnan [EMAIL PROTECTED] wrote: I dont see how Djikstra can be used here?On 10/30/06, Dhyanesh (ધયાનેશ) [EMAIL PROTECTED] wrote: Djikstra's or any other single-source shortest path algorithm should be good enough I guess. -DhyaneshOn 10/30/06, vijay [EMAIL PROTECTED] wrote:Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502 ...I thk its a toughie... --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: PAIR of shortest paths...
I just submitted a solution which uses BFS and passes the judge cases. So it is indeed a shortest path problem. Using Djistra's would be fine too, but as it is here the edge weights are just 1 so BFS works.-Dhyanesh On 10/30/06, Karthik Singaram L [EMAIL PROTECTED] wrote: I am not sure If I got the question right140 3 1 2 31 1 02 2 0 33 2 0 21 2Isn't the answer that camarade 1talks to camarade 0 who inturn talksto 2. Isnt this shortest path algorithm? isntDjikstra O(VlogV) which seems feasible for the problem rite?On 10/30/06, Pradeep Muthukrishnan [EMAIL PROTECTED] wrote: I dont see how Djikstra can be used here? On 10/30/06, Dhyanesh (ધયાનેશ) [EMAIL PROTECTED] wrote: Djikstra's or any other single-source shortest path algorithm should be good enough I guess. -Dhyanesh On 10/30/06, vijay [EMAIL PROTECTED] wrote: Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502 ... I thk its a toughie... --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: iarcs basic division (problem 1 and 2)
I would agree with problem 2.However, in problem 1, they have given you the different operations right ? I do not think you can choose your own operation. From the problem statement - Thisis followed by M lines each containing K integers describing the M different operation. So if you have a restricted set to choose from then it might not be always possible. -DhyaneshOn 9/18/06, Terry [EMAIL PROTECTED] wrote: Please ignore . my mistake.Terry wrote: What about problem 1 ? i am really puzzled . Problem 1: The Hunpur Visa Hunpur lies to the north of Siruseri and flights from Siruseri to many parts of the world go through Samosa Airport, the busiest airport in Hunpur. Hunpur demands that residents of Siruseri obtain transit visas in order to fly through Samosa. Recently, the authorities of Hunpur have enforced some strange rules regarding photographs to be submitted for obtaining visas. The size of the face in the photograph is measured along K different directions to get the numbers (m1,m2, ...,mK). The consulate has specified a lower bound and upper bound (li and ui respectively) along each of the K directions. So, a photograph with measurements (m1, m2, ...,mK) is accepted if and only if li = mi = ui for 1 = i = K. Otherwise, it is rejected. For example, if K =2 with l1 = 32, u1 = 36, l2 = 20 and u2 = 24, a photograph with measurements (33,20) would be accepted, but photographs with measurements (31,20) or (36,25) would be rejected. Many studios in Siruseri have come up with a partial solution to this problem. They digitally alter the image. They have a fixed collection of M operations. Each operation is a tuple (d1, d2, ...,dK), where each di is a (positive or negative) integer. The effect of this operation on a image with dimensions (m1,m2, ...,mK) is to change the dimensions to (m1+d1, m2+d2, ..., mK+dK). The studio cannot apply more than two operations on a photograph as it damages the quality of the image. Moreover, no operation can be applied more than once. For example, using the operations (-2,3) and (3,-1) we can transform an image of size (31,20) to one of size (32,22) which would be accepted by the Hunpur consulate. On the other hand, using these operations we cannot alter an image of size (36,25) to an acceptable one. Your task is to determine whether the photograph whose dimensions are given can be altered using at most two operations to an acceptable photograph. Input format The first line contains two integers K and M. The second line contains K integers giving the lower bounds for the K directions. The third line contains K integers giving the upper bounds for the K directions. This is followed by M lines each containing K integers describing the M different operations. This is followed by the last line containing K integers specifying measurements of the photograph. Output format If it is not possible to alter the image using at the most 2 operations then print a single line with the word NO. Otherwise, the first line of the output must have the single word YES, the second line must contain an integer i, indicating the number of operations (0 = i = 2) that may be used to transform the image into an acceptable one, and this should be followed by i lines describing the i operations. There may be more than one way to transform the image into an acceptable one, it suffices to print any one. Note: In this task, test inputs will be arranged in groups and marks will be assigned for groups of test inputs rather than to each individual test input. For example, one mark may be assigned for a group of three test inputs. This means that to score that one mark your program must run correctly on all three test inputs in the group. Thus, blindly printing NO is not likely to score many marks. Test data You may assume that K = 100 and M = 100. Example Here is a sample input and output corresponding to the example discussed above. Sample input 2 2 32 20 36 24 -2 3 3 -1 31 20 Sample output YES 2 3 -1 -2 3 ** Solution;I think the answer will always be YES. we have numbers like (l1,u1) ,(l2,u2),(l3,u3)...(ln,un) and numbers m1 ,m2,m3,...mn. now to map mi to (li,ui) , it is always possible (forgetting overflow). Is something wrong with my understanding of the problem. So i can always find a vector d1,d2,d3..,dn which maps m1,m2,m3...,mn between (l1,u1),(l2,u2)...(ln,un) in a single operation or 0 operations (if they already are in the range ).If a point is on x axis, then to move them between 2 points on x axis requires 1 displacement.similarly for other Comments please. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at
[algogeeks] Re: How to partition a set into two?
This is a NP hard problem. There is no efficient way to solve it quickly, though if you have small numbers you can do it with Dynamic Programming in a way very similar to the Knapsack problem in O(sum*n) time, where sum is sum of all the integers and 'n' is the number of integers you have. -Dhyanesh On 7/8/06, valpa [EMAIL PROTECTED] wrote: give a set with n integers, partition it into two sets with equal sum-value how can I do it efficiently? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find the most occured (more than N/2 times , where N is the length of the array) element in an array
If the array may or may not contain the majority element, then after the last step(ie once you get the get the array with one element) , just iterate thru the original array once counting the number of occurences of this element. This along with karthik's logic works perfect. And it does not take nlogn time. In fact it takes O(N) time. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find all paths from one node to another node
The problem does not ask for the *shortest* path. He wants to
enumerate *all* possible paths between two nodes.
-Dhyanesh
On 5/9/06, Narek Saribekyan [EMAIL PROTECTED] wrote:
Dhyanesh wrote:
Well if you have a graph of 'n' nodes ... then the number of paths can
be n! . And you would need that much time to enumerate all of them.
You can write a recursive algo to do this job.
-Dhyanesh
On 5/8/06, david wolf [EMAIL PROTECTED] wrote:
Hi,
I have a questions about a directed graph. Given two node k and i, I
wish to enumerate all the paths from node k to node i. How to do this?
Can anyone direct me how to do it or maybe give me a url for
explanation somewhere else?
Also, what is the time complexity for achieving this?
Thanks,
David
Dynamic Programming-the answer is in Dijkstra's algorithm.
5.3. Dijkstra Algorithm
Taken from:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the
problem of finding the shortest path from a point in a graph (the
source) to a destination. It turns out that one can find the shortest
paths from a given source to all points in a graph in the same time,
hence this problem is called the Single-source shortest paths problem.
This problem is related to the spanning tree. The graph representing
all the paths from one vertex to all the others must be a spanning tree
- it must include all vertices. There will also be no cycles as a cycle
would define more than one path from the selected vertex to at least
one other vertex. For a graph, G=(V,E) where V is a set of vertices and
E is a set of edges.
Dijkstra's algorithm keeps two sets of vertices: S (the set of vertices
whose shortest paths from the source have already been determined) and
V-S (the remaining vertices). The other data structures needed are: d
(array of best estimates of shortest path to each vertex) pi (an
array of predecessors for each vertex)
The basic mode of operation is:
1. Initialise d and pi,
2. Set S to empty,
3. While there are still vertices in V-S,
i. Sort the vertices in V-S according to the current best estimate of
their distance from source,
ii. Add u, the closest vertex in V-S, to S,
iii.Relax all the vertices still in V-S connected to u
Dijkstra Algorithm:
DIJKSTRA(Graph G,Node s)
initialize_single_source(G,s)
S:={ 0 } /* Make S empty */
Q:=Vertices(G) /* Put the vertices in a PQ */
while not Empty(Q)
u:=ExtractMin(Q);
AddNode(S,u); /* Add u to S */
for each vertex v which is Adjacent with u
relax(u,v,w)
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: find all paths from one node to another node
DFS will give only one path. You need all paths .. so it would be
something like this :
end_node
path_so_far
FindPaths ( curr_node ) {
if ( curr_node = = end_node ) {
print path_so_far;
return;
}
for each node new_node reachable from curr_node {
add new_node to path_so_far;
FindPaths( new_node );
remove new_node from path_so_far;
}
}
main
add start to path_so_far
end_node = end
FindPaths ( start )
-Dhyanesh
On 5/9/06, Nat (Padmanabhan Natarajan) [EMAIL PROTECTED] wrote:
How about a DFS? I guess this is Dhyanesh meant by a recursive solution.
On 5/9/06, akshay ranjan [EMAIL PROTECTED] wrote:
Floyd Warshall, Ford or djikistra's algorithms will solve shortest path
problems but not find all paths . The soln for this would be recursive(
brute force aproach)
On 5/9/06, Alejandro Narancio [EMAIL PROTECTED] wrote:
You can use the Floyd algorithm.
Regards,
Alejandro
On 5/9/06, Dhyanesh [EMAIL PROTECTED] wrote:
The problem does not ask for the *shortest* path. He wants to
enumerate *all* possible paths between two nodes.
-Dhyanesh
On 5/9/06, Narek Saribekyan [EMAIL PROTECTED] wrote:
Dhyanesh wrote:
Well if you have a graph of 'n' nodes ... then the number of paths
can
be n! . And you would need that much time to enumerate all of
them.
You can write a recursive algo to do this job.
-Dhyanesh
On 5/8/06, david wolf [EMAIL PROTECTED] wrote:
Hi,
I have a questions about a directed graph. Given two node k and
i, I
wish to enumerate all the paths from node k to node i. How to do
this?
Can anyone direct me how to do it or maybe give me a url for
explanation somewhere else?
Also, what is the time complexity for achieving this?
Thanks,
David
Dynamic Programming-the answer is in Dijkstra's algorithm.
5.3. Dijkstra Algorithm
Taken from:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
Dijkstra's algorithm (invented by Edsger W. Dijkstra) solves the
problem of finding the shortest path from a point in a graph (the
source) to a destination. It turns out that one can find the
shortest
paths from a given source to all points in a graph in the same time,
hence this problem is called the Single-source shortest paths
problem.
This problem is related to the spanning tree. The graph representing
all the paths from one vertex to all the others must be a spanning
tree
- it must include all vertices. There will also be no cycles as a
cycle
would define more than one path from the selected vertex to at least
one other vertex. For a graph, G=(V,E) where V is a set of vertices
and
E is a set of edges.
Dijkstra's algorithm keeps two sets of vertices: S (the set of
vertices
whose shortest paths from the source have already been determined)
and
V-S (the remaining vertices). The other data structures needed are:
d
(array of best estimates of shortest path to each vertex) pi (an
array of predecessors for each vertex)
The basic mode of operation is:
1. Initialise d and pi,
2. Set S to empty,
3. While there are still vertices in V-S,
i. Sort the vertices in V-S according to the current best
estimate of
their distance from source,
ii. Add u, the closest vertex in V-S, to S,
iii.Relax all the vertices still in V-S connected to u
Dijkstra Algorithm:
DIJKSTRA(Graph G,Node s)
initialize_single_source(G,s)
S:={ 0 } /* Make S empty */
Q:=Vertices(G) /* Put the vertices in a PQ */
while not Empty(Q)
u:=ExtractMin(Q);
AddNode(S,u); /* Add u to S */
for each vertex v which is Adjacent with u
relax(u,v,w)
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Insertion in a binary tree.
This method is better ! It would take only O ( log(n) ) time.
-Dhyanesh
On 5/8/06, W Karas [EMAIL PROTECTED] wrote:
shishir wrote:
Hi,
I am looking for a method for left to right insertion in a binary tree(
mind it, its not BST am talking about). A simple binary tree where
every root has not more than two childs and the insertion is always
done starting from the leftmost side of any given node.
13
/ \
27 54
/ \ / \
23 42
For eg in the above case the next node should be inserted as the left
most child of 54.
Let me know if there's any doubt regarding the question.
~Shishir
void add(elem *root, unsigned num_elems, elem *new_elem)
{
num_elems++;
if (num_elems == 1)
{
root = nuw_elem;
return;
}
elem *p = root;
unsigned mask = 1;
while (mask = num_elems)
mask = 1;
for (mask = 2; mask 1; mask = 1)
if (mask num_elems)
p = p-right;
else
p = p-left;
if (num_elems 1)
p-right = new_elem;
else
p-left = new_elem;
return;
}
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Chord Intersection
@pramod Arent all the 'n' chords part of the same circle ? If they are how can they be parallel without intersecting. If they are not of the same circle then its a different problem. @Karthik The complexity is not O(n). It is O(nlg(n)), since my first step is sorting the chords. Also you are doing essentially the same thing sorting, but instead of doing it at first, you are inserting stuff at each step of your algo. -Dhyanesh On 4/25/06, pramod [EMAIL PROTECTED] wrote: I don't think this will work. Suppose we have two chords which are parallel and both on the one side of the circle. i.e., say draw a diameter parallel to X and say the chords are above this parallel to each other. In that case, your answer will be 1 but they are not intersecting at all. I think your statement if you get another start point it means there is an intersection is not correct. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: k connectivity
I dont think max flow would work, because a max flow of 'k' will guarantee atleast k edges and not vertices. It is easy to come up with a case where removal of just one vertex will disconnect a graph with max flow of 'k'. On the other hand, I think the BFS would work pretty well, just ensuring that each time you remove vertices in the path and not edges. -Dhyanesh On 4/25/06, forest [EMAIL PROTECTED] wrote: you can not use BFS to find out if there are k disjoint paths between 2 vertices. It can be done by finding maximum flow and comparing it to k. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: k connectivity
Well .. I actually meant vertices as well as its edges ... not the other way around. Just a typo. Interesting ... how do you put restriction on vertices ? I havent heard of a max flow like it. -Dhyanesh On 4/25/06, forest [EMAIL PROTECTED] wrote: hard to undestand what you mean by removing vertices in the path and not edges. How can you remove a vertex without removing all its edges ? When i talked of maximum flow i of course ment that you also need put restriction on vertexes too. All edges and vertexes have unit capacity. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
This works only if you assume that you do not go backwards i.e. your max path length is N+M-2. If you can go backwards, then I think that there are more paths than just these. e.g. in 3x3 grid you can have path length more than 4 (1,1) - (1,2) - (2,2) - (2,1) - (3,1) - (3,2) - (3,3) I havent given much thought on how to count all possible paths ... maybe some variation of Floyd-Warshalls ... -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: There's a small error in my formula. The formula holds for a NxM grid (N horizontal and M vertical lines) where N= n+1 and M = m+1, which essentially boils down to C(N+M-2, N-1) = C(N+M-2,M-1). This should work fine. -Shishir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Shishir , have a look at my example ... there is no repetition of points in it. Your formula wont work for it. -Dhyanesh On 4/6/06, shishir [EMAIL PROTECTED] wrote: Well the formula works only for the corner end points as starting and ending node and that too on the diagonal ends. Its not a general formula for any set of starting/ending nodes. @Dhyanesh I think the problem clearly states that the nodes can only be traversed once i.e. no repetition. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: tree lock problem
This can be solved by two DFS traversals.The first from the root to the node N. Here you will get the path from root to N. Just go along the path and see whether there is any locked node. If there is a locked node then you cannot lock node N. Next you do a complete DFS of the subtree starting with node N. If any of the lower nodes are locked you cannot lock node N.Time complexity : O(nodes)-Dhyanesh On 3/24/06, Balaji Gopalan [EMAIL PROTECTED] wrote: hii had this question in my interview:you are given an n-ary tree.you are given its root R and a node N.the problem is to determine if u can lock the node N, given the constraints: 1) you cannot lock a node if any of its ancestors is locked. that is, if you lock a node N, then any node S in the subtree(with root N) cannot be locked till N is unlocked ( N is anscestor of S)2) similarly you cannot lock a node N if any node S in the subtree rooted at N is locked. 3) no parent pointers in node, you can traverse from root to child only.4) any representation for a node allowedEg: 1 / \ 2 3 / \ 4 5 here if 2 is already locked, then we cannot lock 4 or 5 else if 5 is already locked, we cannot lock 2byebalaji --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting Problem : Polynomial-time Algorithm !!!
The first part occurs when you place the file at a location 'i'. This would cost you Ci , also 'pi' is the place where the last storage server was placed. So for each in between you have to add a cost of '1' extra over the cost cost[i+1 , i ] whic would i -pi. The second case occurs when you dont put a server at location i. Then you just add a cost of one each for the servers between i and pi.Just make sure you fill the table in order.-Dhyanesh On 3/10/06, gcet [EMAIL PROTECTED] wrote: --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: need help help n help!!!
@pramod not quite ... the equivalence tester does not give a less than operation which is needed for sorting. It only tells whether they are equal or not. You cannot order them on the basis of that. -Dhyanesh On 3/9/06, pramod [EMAIL PROTECTED] wrote: Isn't third problem solved by sorting where comparison function isreplaced by the equivalence tester? After sorting we just run throughthe array to see if there n/2 repetitions.ajay mishra wrote: @stefan, ur idea seems correct to me. On 3/8/06, SPX2 [EMAIL PROTECTED] wrote:ajay what do you think of what i wrote ? -- Ajay kr. Mishra http://ajay.mishra19.googlepages.com IIT KGP --=_Part_1256_15286189.1141885069996 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Google-AttachSize: 554 @stefannbsp; , ur idea seems correct to me.brbrdivspan class=gmail_quoteOn 3/8/06, b class=gmail_sendernameSPX2/b lt;a href="" href="mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED][EMAIL PROTECTED]/agt; wrote:/spanblockquote class=gmail_quote style=border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex; brbr/blockquote/divbrbr clear=allbr-- brAjay kr. Mishrabra href="" href="http://ajay.mishra19.googlepages.com"> http://ajay.mishra19.googlepages.comhttp://ajay.mishra19.googlepages.com/abrIIT KGP --=_Part_1256_15286189.1141885069996-- --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting Problem : Polynomial-time Algorithm !!!
This can be solved by dynamic programming. The recurrence would be something like this : cost [ i , pi ] = min ( cost[ i+1 , i ] + Ci + i - pi ) ( i pi ) ( cost [i+1 , pi ] + i - pi ) ( i pi ) cost [ n , j ] = Cn for 1= j =n Least cost would be found in cost [ 0 , 0 ]. -DhyaneshOn 3/9/06, gcet [EMAIL PROTECTED] wrote: hi guysnew problem for uthink abt it and help me :)Suppose we want to replicate a file over a collection of n servers,labeled S1,S2,,Sn. To place a copy of the file at server Si results in a placement cost of Ci, for an integer Ci0. If a user requests thefile at server Si, and no copy of the file is present at Si, then theservers Si+1,Si+2, zre scheduled in order until a copy of the file is finally found, sat at server Sj, where ji. This results in anaccess cost of j-i. The accsess cost is 0 if Si holds a copy of thefile. We will require that a copy of the file be placed at server Sn,so that all such searches will terminate, at the last, at Sn. A configuration is a choice, for each server Si, with i=1,2,...,n-1, ofwhether to place a copy of the file at Si or not. The total cost of aconfiguration is the sum of all placement costs for servers with a copy --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: optimal assignnment of program to tapes.
Your solution is perfectly right. But this is NP hard problem and O(n L ). So for exponential L, the program runs into exponential time. -DhyaneshOn 3/8/06, Karthik Singaram L [EMAIL PROTECTED] wrote: This is the problem of dividing a set into two such that the sum of their differences is minimum.This can be solved using dynamic programming as follows: algo: 1. Create an array of size L say Arr[L] and initialize to zeroes 2. Put Arr[0]=1 3. For each program Pi Scan the array Arr from the right and if Arr[j]=1 then set Arr[j+Li]=1 4. From the right choose the first j such that Arr[j]=1 that will be the Length in S1 and the remaining will be Length in S2 --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Anyone interested in being paid to find a solution to a commercial problem?
I completely agree with you zavandi. Adak I think you need to take a course in basic algorithms. Quite a few times I have noticed you trying to trivialize algorithmic problems by giving some hack or ad-hoc solution which is not acceptable. I am a studied databases very well and know that this is not a database problem. If you still believe so give atleast some pseudo-code as to how you will create indices and so on. -DhyaneshOn 3/5/06, zavandi [EMAIL PROTECTED] wrote: On 3/5/06, adak [EMAIL PROTECTED] wrote: That may be part of the problem. I worked in Real Estate for 20+ years, but I don't relate to the OP's problem. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Anyone interested in being paid to find a solution to a commercial problem?
Isnt this exactly the same as the 0-1 Knapsack problem ? -DhyaneshOn 2/28/06, josh [EMAIL PROTECTED] wrote: We are software developers for the vacation rental business.We needto code an availability search (in Microsoft SQL Server) to find thecheapest combination of properties that will accommodate a givencapacity.Testing all possible combinations is not an option as forty properties will yield roughly a trillion combinations.We have got tothe point where we take each property in turn, starting with thecheapest in terms of cost per head, and then adding the next cheapestand so on, until greater than or equal to the required capacity is reached.If that capacity is reached EXACTLY, we then have a solution.So far so good.But if we have gone over the required capacity, thereis a possibility that a different mix with a lower capacity will be cheaper, even if the cost per head of capacity is higher, as a resultof the spare capacity in going over what is required rather thanmatching it exactly.We also need to be able to implement a solution WITHIN SQL Server as 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: largest Number Smaller Than Given Number
Hi
The function I used is previous permutation of STL.
#include algorithm
#include cstdio
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 smallest possible number \n);
return 0;
}On 2/26/06, ajay mishra [EMAIL PROTECTED] wrote:
@dhyanesh have u written some pseudo-code function fo the
problem as actually i could only c prev_permutation. Can u make it more
clear.On 2/26/06, Dhyanesh
[EMAIL PROTECTED] wrote:
This should work prev_permutation ( )-DhyaneshOn 2/26/06, Dont Know
[EMAIL PROTECTED]
wrote:@daizi sheng Thanks for Ur ideas.But in Ur solution how dou fix the prefix.
ie., How did U choose 112 as the prefix in the number 11261.Canu pls provide the algo.@Ajay U are correct.for the first example I gave, I made a mistake.So, I will define the problem again.Sorry for that.So the correct
requirement is the algo should give the largest number possible, but smallerthan the given number with a constraintthat the same combinationof digits are to be used.It is true that for some numbers this may
-- Ajay kr. Mishra
www.ajay.mishra19.googlepages.comIIT KGP
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: largest Number Smaller Than Given Number
This should work prev_permutation ( )-DhyaneshOn 2/26/06, Dont Know [EMAIL PROTECTED] wrote:@daizi sheng Thanks for Ur ideas.But in Ur solution how dou fix the prefix. ie., How did U choose 112 as the prefix in the number 11261.Canu pls provide the algo.@Ajay U are correct.for the first example I gave, I made a mistake.So, I will define the problem again.Sorry for that.So the correct requirement is the algo should give the largest number possible, but smallerthan the given number with a constraintthat the same combinationof digits are to be used.It is true that for some numbers this may --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: An interesting problem from Code4bill second round
I dont think that this would work either when you flip the first 14 cells to zero. The 15th cell would be still one. This cell you cannot flip to zero since its previous cell is zero. Then as you go on proceeding you would be leaving one cell every 15 cells as 1. You will reach a point where you already have 15 ones and then you cannot toggle a cell any more. -DhyaneshOn 2/1/06, Richa Minda [EMAIL PROTECTED] wrote: i got anwser of this question as::65527 as 1st time it would reuire 15(14+1) flips to one then again flip 14 cells to zero now after tht we will reach 14 cell now again flipnext 14 cells to one and then to zero then we will reach 28 cell i.e in every28 filp we gohead 14 cells (except in 1st time where we neeed one flip extra) i.e. in 2340 time i.e 2340*28 =65520 flips we will reach 32760 cell and add another 6 flip to reach 32766th cell =65520+1+6=65527 On 2/1/06, Dhyanesh [EMAIL PROTECTED] wrote: Once you have set the 14th one to zero in the next step you wont be able to flip the 15th one. On 2/1/06, srinics [EMAIL PROTECTED] wrote: How about this ?1) Set first 15 1's2) Flip 14th and 16th 2) Flip 15th and 17th...and so on The no. of flips would be:15 in step 1 +two flips each for the remaining (32767-15) cells15 + 2(32767-15) -- Richa
[algogeeks] Re: Recursion in blobs
Your answer is absolutely right. It is indeed O(n). This algorithm is more commonly known as Depth-First Search (DFS). It is used for a variety of problems. Google for depth-first search and you will get more results. -DhyaneshOn 1/26/06, H. [EMAIL PROTECTED] wrote: Today in a data structures class we went over blob recursion. What wewent over is actually described on this page (different school though): http://www.bowdoin.edu/~ltoma/teaching/cs107/fall05/Labs/lab9.htmlI understand how the recursion works, but I'm more interested indeterming the exact algorithm. I asked the professor, and he didn'tknow, except to say that it was very inefficient I toyed around with it a for a few minutes tonight, trying to determinethe worse-case efficiency if all squares will filled in a playing fieldof x*y=n squares. I think I'm doing something wrong, because my initial figur ended up with 9n, which would be Big Oh n, which I'm sure can'tbe right; it must be more inefficient than that.Any ideas? Both on how to go about determining the algorithm and theactual algorithm itself.
[algogeeks] Re: How to construct a LL(1) grammar for language...
As per the problem statement it does not seem that just looking at one
symbol it would be able to determine the next production, which is a
requirement for LL(1) grammar. I havent tried to reduce it, but just an
observation that it might not be possible.
-DhyaneshOn 12/23/05, feeldead [EMAIL PROTECTED] wrote:
I encountered a problem like this:Construct a LL(1) grammar for language {w | a and b have the samenumber of appearances in w}for example, ab, aabb, abab... all should be in this language.A candidate grammar is:
S :: aSbS | bSaS | @where @ stands for empty string.Unfortunately, this grammar is not LL(1), and I tried and failed totransform it into LL(1), anybody has good ideas?
[algogeeks] Re: TSP JAVA code Needed
Hi
Backtracking is the n! solution. It does not require too much
space. However it is much slower than the O ( 2^n . n ) solution.
This difference is easily evident even if you try to solve for say n =
15.
15 ! = 1307674368000 operations
15 . 2^15 = 491520 operations
I still believe that the dynamic programming solution is the best
even though it requires a lot of space. For large 'n' the space would
surely increase exponentially , but then for those larger numbers it
would be much much time consuming to get the n! solution.
Here is a problem which I had solved : http://online-judge.uva.es/p/v109/10944.html
#include cstdio
#include algorithm
#include cstdlib
#include cmath
#include cassert
using namespace std;
int dist[20][20];
char arr[50][50];
int ord[20],no;
int memo[20][117];
int go(int c,int st)
{
int ret=memo[c][st];
if (ret=0)
return ret;
if (st==1)
return ret=dist[c][0];
ret=130;
for(int i=1;i=no;i++)
if ((st(1i)))
ret ?= dist[c][i]+go(i,st~(1i));
return ret;
}
int main(void)
{
int x,y,i,j;
while (scanf(%d %d\n,x,y)==2){
memset(dist,0x7f,sizeof(dist));
int c=1;
for(i=0;ix;i++){
fgets(arr[i],sizeof(arr[i]),stdin);
for(j=0;jy;j++)
if (arr[i][j]=='#')
arr[i][j]=c++;
else if (arr[i][j]=='L')
arr[i][j]=0;
}
for(i=0;ix;i++)
for(j=0;jy;j++){
if (arr[i][j]=='.')
continue;
int k,m;
for(k=i;kx;k++)
for(m=0;my;m++){
if (arr[k][m]=='.')
continue;
int t = min(abs(i-k),abs(j-m));
dist[arr[i][j]][arr[k][m]] = t+abs(i-k)-t+abs(j-m)-t;
dist[arr[k][m]][arr[i][j]] = t+abs(i-k)-t+abs(j-m)-t;
}
}
c--;
if (c==0)
printf(0\n);
else{
int min=130;
memset(memo,0xff,sizeof(memo));
int cst = (1c+1)-1;
no=c;
for(i=1;i=c;i++)
min ?= dist[0][i]+go(i,cst ~(1i));
printf(%d\n,min);
}
}
return 0;
}
-DhyaneshOn 12/22/05, sudhakar-aluri [EMAIL PROTECTED] wrote:
what if we use backtracking to find the hamiltonian cycles andfinding the min of that. It reduces the space required.since we need tostore only one cycle at one shot. am i missing the stack space required
of recursion of backtrack.??Dhyanesh, what about time. does it reduces the time as well??here we go...{mincost - 0;answercycle - null; while( (h - GetNextHamiltoncycle()) != NULL){.
C - getcose(h);if( mincost == 0) mincost = C; //init.else if( C mincost){mincost - C; answercycle - h;}}}
[algogeeks] Re: 1 to 1 Lack numbers in a stream .. find the missing number
This problem has already been solved on this group before. See previous threads for title Missing Numbers. It is done by XORing.-DhyaneshOn 12/20/05, Uppala Babu [EMAIL PROTECTED] wrote: you have been a long input stream of 1 to 1Lakh number in which one number is missing and in place of that number -1 is present, input comes in random order, you have to find the number which is missing and also at what position in the input stream this -1 occurs. Regards Babu
[algogeeks] Re: TSP JAVA code Needed
TSP problem statemet : Given n cities find the shortest tour that passes through each of the cities exactly once. This is not a shortest path problem. -Dhyanesh On 12/15/05, HalFas` [EMAIL PROTECTED] wrote: you can find some info about path finding in theese links:http://theory.stanford.edu/~amitp/GameProgramming/ http://www.gameai.com/pathfinding.htmlhttp://www.redbrick.dcu.ie/~hazy/networks/dijkstra.html http://www.eas.asu.edu/trace/eee459/sriram.htmlOn 12/16/05, ridvansg [EMAIL PROTECTED] wrote: HalFas I am interested give some more info about this point based algorithem-- Lukas Šalkaukas
[algogeeks] Re: Polygon area
Hi
Here is some code .. which does it in linear time in one pass .. you
cant do better than that since you need to read the directions atleast
once.
int area( ){
int ret = 0 , x=0;
while (// there are more chars ) {
//read next char into ch
switch ( ch ){
case 'n': y++;
break;
case 's': y--;
break;
case 'e': area += y;
break;
case 'w': area -= y;
break;
};
}
return abs ( ret );
}
-Dhyanesh
On 11/21/05, pramod [EMAIL PROTECTED] wrote:
Here's another interesting problem I came across:
You are to compute the area of the polygon described a set of vertical
and horizontal lines.
· The input to your program describes a path around the polygon.
· The path is described as a set of directions:
o North: 'n'.
o East: 'e'.
o South: 's'.
o West: 'w'.
· The path description will be terminated by a period, '.'.
· The path will never cross itself and will never go over the same
area twice.
· You may assume that the path is made up of no more than 5
segments.
Here is some sample input:
e n w s .
n e s e n e s s w w w n .
and the output corresponding to the input:
1
5
How quickly can you compute the area of a polygon described in this
fashion?
What is the order of the computation that needs to be performed?
How small a program can you write to perform this computation?
-Pramod
