Re: [algogeeks] BST Question

2010-10-13 Thread nishaanth
>
> Just see the value of the node at every point, if it is greater than zero
dont recurse the right sub-tree, as simple as it is.print the node u
inspected if it is less than zero.




-- 
S.Nishaanth,
Computer Science and engineering,
IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm

2010-10-13 Thread Amod
@Dave  You are partly correct.

If i ask for four minimum fares for the round trip then
first suggestion is what u said : sum the sum of the minimum cost from
A to B and the minimum cost from B to A
after that we have to see which combination from both costs, sums up
least

On Oct 14, 9:55 am, Dave  wrote:
> @Amod. Isn't the minimum sum the sum of the minimum cost from A to B
> and the minimum cost from B to A? What am I missing?
>
> Dave
>
> On Oct 13, 11:06 pm, Amod  wrote:
>
>
>
> > Hi
>
> > I think I forgot to mention that the SUM of the ROUND trip i.e. A->B->A  
> > (sum = going + returning) should be least.
>
> > Please don't take into account any other thing like time and
> > availability.
> > So solution is not that straightforward.
>
> > Its like we have two arrays and we have to return least k sum from the
> > given arrays where we take one element from the first and one from
> > second in the sum.
>
> > Cheers
> > Amod
>
> > On Oct 13, 2:26 pm, Shiyam code_for_life 
> > wrote:
>
> > > When a user wants to choose to fly from A to B, suggest the flight
> > > with lowest fare that's available, here its A1, if A1 is busy then A2
> > > and so on
> > > Repeat the same for B to A.
>
> > > Am I missing something here?
>
> > > Complexity is O( (number of flights from A to B) + number of flights
> > > from B to A) )
>
> > > Cheers
>
> > > 'Coding is an art'- Hide quoted text -
>
> > - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] BST Question

2010-10-13 Thread Narsimha Raju
HI
   A BST is given you need to print all the negative numbers.

Sol: Inorder traversal will work. but i want to ignore the right sub trees
based on the value at the root. (i.e efficient sol)

-- 
Regards,
C. Narsimha Raju
MS, IIIT Hyderabad.
http://research.iiit.ac.in/~narsimha_raju/

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm

2010-10-13 Thread Dave
@Amod. Isn't the minimum sum the sum of the minimum cost from A to B
and the minimum cost from B to A? What am I missing?

Dave

On Oct 13, 11:06 pm, Amod  wrote:
> Hi
>
> I think I forgot to mention that the SUM of the ROUND trip i.e. A->B->A  (sum 
> = going + returning) should be least.
>
> Please don't take into account any other thing like time and
> availability.
> So solution is not that straightforward.
>
> Its like we have two arrays and we have to return least k sum from the
> given arrays where we take one element from the first and one from
> second in the sum.
>
> Cheers
> Amod
>
> On Oct 13, 2:26 pm, Shiyam code_for_life 
> wrote:
>
>
>
> > When a user wants to choose to fly from A to B, suggest the flight
> > with lowest fare that's available, here its A1, if A1 is busy then A2
> > and so on
> > Repeat the same for B to A.
>
> > Am I missing something here?
>
> > Complexity is O( (number of flights from A to B) + number of flights
> > from B to A) )
>
> > Cheers
>
> > 'Coding is an art'- Hide quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm

2010-10-13 Thread Amod
Hi

I think I forgot to mention that the SUM of the ROUND trip i.e. A->B-
>A  (sum = going + returning) should be least.
Please don't take into account any other thing like time and
availability.
So solution is not that straightforward.

Its like we have two arrays and we have to return least k sum from the
given arrays where we take one element from the first and one from
second in the sum.

Cheers
Amod

On Oct 13, 2:26 pm, Shiyam code_for_life 
wrote:
> When a user wants to choose to fly from A to B, suggest the flight
> with lowest fare that's available, here its A1, if A1 is busy then A2
> and so on
> Repeat the same for B to A.
>
> Am I missing something here?
>
> Complexity is O( (number of flights from A to B) + number of flights
> from B to A) )
>
> Cheers
>
> 'Coding is an art'

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: spoj problem BOTTOM

