celicom
BAN USERLets put F(n) - number of 2s... Lets call F[a1,a2) - number of 2s between a1 and a2-1 and F[a1,a2] - between a1 and a2. So, F(n) == F[0,n] == F[0,n+1).
First, lets see how many 2s are in [0, 10^k].
F(10)= 1;
F(100) = F[0,10)+F[10,20)+F[20,30)+...F[90,100) = 9*F(10) + (10+F(10)) =20
F(1000) = F(100)+F[100,200)+F[200,300)+...F[900,1000) = 9*F(100) + (100+F(100)) = 300
F(10^(k+1)) = 10^k + 10*F(10^k) = 10^k +10*(10^(k-1) + 10*(...)) = (k+1)*10^k;
So, F(10^k) = k*10^(k-1).
Now, lets present number n as [a0,a1,a2,...,ak] when n = a0+a1*10+...+ak*10^k.
Then,
if(ak==0)
F([a0,a1,a2,...,0]) = F([a0,a1,a2,...,a(k-1)])
elseif(ak==1)
F([a0,a1,a2,...,1]) = F([a0,a1,a2,...,a(k-1)]) + 1*F(10^k)
elseif(ak==2)
F([a0,a1,a2,...,2]) = F([a0,a1,a2,...,a(k-1)]) + 1+[a0,a1,a2,...,a(k-1)] + 2*F(10^k)
else
F([a0,a1,a2,...,ak]) = F([a0,a1,a2,...,a(k-1)]) + 10^k + ak*F(10^k)
so...
ULONG Count2(ULONG n) {
ULONG nRet = 0;
ULONG n10deg = 1;//10^(nK-1)
ULONG nK = 0;
ULONG n1 = 0; //a mod 10^nK
while (n) {
ULONG a = n % 10;
switch (a) {
case 0: break;
case 1: nRet += nK*n10deg; break;
case 2: nRet += 1 + n1 + 2 * nK*n10deg; break;
default: nRet += n10deg + a*nK*n10deg;
}
if (nK)
n10deg *= 10;
++nK;
n1 = n1 * 10 + a;
n /= 10;
}
return nRet;
}
Here is a note why simply modified DFS/BFS/Prim span-searching algorithms are not applicable. Lets consider graph with for vertex with e1 in the middle with following (vertex,vertex,color) tripples: (e1,e2,b),(e1,e3,r),(e1,e4,b). If all these modified algorithms would start with node e4 (as a root) they will fail to find a spanning tree as node e2 may not be included. However, if we choose e3 as a root, the graph per se is a valid spanning tree. So, for any algorithm, when it chooses a starting node it should consider 2 choices: it will be the root or not. Also, while any sub-tree of the standard spanning tree is a "valid" tree, this is not true for this problem (f.e. for the sample above, the sub-tree (e1,e2,e4) is not valid sub-tree as it has only two black edges). This makes impossible to use usual recursive approach: "if we found some valid sub-tree, continue with searching sub-tree for each node for the rest of the graph's vertex".
Also, if we try for every node to assign it as a root and apply some "simply modified" standard algorithm it may fail. Here is an example, where "modified" BFS search would fail to find a valid span-tree for the graph (e1,e2,b),(e1,e3,b),(e2,e3,r),(e3,e4,b) if it starts with e1 as a root. It would accepts e2 and e3 on the first step and stops with fail on the second as e4 may not be attached to the tree. However, there exists a "valid" spanning tree with the root e1: (e1-e2-e3-e4).
I am still searching for the solution...
It is very good question as I cannot see a good/generic solution with natural limit on the resource (container's memory) while extending the parameter (get recordHit for last 5min, 5 hours, 5 years...). If there is no limit on the resource OR we presume the number of hits for the 5 min is much less than available bytes in memory, I would use (in C++/STL notation with abstract time_t type) the deque<time_t> container (called myDeque below) with a helper function to remove expired times:
void RemoveOld(time_t tm, deque<time_t>& dqTimes) {
while( !dqTimes.empty() && dqTimes.front() < tm )
dqTimes.pop_front();
}
void recordHit() {
time_t tm = --CurrentTime--;
RemoveOld(tm - 5 Min, myDeque);
myDeque.push_back(tm);
}
long getCount() {
time_t tm = --CurrentTimeMinus5Min--;
RemoveOld(tm, myDeque);
return myDeque.size();
}
Nice question. I think the presumptions should be:
1) c1 - cost of moving one step along the road
2) c2 - cost of checking the car on the same side
3) c3- cost of crossing road (to check the car on the other side).
Now, you have to find out an algorithm which gives you the minimal average cost of searching, which will be the best of all functions SearchCost(uint c1, uint c2, uint c3, int Distance, bool bSameSide), where Distance is a distance to your car from the starting point, bSameSide - true if the car is on the same side of the road as the starting point, false - opposite. Well...the answer is not trivial :-).
=========================================
Well...my second thought is - the answer IS trivial: as the car we search can be at any place in the parking with equal probability, we have just go through all parking places (as fast as possible) : go to the right to the end, switch side, go back to the end, switch side, go to the right again...
Here is a draft O(N) algo to find max{j-i,A[j]>A[i]}.
For a given array of numbers A[N] (zero based),
1) Create array B[N]. Init it the following way:
B[0] = A[0];
for(i=1;i<N;++i) B[i] = min(A[i],B[i-1]);
2) Create array C[N]. Init it this way:
C[N-1] = A[N-1];
for(i=N-2;i>=0;--i) C[i] = max(A[i],C[i+1]);
3) Let max_i_j = 0, i=j=0. Now, do this merge type of calculation on B and C:
while(j<N) do {
while(B[i] < C[j] && j<N) j=j+1;
max_i_j = max(max_i_j,j-i);
i=i+1;j=j+1;
}
===============
Each step is O(N). I am sure it can be done some more elegant way though...
Shuffling again...I suppose it is expected to get an "evenly" random array back. Rhino, could you prove your algorithm has this attribute for, lets say array of 3 elements {1,2,3}? So, you will have to show that your algo returns one of six arrays {1,2,3},{2,1,3},{2,3,1}, {1,3,2},{3,1,2} and {3,2,1} with equal probability...
- celicom December 22, 2009jialin solution will work with the few additional steps / modifications:
0.(pre-step) save information about if row0 has '1' and column0 has '1'
1. save in row0/column0 info about having at least one '1' in all rows/columns except row0 and column0 as described above
2. go through the array again except in row0 and column0 and set 1/0 in all elements
3.(post step) set corner element array[0][0] to 1 if row0 had '1' || column0 had '1'
T(n) = 4^(n-1)/n
Brute-force exact solution:
- celicom August 20, 2017