nice solution..
On Sun, Jan 30, 2011 at 11:51 PM, Wei.QI wrote:
> here is the code:
> public int findStartPumpIndex(int[][] pumpDistance){
> int leftGas = 0;
> int start = 0;
> //Find the potential start
> for(int i=0; i int addGas = pumpDistance[i][0];
> int consumeGas = pumpDistance[i][1
@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 becau
here is the code:
public int findStartPumpIndex(int[][] pumpDistance){
int leftGas = 0;
int start = 0;
//Find the potential start
for(int i=0; i= 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;
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
[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 m
It's not right.
On Sun, Jan 30, 2011 at 4:19 PM, Nich01as 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
>
@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 w
@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 wrote:
> can you prove it?
>
> On Jan 29, 2011 6:38 PM, "Wei.QI" wrote:
> >
> > Starting with any pump A, try to finish the circle, if at pum
can you prove it?
On Jan 29, 2011 6:38 PM, "Wei.QI" 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 pum
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
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 wrote:
> There are N petrol pumps along a circular path. Every petrol pump
> gives some amount of fixed p
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
@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 unsubsc
@jammy: Sorry for wrong answer
thats O(n^3 *lg(K))
On Thu, Jan 13, 2011 at 12:28 AM, Jammy 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-an
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
15 matches
Mail list logo