2010-10-13 Thread Gene
The simplest approach is probably to compute the transitive closure of
the graph.  Then look at each pair (row k, column k) of the closure.
When they're equal, k is an element of bottom.  All this requires
O(n^3).  Since n <= 5000, this should take a few seconds in the worst
case.

On Oct 13, 12:52 pm, praba karan  wrote:
> spoj.pl/problems/BOTTOM
>
> my algo for this prob goes by this way..will this work correctly?
>
> 1)first make a bfs from an arbitrary node and store the nodes visited
> in order in an array.
>
> 2)the node that is visited at the end of the BFS in the 1st bfs is now
> taken as the root and then make a BFS from this node and store the
> nodes visited in order in an array.
>
> 3)reverse the array in step 2
>
> 4)find the Longest Common Subsequence between the arrays in step 1 and
> step 3
>
> 5)if any one of the array is empty,then all the other nodes in the
> other array sud b printed.
>
> will this logic work?
>
> any other ideas are welcomed...
>
> praba...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum set of Collinear points

2010-10-13 Thread Dave
@Asquare. Yes, you are wrong. If the slope of the line AB equals the
slope of the line AC, then points A, B, and C are collinear. One way
to look at it is that because AB and AC have the same slope, they are
parallel (if you can call coincident lines parallel), and they both
contain point A. Therefore, they are coincident.

Dave

On Oct 13, 3:04 pm, Asquare  wrote:
> @Dave -
>
> Although what u have posed is correct to an extent but this will also
> include cases where the line joining the points are parallel and not
> collinear
> So we will have to impose a check for one of the points involved
> in every two same slopes to be coincident.
>
> Do correct me if i am wrong..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: DP

2010-10-13 Thread Gene
The example I did by hand was { 3,7,2,1 }.  Here the answer is 8.

My code I ran on 2,5,7,1,8,9.  This produces 18 if you run it.  See
http://codepad.org/FW0Y4rL7 .

Both are correct as far as I can see.  Sorry for the confusion.

On Oct 9, 12:56 am, Lego Haryanto  wrote:
> I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 }
> should be 18, right?
>
>
>
>
>
> On Thu, Oct 7, 2010 at 10:53 PM, Anand  wrote:
> > Using standard Dynamic Programing logic:
> >http://codepad.org/IwBTor4F
>
> > On Thu, Oct 7, 2010 at 8:43 PM, Gene  wrote:
>
> >> Nice problem.  Let N_1, N_2, ... N_n be the values of the N notes.
> >> Let F(i,j) be the maximum possible score the current player can get
> >> using only notes i through j.  Then
>
> >> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) )
>
> >> This is saying that the current player always makes the choice that
> >> minimizes B the best score that the other player can achieve.  When we
> >> know that choice, the best _we_ can do is the sum of all the available
> >> notes minus B.
>
> >> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j)
> >> where i > j.
>
> >> For example, suppose we have notes 3 7 2 1 .  The answer we want is
> >> F(1,4).
>
> >> Initially we have
> >> F(1,1) = 3
> >> F(2,2) = 7
> >> F(3,3) = 2
> >> F(4,4) = 1
>
> >> Now we can compute
> >> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7).
> >> F(2,3) =  9 - min(F(3,3), F(2,2)) =  9 - min(2,7) = 7 (pick N_2=7).
> >> F(3,4) =  3 - min(F(4,4), F(3,3)) =  3 - min(1,2) = 2 (pick N_3=2).
> >> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care).
> >> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7).
> >> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1).
>
> >> On Oct 7, 8:14 pm, Anand  wrote:
> >> > Given a row of notes (with specified values), two players play a game.
> >> At
> >> > each turn, any player can pick a note from any of the two ends. How will
> >> the
> >> > first player maximize his score? Both players will play optimally.
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com >>  .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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum set of Collinear points

