Форум DL
Автор Сообщение
Михаил Долинский

Темы: 1440
Сообщений: 34071

(Analysis by Dhruv Rohatgi )
http://usaco.org/current/data/sol_train_platinum_open18.html

In this problem, we are asked to find all sliding-window minima in an array, for some fixed-length window. We are given two passes through the array. The catch is that we are given only O(vN) memory.

Let f(i) be the location of the smallest element in the range [i,i+K), breaking ties by smallest index. Observe that f(i)?f(i+1) for each i. So if we compute f(0),f(B),f(2B),…,f(N) for some block size B in the first pass, this gives us some information which we may be able to use in the second pass to compute the remaining f(i)s.

Let's ignore the constraint on calls to set/get for now. If we let B=vN, then we can compute f(0),f(vN),…,f(N) in our first pass using only O(vN) memory and O(NvN) time. Now, in the second pass, observe that for any fixed array element i, there are only O(vN) windows for which the minimum could possibly be at position i.

This suggests the following algorithm for the second pass: read and ignore all elements with index less than f(0). Now maintain running minima for f(0),f(1),f(2),…,f(vN). Once we've read in the element with index f(vN), we know that we have computed the correct minima for the first vN windows. Output these, start maintaining minima for the next vN windows, and continue in the same fashion.

The memory usage of the second pass is also vN, as desired. Unfortunately, the time complexity of each pass is O(NvN). In particular, the above algorithm would use O(NvN) calls to set and get, which would exceed the given bound. To improve the time complexity, we can use a monotonic queue in each pass. In the first pass, for instance, the boundaries of the vN windows define 2vN subarrays, and for each subarray we can simply compute the minimum of the subarray and put that into the monotonic queue. The length of the monotonic queue therefore never exceeds O(vN), and we can compute the vN minima-locations in O(N) time. For the second pass, it suffices to observe that in each segment of the array (say, between f(ivN) and f((i+1)vN)) all but O(vN) of the array elements are in all vN windows of interest. This once again allows us to improve the pass to O(N) time will not exceeding O(vN) memory.

Below is an implementation of the above algorithm.

#include "grader.h"
#define BLOCK 1000
#define DIF 4050

// VARIABLE - LOCATION IN BESSIE'S NOTEBOOK
// back index - 0
// top index - 1
// queue (2,3) (4,5) ...
//       (index, value)
// current block's endpoint index (divided by BLOCK) - DIF-1
// current block's global low - DIF-2
// number of minima output - DIF-3

void helpBessie(int v)
{
int N = getTrainLength();
int K = getWindowLength();
int i = getCurrentCarIndex();
int p = getCurrentPassIndex();
if(p==0)
{
if(i==0)
{
set(0,0);
set(1,-1);
}
int top = get(1);
int back = get(0);
if(i%BLOCK == 0 || (i>=K && (i-K)%BLOCK == 0))  // reached boundary of some window
{						// need to make new entry in monotonic queue
while(top >= back && get(2*top+3) >= v)
top--;
top++;
set(2*top+2,i);
set(2*top+3,v);
}
else	//still part of same subarray; just update the top entry of monotonic queue
{
int curTopValue = get(2*top+3);
if(v <= curTopValue)
{
top--;
while(top >= back && get(2*top+3) >= v)
top--;
top++;
set(2*top+2,i);
set(2*top+3,v);
}
}
if(i >= K-1 && (i+1-K)%BLOCK == 0)	// at endpoint of some window; need to store location of minimum
{
while(top >= back && get(2*back+2) <= i-K)	// pop from back end up queue until queue contains only
back++;					// elements in desired window
set(DIF + (i+1-K)/BLOCK, get(2*back+2));	// store location of minimum
}
set(0,back);
set(1,top);
}
else
{
if(i < get(DIF))
return;
if(i == get(DIF))
{
set(0,0);
set(1,-1);
set(DIF-1, 1);
set(DIF-2,1000000000);
set(DIF-3, 0);
}
int bc = get(DIF-1);
int top = get(1);
int back = get(0);
int outputs = get(DIF-3);
if(i - get(DIF+bc-1) <= BLOCK)  // element may not be contained in all relevant windows
{				// so add to monotonic queue
while(top >= back && get(2*top+3) >= v)
top--;
top++;
set(2*top+2,i);
set(2*top+3,v);
}
else 	// element is contained in all relevant windows
{	// so we can update a global minimum
int globalLow = get(DIF-2);
if(v < globalLow)
set(DIF-2,v);
}
if(outputs + K - 1 == i)	//need to output a minimum
{
while(top >= back && get(2*back+2) < outputs)
back++;
shoutMinimum(min(get(DIF-2),get(2*back+3)));
outputs++;
}
while(BLOCK*bc + K-1 < N && get(DIF+bc) == i) // reached boundary of current subarray
{
while(outputs <= BLOCK*bc) // output minimums for all remaining windows in current block
{
while(top >= back && get(2*back+2) < outputs)
back++;
shoutMinimum(min(get(DIF-2),get(2*back+3)));
outputs++;
}
bc++;
set(DIF-2,1000000000);
top = back = 0;
set(2*top+2,i);
set(2*top+3,v);
}
set(DIF-3,outputs);
set(DIF-1,bc);
set(1,top);
set(0,back);
}
}

 Time:0,031