Traversal solution
Marius Andrei
The idea is based on dynamic programming -- something like the number of possibilities to cross the lake with the last box being i. The first thing is to see that it doesn't matter how big H is, because after a sort, we can see in O(N) time which heights are in the range of each box.
The data structure
We compute the values we need, with the help of a data structure based on a binary tree. The structure has the ability to compute the sum from i to j on an array in O(logN) time. Also, updating a value in the array takes O(logN) time.
This structure is actually a heap (we round N to the nearest power of 2, i.e. 217). The array maps over the leaves of the heap. The root holds the sum of all leaves which is equal to the sum of its children. Its first child holds the sum of the first half of the leaves. The second holds the sum of the second half, and so on...
How do we find the sum of the values in the array from i to j ? Well, first we find the sum from 1 to j and 1 to i, and after that we subtract them. The sum from 1 to i is the sum of at most logN vertices...
How do we update the value in the array? Well, we update the value in the leaf, its parent, its parent’s parent, .... This is done by updating at most logN values in the heap.
The algorithm
We update the structure by each height, in the given order.
For each height we find the sum from I1 to I2. I1 is the shortest box that is still in the range of the box we consider, and I2 is the tallest one. This value is added to the existing value in that place.
Because of the condition to have at least 2 boxes thrown we must subtract N from the sum of all values.
So the overall complexity is O(NlogN).
The test cases were written in such manner, that the contestants would have gained points (more or less) for different complexities like: N*Hmax, N*sqrt(Hmax), N*log(Hmax), N*N, N*sqrt(N), and of course NlogN.
uses math;
const NMAX=100000;
N2N=128*1024;
MODULO=9901;
var i,j:longint;
f:text;
n,k:longint;
h,o,li,ls,inv:array[1..NMAX] of longint;
p1,p2:longint;
a:array[0..2*N2N-2] of longint;
nbn,nl2:longint;
s1,s2,poz,val,nr,rez:longint;
procedure Sort(l, r: longint);
var
i, j, x, y: longint;
begin
i := l; j := r; x := h[o[l]];
repeat
while (i<n) and ((h[o[i]]<x) or ((h[o[i]]=x) and (o[i]<o[l]))) do i := i + 1;
while (j>1) and ((x<h[o[j]]) or ((x=h[o[j]]) and (o[l]<o[j]))) do j := j - 1;
if i <= j then
begin
y := o[i]; o[i] := o[j]; o[j] := y;
i := i + 1; j := j - 1;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
procedure daval; {give a value}
var poz,i:longint;
begin
poz:=0;
val:=0;
for i:=nbn downto 0 do begin
if ((nr shr i) and 1)<>0 then begin
val:=val+a[poz];
poz:=poz*2+3;
end else poz:=poz*2+1;
end;
end;
begin
assign(f,'travers.in');reset(f);
read(f,n,k);
for i:=1 to n do read(f,h[i]);
close(f);
for i:=1 to n do o[i]:=i;
sort(1,n);
for i:=1 to n do inv[o[i]]:=i;
p1:=1;p2:=1;
for i:=1 to n do begin
while (h[o[i]]-h[o[p1]]>k) do p1:=p1+1;
while (p2<=n) and (h[o[p2]]-h[o[i]]<=k) do p2:=p2+1;
li[o[i]]:=p1;
ls[o[i]]:=p2-1;
end;
nl2:=(1 shl trunc(log2(n-1)+1));
nbn:=trunc(log2(n-1)+1);
{initializare}
for i:=0 to nl2*2-2 do a[i]:=0;
for i:=1 to n do begin
nr:=li[i]-1;
daval;
s1:=val;
nr:=ls[i];
daval;
s2:=val;
rez:=(s2-s1+1+MODULO) mod MODULO;
poz:=nl2+inv[i]-2;
a[poz]:=a[poz]+rez;
repeat
poz:=(poz-1) div 2;
a[poz]:=(a[poz]+rez) mod MODULO;
until poz=0;
end;
nr:=n;
daval;
assign(f,'travers.out');rewrite(f);
writeln(f,(val-n+100*MODULO) mod MODULO);
close(f);
end.
|