2010-10-13 Thread Gene
There are only O(n^2) pairs of points.  So compute the normalized
coefficients (A,B,C) of the line passing through each pair: Ax + By +
C = 0 where sqrt(A^2 + B^2) = 1 and either A>0 or (A=0 and B = 1).
This is simple algebra.   Now you can hash all the points in the pairs
using their (A,B,C) triples as keys.  This will give you equivalence
classes of points. The largest equivalence class is your answer, and
you'll have it in O(n^2) time.

The interesting thing is to consider whether it can be done in less
than O(n^2)...

On Oct 13, 5:52 am, Mridul Malpani  wrote:
> There are n points in 2d space.we have their (x,y) co-ordinates. you
> have to find the maximum set of points that are colinear?
> I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
> n^2).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] spoj-party problem

2010-10-13 Thread Devendra Pratap Singh
Replace

 if(x>=y)
 {
  m[i][j]=x;
 //cost=wt[i];
 ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
  }

with

if(x>y){
  m[i][j] = x;
  ans[i][j] = wt[i]+ans[i-1][j-wt[i]];
}else if(x==y){
 m[i][j] = x;
 ans[i][j] = min(ans[i-1][j] , ans[i-1][j-wt[i]]+wt[i]);
}


try it  






On Wed, Oct 13, 2010 at 9:35 AM, keyankarthi wrote:

> hey guys.., i tried solving this problem
> http://www.spoj.pl/problems/PARTY/
> i get answer for the test cases that i try.. getting WA in the judge..
> can anyone help me out here.. my code is as follows..
>
> #include
> #include
> using namespace std;
>
> int m[150][150],v[150],wt[150],ans[150][150];
> void dp(int weight,int n)
> {
>int i,j,x,y,anscount=0;
>for(i=0;i<=weight;i++)
>m[0][i]=0;
>for(i=1;i<=n;i++)
>ans[0][i]=0;
>
>for(i=1;i<=n;i++)
>{
>for(j=0;j<=weight;j++)
>{
>if(wt[i]<=j)
>{
>x=(v[i]+m[i-1][j-wt[i]]);
>y=(m[i-1][j]);
>if(x>=y)
>{
>m[i][j]=x;
>//cost=wt[i];
>ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
>}
>else
>{
>m[i][j]=y;
>ans[i][j]=ans[i-1][j];
>}
>}
>else
>{
>m[i][j]=m[i-1][j];
>ans[i][j]=ans[i-1][j];
>}
>}
>}
>printf("%d %d",ans[n][weight],m[n][weight]);
> }
>
> int main()
> {
>
>int weight,no,i,j;
>while(1)
>{
>scanf("%d %d",&weight,&no);
>if(!weight && !no)
>break;
>for(i=1;i<=no;i++)
>scanf("%d %d",&wt[i],&v[i]);
>dp(weight,no);
>}
> }
>
> thanks,
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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.
>
>


-- 
Devendra Pratap Singh
B.Tech (IT)
IIIT - Allahabad

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum set of Collinear points

2010-10-13 Thread Asquare
@Dave -

Although what u have posed is correct to an extent but this will also
include cases where the line joining the points are parallel and not
collinear
So we will have to impose a check for one of the points involved
in every two same slopes to be coincident.

Do correct me if i am wrong..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: first unrepeated char

2010-10-13 Thread Asquare
Thanks  :)
This is definitely a much better option than O(mn)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: plz explain output

2010-10-13 Thread Asquare
@Nidhi -

I guess thats correct.. but am still not 100% sure about how the
explanation goes..
 Actually printf() is a variable argument function and so the
acceptance of a value of a data type depends on the way it is defined
in the library..
and since %f if encountered in the string must be replaced by a float
value (as defined since it can be anything - VARIABLE)
so the function (as we see the way it works) expects a float value..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] Modify Queue Data Structure which returns min in O(1) time.

2010-10-13 Thread AlgoSau Sau
Similar question was posted sometime back but the DS in question was stack.
please look in to the existing topics to look for the solution to your
problem.

On Thu, Oct 14, 2010 at 12:13 AM, rahul  wrote:

