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, N-j, K-1))) for 0<= j < N - K
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<B-1
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 + (B-1)/(N-1))*(N+1)
= (A+1)*(N+1) + (B-1)(1 + 2/(N-1))
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 re-choose 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;
}
Repjuanitasfalbo45, Android Engineer at 247quickbookshelp
Hey, Juanita Falbo, and I am working as a Yoga instructor. And nowadays I am doing a new experiment on ...
RepKimDavilla, Questions - Problem Solving Round at Cavium Networks
Kim , an associate veterinarian with 4+ years of experience. Specialist in companion animal emergency and also expert at Sudoku , playing ...
- Westlake February 03, 2014