Westlake
BAN USERSort the array so that x_1 <= x_2 <= …. <= x_n. Now the problem is reduced to partitioning number N into K positive numbers a_1, a_2, …., a_K. From the partition we can construct a grouping: First we pick up a_1 numbers from x_1 to x_a for the first group, next we pick another a_2 numbers from x_(a1+1) ….x_(a2+a1), and this process continues. The problem can be reduced into a DP problem:
F(i, N, K) = 0 if K>=N, or K==0
F(i, N, K) = min_j (max(x[i+j]  x[i], F(i+j+1, Nj, K1))) for 0<= j < N  K

Westlake
February 01, 2014 Suppose the distance of loop entry from the starting point is A, and the loop size is B, and the speed ration of the slow and fast pointers is 1:N.
At A'th step the slow pointer reaches the entry, while the fast pointer is
behide the slow pointer by distance X.
X = (B  ((N  1) * A) % B)) % B // note 0<=X<B1
It will take floor (X / (N  1)) steps for the fast pointer to catch the slow pointer.
The total cost is
Y = (A + floor(X / (N 1)) * (N + 1)
Obviously
A * (N + 1) <= Y <= (A + floor ((B  1) / N  1)) * (N + 1)
Since the lower bound is A * (N + 1), we should make N as small as possible.
For curious readers the upper bound is
(A + floor ((B  1) / N  1)) * (N + 1) < (A + 1 + (B1)/(N1))*(N+1)
= (A+1)*(N+1) + (B1)(1 + 2/(N1))

Westlake
January 31, 2014 At time i we read the i'th line. We pick this line with the possibility 1/i. If this line is not selected, nothing needs to be done later for this line. At time (i+1) we rechoose the i'th line with possibility i/(i+1), so that the possibility to keep the i'th line at time (i+1) is 1/i * i / (i+1) = 1/(i+1).
This process can be continued until we reach the end of the file. For the lines kept we can randomly pick one.
How about this:
#include <iostream>
#include <limits.h>
using namespace std;
#define INCR(x) if((x)!= INT_MAX)(x)++;
int main()
{
int p1 = INT_MAX;
int p2 = INT_MAX;
int d = INT_MAX;
string word;
while (cin >> word) {
if (word == "hello")
p1 = 0;
else if (word == "you")
p2 = 0;
if (p1 != INT_MAX && p2 != INT_MAX) {
d = min(d, p1  p2);
}
INCR(p1);
INCR(p2);
}
cout << "distance = " << d << endl;
}

Westlake
January 29, 2014 Open Chat in New Window
 Westlake February 03, 2014