> it look like a priority queue type of DS to me
> well min-heap is another solution,which do the heap process at each
> insertion and deletion,so that min element stay the root position.
>
> comments invited.
>
> regards.
>
>
> On Wed, Oct 13, 2010 at 11:52 PM, malli  wrote:
>
>> A queue data structure has functions enqueue(int x) ( inserts element
>> in right end), dequeue() ( deletes element from left end) functions.
>> These operations take O(1) time. Modify this queue data structure, so
>> that  it supports findmin() which returns minimum element of stack in
>> O(1) time.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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] Modify Queue Data Structure which returns min in O(1) time.

2010-10-13 Thread rahul
it look like a priority queue type of DS to me.
well min-heap is another solution,which do the heap process at each
insertion and deletion,so that min element stay the root position.

comments invited.

regards.

On Wed, Oct 13, 2010 at 11:52 PM, malli  wrote:

> A queue data structure has functions enqueue(int x) ( inserts element
> in right end), dequeue() ( deletes element from left end) functions.
> These operations take O(1) time. Modify this queue data structure, so
> that  it supports findmin() which returns minimum element of stack in
> O(1) time.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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] Modify Queue Data Structure which returns min in O(1) time.

2010-10-13 Thread malli
A queue data structure has functions enqueue(int x) ( inserts element
in right end), dequeue() ( deletes element from left end) functions.
These operations take O(1) time. Modify this queue data structure, so
that  it supports findmin() which returns minimum element of stack in
O(1) time.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: spoj problem BOTTOM

2010-10-13 Thread Ruturaj
I didnt understand the above solution, but I have a bad complexity
solution.
Make an nXn boolean adjacency matrix.
Run transitivy closure on the matrix.
For every node w, check if for all v E V, w->v=> v->w

On Oct 13, 9:52 pm, praba karan  wrote:
> spoj.pl/problems/BOTTOM
>
> my algo for this prob goes by this way..will this work correctly?
>
> 1)first make a bfs from an arbitrary node and store the nodes visited
> in order in an array.
>
> 2)the node that is visited at the end of the BFS in the 1st bfs is now
> taken as the root and then make a BFS from this node and store the
> nodes visited in order in an array.
>
> 3)reverse the array in step 2
>
> 4)find the Longest Common Subsequence between the arrays in step 1 and
> step 3
>
> 5)if any one of the array is empty,then all the other nodes in the
> other array sud b printed.
>
> will this logic work?
>
> any other ideas are welcomed...
>
> praba...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] spoj problem BOTTOM

2010-10-13 Thread praba karan
spoj.pl/problems/BOTTOM

my algo for this prob goes by this way..will this work correctly?

1)first make a bfs from an arbitrary node and store the nodes visited
in order in an array.

2)the node that is visited at the end of the BFS in the 1st bfs is now
taken as the root and then make a BFS from this node and store the
nodes visited in order in an array.

3)reverse the array in step 2

4)find the Longest Common Subsequence between the arrays in step 1 and
step 3

5)if any one of the array is empty,then all the other nodes in the
other array sud b printed.

will this logic work?

any other ideas are welcomed...

praba...

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] regarding output

2010-10-13 Thread albert theboss
p[b] is equivalent to *(p+b)

here p is converted to the void pointer pointing to address location 0x0003

then the pointer value is added by the offset b which is 8 here .

8+3 giving 11


this is one of the method of finding the sum of two numbers without using
addition operator

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: sorted array

2010-10-13 Thread AlgoSau Sau
let the numbers be i1,i2,i3i8


Array A has to contain 5 sorted numbers..
So basically u have to make 5 choices among given 8. Standard formula of it
is 8C5 (8!/(3! * 5!)).

After creating array A there will be 3 elements left which will suffice to
create array B (no choice is left in this case so it will be 1C1=1).

No shuffling among the numbers in array A and B will be there as numbers
have to be sorted and so only one possible arrangment is possible to
maintain the array sorted.

so total number of arrangements will be 8C5 * 1C1 = 8C5= 56.



On Wed, Oct 13, 2010 at 5:25 PM, Divya Jain wrote:

