Re: [algogeeks] Re: Amazon Again
nice solution..
On Sun, Jan 30, 2011 at 11:51 PM, Wei.QI qiw...@gmail.com wrote:
here is the code:
public int findStartPumpIndex(int[][] pumpDistance){
int leftGas = 0;
int start = 0;
//Find the potential start
for(int i=0; ipumpDistance.length; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left = 0){
leftGas = left;
}else {
leftGas = 0;
start = i+1;
}
}
//if we failed find a start at last, not solution
if(start = pumpDistance.length)
return -1;
//otherwise continue to go, until back to start
for(int i=0; istart; i++){
int addGas = pumpDistance[i][0];
int consumeGas = pumpDistance[i][1];
int left = leftGas + addGas - consumeGas;
if(left 0){
leftGas = left;
}else {
return -1;
}
}
return start;
}
On Sun, Jan 30, 2011 at 9:55 AM, Wei.QI qiw...@gmail.com wrote:
For any gas pump, when your car arrives, it contains 0 or more gas.
So, for each gas pump, the worst case is starting from that pump.
Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for
A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start
from Ak+1.
This could be solved in liner time. finding a possible start pump use O(n)
and prove it use another O(n).
-weiq
On Sat, Jan 29, 2011 at 9:47 PM, nishaanth nishaant...@gmail.com wrote:
@Wei.Qi Can you clarify when your algorithm terminates and also what
is the running time of the algorithm ?
On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.comwrote:
can you prove it?
On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote:
Starting with any pump A, try to finish the circle, if at pump B that
can not reach pump B+1, it means all pumps from A to B can not finish the
circle (it will go broke at pump B), then just start with B+1. After go
through all the pumps start from some pump, we got an answer. if we go back
to pump A and later, still can not find an answer, there is no answer.
On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava
richi.sankalp1...@gmail.com wrote:
I'm sure you have misstated the problem statement
just find out the total path length and return the first petrol pump
which gives you the required milage
go greedy
On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote:
There are N petrol pumps along a circular path. Every petrol pump
gives some amount of fixed petrol. Need not to be unique and in no
particular order means it is random. We have a car and we need to
find
a petrol pump which can provide so much of petrol that we can take
a
full of the circle. Mileage of car is fixed.
Distance between adjacent petrol pumps are given.
Thanks Regards
Shashank
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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
[algogeeks] Re: Amazon Again
@wei.qui On a second thought , if the petrol pumps have many petrol pumps connected to it , we cannot find the answer your way or the method suggested by me previously . Thus , the solution becomes one to find out the Eulerian Path (constraint based of course ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
@Wei.Qi the algorithm is right, but the running time is ...? define Pi the amount of petrol each pumps has. Di is the distance between Ith and i+1th pumps. then we can double the circle, we can get to sequence p1, p2, p3, p4...pn, p1, p2, p3..pn d1, d2, d3, d4...dn, d1, d2, d3..dn the problem will become to find a subsequence in above sequences with length N where sum(P(start, start+i)) = sum(D(start, start+i)) for any 0=iN. change those two sequences to below one. p1-d1, p1+p2-d1-d2, p1+p2+p3-d1-d2-d3 . p1+p2+..+p2-d1-d2...-dn make the sequence as s1, s2, s3, s4...sn, s1, s2..sn finally the problem becomes to find a subsquence in Sn start at element j where S(j+i) = Sj and Sj = 0. So it can be solved in NlogN On Sun, Jan 30, 2011 at 1:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Southeast University Nicholas.Zhaoyu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
It's not right. On Sun, Jan 30, 2011 at 4:19 PM, Nich01as nicholas.zha...@gmail.com wrote: @Wei.Qi the algorithm is right, but the running time is ...? define Pi the amount of petrol each pumps has. Di is the distance between Ith and i+1th pumps. then we can double the circle, we can get to sequence p1, p2, p3, p4...pn, p1, p2, p3..pn d1, d2, d3, d4...dn, d1, d2, d3..dn the problem will become to find a subsequence in above sequences with length N where sum(P(start, start+i)) = sum(D(start, start+i)) for any 0=iN. change those two sequences to below one. p1-d1, p1+p2-d1-d2, p1+p2+p3-d1-d2-d3 . p1+p2+..+p2-d1-d2...-dn make the sequence as s1, s2, s3, s4...sn, s1, s2..sn finally the problem becomes to find a subsquence in Sn start at element j where S(j+i) = Sj and Sj = 0. So it can be solved in NlogN On Sun, Jan 30, 2011 at 1:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Southeast University Nicholas.Zhaoyu -- Southeast University Nicholas.Zhaoyu -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
[quote]We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle.[/quote] So , we just need to find a petrol pump which takes you just a full circle , not anything ahead , not anything behind . 1)Sort the petrol he can get from maximum stations .If the total distance is not given , calculate this while sorting . Binary search over this array for the required distance . complexity :-O(nlogn+k) 2)Hash it !! keep a hash for all the distance in some boolean array .now find out the one which can get you the full circle , O(n) complexity . Not space efficient . 3)Using dynamic programming . dp[i][j] :-The distance we still need to cover (j) .while , we are on the started at the ith station . dp[i][0]:- answer , we need to look at the all the dp pairs for the answer . dp[i][j]= min(dp[i+next[i][j-d[i][next[i]]]) Basically a BFS . O(n^2) . worst case . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
For any gas pump, when your car arrives, it contains 0 or more gas. So, for each gas pump, the worst case is starting from that pump. Then, if we starting from pump A1, passed A2 - Ak and failed at Ak+1. for A1 to Ak, we can not pass Ak+1 starting from any of them. So we try start from Ak+1. This could be solved in liner time. finding a possible start pump use O(n) and prove it use another O(n). -weiq On Sat, Jan 29, 2011 at 9:47 PM, nishaanth nishaant...@gmail.com wrote: @Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Again
@Wei.Qi Can you clarify when your algorithm terminates and also what is the running time of the algorithm ? On Sun, Jan 30, 2011 at 9:46 AM, yq Zhang zhangyunq...@gmail.com wrote: can you prove it? On Jan 29, 2011 6:38 PM, Wei.QI qiw...@gmail.com wrote: Starting with any pump A, try to finish the circle, if at pump B that can not reach pump B+1, it means all pumps from A to B can not finish the circle (it will go broke at pump B), then just start with B+1. After go through all the pumps start from some pump, we got an answer. if we go back to pump A and later, still can not find an answer, there is no answer. On Sat, Jan 29, 2011 at 4:38 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: I'm sure you have misstated the problem statement just find out the total path length and return the first petrol pump which gives you the required milage go greedy On Jan 28, 5:09 pm, bittu shashank7andr...@gmail.com wrote: There are N petrol pumps along a circular path. Every petrol pump gives some amount of fixed petrol. Need not to be unique and in no particular order means it is random. We have a car and we need to find a petrol pump which can provide so much of petrol that we can take a full of the circle. Mileage of car is fixed. Distance between adjacent petrol pumps are given. Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
@radha krishnanan do u means this http://en.wikipedia.org/wiki/Matrix_exponential anyways got it. Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
If the matrix is diagonalizable, then it can be raised to any power in O(n^3) independent of k. Find the eigenvalue/eigenvector decomposition of the matrix, raise the eigenvalues to power k, and then multiply on the right and left by the matrix of eigenvectors and its inverse, respectively. Dave On Jan 12, 6:58 am, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Again
I think you meant n^3*log(K). Multiplication on two matrices would take O(n) per entry. And total #entries is n*n, thus multiplying 2 matrices takes O(n^3) To get a^(K), use simple divide-and-conquer technique. Since once one gets a^(K/2), to get a^(K) only needs to square it. Now we get T(K) = T(K/2)+O(multiply)---T(K) = logK*O(multiply) = n^3*logK. On Jan 12, 8:04 am, radha krishnan radhakrishnance...@gmail.com wrote: Using Matrix Exponentiation technique Complexity is n^3*(lg n) for matrix n x n we need two n x n matrix to raise the matrix to power K .. Correct me if am wronf On Wed, Jan 12, 2011 at 6:28 PM, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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 athttp://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: Amazon Again
@jammy: Sorry for wrong answer thats O(n^3 *lg(K)) On Thu, Jan 13, 2011 at 12:28 AM, Jammy xujiayiy...@gmail.com wrote: I think you meant n^3*log(K). Multiplication on two matrices would take O(n) per entry. And total #entries is n*n, thus multiplying 2 matrices takes O(n^3) To get a^(K), use simple divide-and-conquer technique. Since once one gets a^(K/2), to get a^(K) only needs to square it. Now we get T(K) = T(K/2)+O(multiply)---T(K) = logK*O(multiply) = n^3*logK. On Jan 12, 8:04 am, radha krishnan radhakrishnance...@gmail.com wrote: Using Matrix Exponentiation technique Complexity is n^3*(lg n) for matrix n x n we need two n x n matrix to raise the matrix to power K .. Correct me if am wronf On Wed, Jan 12, 2011 at 6:28 PM, bittu shashank7andr...@gmail.com wrote: How will you raise a n x n matrix to the power k efficiently. What's the time complexity and space complexity of you algorithm? How will you optimize this? Thanks Regards Shashank Don't b Evil U Can Earn While U Learn -- 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 athttp://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.