> ignore the above post of mine
> @ shiyam
> u r doing wrong. we hv been the size of both array b and c which is 5 n 3
> respectively
>
> @ AlgoSAu
> can u please explain ur method?
>
>
> On 13 October 2010 17:23, Divya Jain  wrote:
>
>> @above
>> can u plz explain hw did u apply this formula?
>>
>>
>> On 13 October 2010 16:14, Shiyam code_for_life 
>> wrote:
>>
>>> Lets say 8 integers are 1 to 8
>>>
>>> So first way array can be split is 1,7
>>>
>>> 1st array can have one among 8 integers so in 8 ways and 2nd array has
>>> just one arrangement of other integers in sorted manner and same goes
>>> on for other ways to split the array.
>>>
>>> Whats wrong here?
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: remove redundantt parenthesis

2010-10-13 Thread jaladhi dave
how can once evaluate a+b, when a and b are just variables.. Its not
necessary that the expression contains all the constants.

On Wed, Oct 13, 2010 at 10:07 AM, Shiyam code_for_life <
mailshyamh...@gmail.com> wrote:

> For every pair of braces,
> Evaluate the expression within the outer braces of current braces
> under consideration
> (1)With current braces
> (2)Without current braces
>
> If both are the same, then you can drop the current braces that its
> redundant.
>
> P.S for outer most braces, evaluate the entire expression with and
> without it
>
> Ex:
> (a+[b+c])
> Here to check if square braces are redundant
> (1)Evaluate (a+[b+c]) and (a+b+c)
> (2)If both are equal then drop the braces so expression can be reduced
> as (a+b+c)
> (3)Else the braces are required so they remain as (a+[b+c])
>
> Cheers
>
> 'Coding is an art and I'm one of the finest of them'
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: sorted array

2010-10-13 Thread Divya Jain
ignore the above post of mine
@ shiyam
u r doing wrong. we hv been the size of both array b and c which is 5 n 3
respectively

@ AlgoSAu
can u please explain ur method?

On 13 October 2010 17:23, Divya Jain  wrote:

> @above
> can u plz explain hw did u apply this formula?
>
>
> On 13 October 2010 16:14, Shiyam code_for_life wrote:
>
>> Lets say 8 integers are 1 to 8
>>
>> So first way array can be split is 1,7
>>
>> 1st array can have one among 8 integers so in 8 ways and 2nd array has
>> just one arrangement of other integers in sorted manner and same goes
>> on for other ways to split the array.
>>
>> Whats wrong here?
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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: sorted array

2010-10-13 Thread Divya Jain
@above
can u plz explain hw did u apply this formula?

On 13 October 2010 16:14, Shiyam code_for_life wrote:

> Lets say 8 integers are 1 to 8
>
> So first way array can be split is 1,7
>
> 1st array can have one among 8 integers so in 8 ways and 2nd array has
> just one arrangement of other integers in sorted manner and same goes
> on for other ways to split the array.
>
> Whats wrong here?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Least fare for a return trip Algorithm

2010-10-13 Thread AlgoSau Sau
Although no inputs are given on flight timing (date and time) front but that
is one more factor that should be considered while scheduling the cheapest
round trip journey as it happens on travel sites normally

On Wed, Oct 13, 2010 at 2:56 PM, Shiyam code_for_life <
mailshyamh...@gmail.com> wrote:

> When a user wants to choose to fly from A to B, suggest the flight
> with lowest fare that's available, here its A1, if A1 is busy then A2
> and so on
> Repeat the same for B to A.
>
> Am I missing something here?
>
> Complexity is O( (number of flights from A to B) + number of flights
> from B to A) )
>
> Cheers
>
> 'Coding is an art'
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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] plz explain output

2010-10-13 Thread Lily Aldrin
How is the link you gave related to the output question here??

On Wed, Oct 13, 2010 at 7:20 PM, dinesh bansal  wrote:

> check http://en.wikipedia.org/wiki/NaN
>
> On Sat, Oct 9, 2010 at 6:15 PM, ankush  wrote:
>
>> #include
>> void main()
>> {
>>int x;
>>float t;
>>scanf("%f",&t);
>>printf("%f\n",t);
>>x=90;
>>printf("%f\n",x);
>>{
>>x=1;
>>printf("%f\n",x);
>>{
>>x=30;
>>printf("%d\n",x);
>>}
>>printf("%f\n",x);
>>}
>>x=9;
>>printf("%f\n",x);
>> }
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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.
>>
>>
>
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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 puzzle

2010-10-13 Thread nidhi gupta
No

const char * p is a pointer to a constant string, and is not itselves a
constant pointer!

On Sun, Oct 10, 2010 at 11:41 AM, Harshal  wrote:

> @Soumya
> Typedef merely adds a new name for some existing type, here for char* type
> in your code.
> So instead you should write *typedef const char* char*p rather than *typedef
> char* char*p. bcoz you want new name for the whoole thinge (const char*),
> not just char*.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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] plz explain output

2010-10-13 Thread dinesh bansal
check http://en.wikipedia.org/wiki/NaN

On Sat, Oct 9, 2010 at 6:15 PM, ankush  wrote:

> #include
> void main()
> {
>int x;
>float t;
>scanf("%f",&t);
>printf("%f\n",t);
>x=90;
>printf("%f\n",x);
>{
>x=1;
>printf("%f\n",x);
>{
>x=30;
>printf("%d\n",x);
>}
>printf("%f\n",x);
>}
>x=9;
>printf("%f\n",x);
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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.
>
>


-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] spoj-party problem

2010-10-13 Thread keyankarthi
hey guys.., i tried solving this problem   http://www.spoj.pl/problems/PARTY/
i get answer for the test cases that i try.. getting WA in the judge..
can anyone help me out here.. my code is as follows..

#include
#include
using namespace std;

int m[150][150],v[150],wt[150],ans[150][150];
void dp(int weight,int n)
{
int i,j,x,y,anscount=0;
for(i=0;i<=weight;i++)
m[0][i]=0;
for(i=1;i<=n;i++)
ans[0][i]=0;

for(i=1;i<=n;i++)
{
for(j=0;j<=weight;j++)
{
if(wt[i]<=j)
{
x=(v[i]+m[i-1][j-wt[i]]);
y=(m[i-1][j]);
if(x>=y)
{
m[i][j]=x;
//cost=wt[i];
ans[i][j]=wt[i]+ans[i-1][j-wt[i]];
}
else
{
m[i][j]=y;
ans[i][j]=ans[i-1][j];
}
}
else
{
m[i][j]=m[i-1][j];
ans[i][j]=ans[i-1][j];
}
}
}
printf("%d %d",ans[n][weight],m[n][weight]);
}

int main()
{

int weight,no,i,j;
while(1)
{
scanf("%d %d",&weight,&no);
if(!weight && !no)
break;
for(i=1;i<=no;i++)
scanf("%d %d",&wt[i],&v[i]);
dp(weight,no);
}
}

thanks,

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum set of Collinear points

2010-10-13 Thread Dave
@Sudheer: We don't need to do any extra work to eliminate it. It is a
smaller set than the previous max found, so we don't have to consider
it further. The problem says "the maximum set," and doesn't specify
what to do in the case of ties. Since apparently one answer is
expected, I assume that it means "a maximal set," so you can ignore
any set that is not larger than the current max.

Dave

On Oct 13, 6:41 am, sudheer babu  wrote:
> suppose after caliculating slopes for ist point we formed set points(n=9)
> whose slopes are eequal are
> {1,2,3,4},{1,5,6,7,9},{1,}.
> now for second point we will definitely get 1 set{1,2,3,4}and some other and
> we have to eliminate this set
> it takes some more time
>
>
>
> On Wed, Oct 13, 2010 at 5:52 PM, Dave  wrote:
> > @Mridul: For each point i, find the slope to every other point j and
> > look for duplicates. Duplicates can be found by sorting the slopes and
> > comparing adjacent values. Point i is collinear with the points in
> > each set of duplicates. Keep track of the maximal set as you go.
>
> > For each i, you have n-1 slopes to calculate and sort and compare.
> > Therefore, using a log n sort, the complexity of the algorithm is
> > O(n^2 log n).
>
> > Dave
>
> > On Oct 13, 4:52 am, Mridul Malpani  wrote:
> > > There are n points in 2d space.we have their (x,y) co-ordinates. you
> > > have to find the maximum set of points that are colinear?
> > > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
> > > n^2).
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@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.- Hide quoted text -
>
> - Show quoted text -

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum size binary search tree

2010-10-13 Thread sudheer babu
in the gopinath solution we need to maintain another array and it
contains the maximum bst constructed so far...
when len is updated this array also updated to contain the present
queue values...

On Aug 15, 11:57 am, Ankit Singh  wrote:
> Space complexity- O(n), Time - O(n2).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Maximum set of Collinear points

2010-10-13 Thread sudheer babu
suppose after caliculating slopes for ist point we formed set points(n=9)
whose slopes are eequal are
{1,2,3,4},{1,5,6,7,9},{1,}.
now for second point we will definitely get 1 set{1,2,3,4}and some other and
we have to eliminate this set
it takes some more time

On Wed, Oct 13, 2010 at 5:52 PM, Dave  wrote:

> @Mridul: For each point i, find the slope to every other point j and
> look for duplicates. Duplicates can be found by sorting the slopes and
> comparing adjacent values. Point i is collinear with the points in
> each set of duplicates. Keep track of the maximal set as you go.
>
> For each i, you have n-1 slopes to calculate and sort and compare.
> Therefore, using a log n sort, the complexity of the algorithm is
> O(n^2 log n).
>
> Dave
>
> On Oct 13, 4:52 am, Mridul Malpani  wrote:
> > There are n points in 2d space.we have their (x,y) co-ordinates. you
> > have to find the maximum set of points that are colinear?
> > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
> > n^2).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: Maximum set of Collinear points

2010-10-13 Thread Dave
@Mridul: For each point i, find the slope to every other point j and
look for duplicates. Duplicates can be found by sorting the slopes and
comparing adjacent values. Point i is collinear with the points in
each set of duplicates. Keep track of the maximal set as you go.

For each i, you have n-1 slopes to calculate and sort and compare.
Therefore, using a log n sort, the complexity of the algorithm is
O(n^2 log n).

Dave

On Oct 13, 4:52 am, Mridul Malpani  wrote:
> There are n points in 2d space.we have their (x,y) co-ordinates. you
> have to find the maximum set of points that are colinear?
> I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
> n^2).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: output for optimal binary search tree

2010-10-13 Thread Shiyam code_for_life
Can you be clear here? There is no difference in printing a binary
tree whether its optimized or not!
Or am I missing something here?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: sorted array

2010-10-13 Thread Shiyam code_for_life
Lets say 8 integers are 1 to 8

So first way array can be split is 1,7

1st array can have one among 8 integers so in 8 ways and 2nd array has
just one arrangement of other integers in sorted manner and same goes
on for other ways to split the array.

Whats wrong here?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Smallest window of K[] in N[]. Best order solution

2010-10-13 Thread Mridul Malpani
@ ankit agarwal, you are right. thanx man.

On Oct 13, 11:37 am, prodigy <1abhishekshu...@gmail.com> wrote:
> Let I,Q be input array,query array respectively.
>
> 1. Sort query array. O(klogk)
> 2. Allocate an array A of size N.
> 3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in
> I.  O(nlogk)
> 4. Allocate an array B of size k with all elements initiated to -1.
> 5. for(counter=0,i=0,counter     {
>           if(B[i]==-1)
>                counter++;
>           if(A[i]!=-1)
>                  B[A[i]] = i
>      }
> 6. Build min-heap of B.(use an auxiliary array  C to keep track of
> position of last occurence of an element of Q in min-heap B.)
> 7. for(diff=i-B[1] ; i            if(A[i]!=-1)
>                   B[C[A[i]] = i
>                   //percolate up or down if needed
>             diff=max(diff,i-B[1]);
>
> 8. print    diff
>
> On Oct 7, 1:20 pm, RAHUL KUJUR  wrote:
>
>
>
> > @prodigy: how is it coming O(nlogk) can u explain???

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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] Maximum set of Collinear points

2010-10-13 Thread Mridul Malpani
There are n points in 2d space.we have their (x,y) co-ordinates. you
have to find the maximum set of points that are colinear?
I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
n^2).

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm

2010-10-13 Thread Shiyam code_for_life
When a user wants to choose to fly from A to B, suggest the flight
with lowest fare that's available, here its A1, if A1 is busy then A2
and so on
Repeat the same for B to A.

Am I missing something here?

Complexity is O( (number of flights from A to B) + number of flights
from B to A) )

Cheers

'Coding is an art'

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: first unrepeated char

2010-10-13 Thread Shiyam code_for_life
(1) Take a hash table of all characters
(2) Initialize them to 0
(3) For each character
  (3.1) If hash[character] == 0 then hash[character]=current loop
index  #Appearing for first time so store index at which it
appears
  (3.2) elsif hash[character] > 0 then hash[character]=-1
#Already occurred so reject it
(4) Loop through the hash table, the element with lowest positive
value is the first unrepeated character

Time complexity : O(n)


Tips:

If hash[character] is 0 then character has never occurred
if hash[character] is > 0 then character has occurred once at position
which is stored as hash value
if hash[character] is -1 then it has repeated.

'Coding is an art'

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: first unrepeated char

2010-10-13 Thread Shiyam code_for_life
(1) Take a hash table of all characters
(2) Initialize them to 0
(3) For each character
  (3.1) If hash[character] == 0 then hash[character]=current loop
index  #Appearing for first time so store index at which it
appears
  (3.2) elsif hash[character] > 0 then hash[character]=-1
#Already occurred so reject it
(4) Loop through the hash table, the element with lowest positive
value is the first unrepeated character

Time complexity : O(n)


Tips:

If hash[character] is 0 then character has never occurred
if hash[character] is > 0 then character has occurred once at position
which is stored as hash value
if hash[character] is -1 then it has repeated.

'Coding is an art'

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: sorted array

2010-10-13 Thread AlgoSau Sau
Read the question again..only 3rd case you have mentioned needs t

On Wed, Oct 13, 2010 at 12:58 PM, Shiyam code_for_life <
mailshyamh...@gmail.com> wrote:

> First lets look at how many ways the array can be split
> (1) 1,7
> (2) 2,6o be considered here...
> (3) 3,5
> (4) 4,4
>
> Now how many combinations in each
>
> 1,7 => 8 combinations for first array
> 2,6 => 8*7 combinations for first array
> 3,5 => 8*7*6 combinations for first array
> 4,4 => 8*7*6*5 combinations for first array
>
> so its the sum (8) + (8*7) + (8*7*6) + (8*7*6*5)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: sorted array

2010-10-13 Thread Shiyam code_for_life
First lets look at how many ways the array can be split
(1) 1,7
(2) 2,6
(3) 3,5
(4) 4,4

Now how many combinations in each

1,7 => 8 combinations for first array
2,6 => 8*7 combinations for first array
3,5 => 8*7*6 combinations for first array
4,4 => 8*7*6*5 combinations for first array

so its the sum (8) + (8*7) + (8*7*6) + (8*7*6*5)

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: Bee Maja spoj

2010-10-13 Thread Shiyam code_for_life

Ruby simple code(ruby is so damn readable)
pos[0]=x pos[1]=y
just pass the value u wanna convert to translate function, logic is
quite clean :)


step=10
print translate(step)

def move(pos,direction)
case direction
when :down
pos[1]+=1
when :left
pos[0]-=1
when :up
pos[1]-=1
when :right
pos[0]+=1
when :diagup
pos[0],pos[1]=pos[0]+1,pos[1]-1
when :diagdown
pos[0],pos[1]=pos[0]-1,pos[1]+1
end
end

def translate(steps)
guide=[:left,:up,:diagup,:right,:down,:down,:diagdown]
pos=[0,0]
move(pos,:down)
(steps-1).times{|i|
move(pos,guide[i%7])
}
return pos
end

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.