Nguồn đề bài: http://vn.spoj.com/problems/TNHWIFI/
1. Đề bài TNHWIFI spoj
Trong một thành phố, người ta thấy có M con đường song song theo hướng đông – tây và N con đường song song theo hướng bắc – nam, khoảng cách giữa hai con đường song song với nhau là 1. Tại mỗi giao lộ đều có một quán cafe. K quán cafe trong số này là cafe Wifi, wifi của mỗi quán không giống nhau, wifi của quán cafe thứ i cho phép người dùng có thể truy cập trong phạm vi bán kính Ri với tốc độ đường truyền là Bi. Bởi vậy người ngồi tại một quán cafe không có wifi vẫn có thể truy cập wifi của quán cafe khác nếu cách quán cafe đó không quá Ri.
Giả sử laptop của bạn được trang bị một thiết bị đặt biệt có khả năng kết hợp tốc độ đường truyền của các quán cafe wifi mà chúng phủ sống đến địa điểm của bạn hiện tại, để nhận được đường tuyền có tốc độ bằng tổng tốc độ của các đường truyền wifi của các quán cafe đó.
Hãy xác định tốc độ đường truyền tối đa mà khi ngồi tại một quán cafe nào đó bạn có thể nhận được và đếm số lượng các quán cafe như thế.
Input
- Dòng đầu ghi số nguyên M (1<=M<=30000), là số con đường theo hướng đông – tây.
- Dòng thứ hai ghi số nguyên N (1<=N<=1000), là số con đường theo hướng bắc – nam.
- Dòng thứ ba ghi số nguyên K (1<=K<=1000), là số quán cafe wifi.
- K dòng tiếp theo mỗi dòng chứa thông tin về các quán cafe wifi gồm 4 số nguyên: x, y, R, B. Với x,y lần lượt là số thứ tự của con đường theo hướng bắc – nam, đông – tây của quán cafe wifi, R, B lần lượt là bán kính phủ sống và tốc độ của quán cafe wifi đó. (1<=x<=N, 1<=y<=M, 1<=R<=30000, 1<=B<=10000)
Output
- Dòng thứ nhất là tốc độ đường truyền tối đa mà bạn có thể nhận được.
- Dòng thứ hai là số lượng các quán cafe wifi mà tại đó bạn có thể nhận tốc độ đường truyền tối đa trên.
Example
Input:
3
5
3
1 3 2 5
3 1 2 7
5 1 1 5
Output:
12
5
2. Lời giải O(k*n*log2 R)
– Do đề bài quy định nhập cột trước vào M và nhập số dòng sau vào N, trong khi nhập tọa độ vào là nhập chỉ số dòng trước rồi đến nhập chỉ số cột, nên để đơn giản ta đọc file đảo ngược M và N, theo test ví dụ bên trên M=5, N=3.
– Nhận xét: bài này ý tưởng đơn giản nhất là xây dựng mảng A[i,j] với ý nghĩa là tổng sức mạnh wifi nơi có tọa độ i, j nhận được, sau đó tìm nơi có sức mạnh wifi mạnh nhất.
– Với ý tưởng như trên, chúng ta sẽ dễ dàng tính được mảng A bằng cách duyệt R^2 với mỗi điểm được nhập vào, bằng cách xét trong một bảng hình vuông có kích thức R*R chứa tọa độ của điểm phát sóng wifi, rồi kiểm tra từng ô trong hình chữ nhật, xem ô đó có thuộc bán kính R hay không , như vậy độ phức tạp thuật toán cho cách làm này sẽ là O(K*R^2), tương đương 9*10^11.
– Nhận xét: Ta có công thức QHĐ để tăng từ vị trí u đến vị trí v k đơn vị:
{ // tăng từ vị trí u đến v k đơn vị
F[u]:=F[u]+k;
F[v+1]:=F[v+1]-k;
}
sau khi thực hiện nhiều lần việc tăng từ đoạn u đến đoạn v bằng công thức như trên, ta chỉ cần cộng dồn mảng A(A[i]:=a[i-1]+a[i], với i=1..n) , thì mảng A sẽ đúng theo ý đồ bài toán, là tăng từ đoạn u đến đoạn v nhiều lần với độ phức tạp nhỏ nhất. O(max(n, số lượng cặp u,v)), trong khi làm bằng cách for u đến v nhiều lần thì độ phức tạp lên đến O(số lượng cặp u,v * N).
– Như vậy, với ý tưởng như trên, ta chỉ cần tìm biên của hình tròn thỏa mãn. cách thông thường là dùng 2 dòng for, nhưng chúng ta sẽ mất thêm O(R^2). Như vậy chúng ta chỉ cần chặt nhị phân. Đề bài cho chúng ta một bảng có kích thước tối đa (1000*30000) mà bán kính vào R(30000) vậy nếu 1 điểm có bán kính tối đa 30000 thì bán kính đó sẽ phủ sóng ngoài bảng M*N, Theo như dữ liệu vào thì số dòng tối đa là 1000, số cột 30000, chúng ta sẽ chặt nhị phân theo cột, độ phức tạp Log2 30000, và chặt nhị phân trên từng dòng (1000 dòng), thực hiện việc áp dụng công thức tăng từ vị trí u đến v lên k đơn vị.
Như vậy độ phức tạp ý tưởng trên cho mỗi điểm phát sóng wifi sẽ là O(M*Log2 R) tương đương O(10^4).
Lưu ý khi chặt nhị phân, chỉ cần chặt nửa bên của hình tròn, vì khoảng cách từ cột x của hình tròn có tâm (x,y) đến vị trí 2 biên trên dòng là như nhau, và từ x đến x+r sẽ thỏa mãn tính chất tăng dần để chặt nhị phân.
Ở ý tưởng trên, chúng ta chọn chặt nhị phân theo cột bởi vì, 1000(M)*Log2 30000(R) sẽ nhỏ hơn chặt nhị phân theo dòng Log2 1000(M)*30000(R).
Tổng quát ý tưởng trên, độ phức tạp thuật toán sẽ là O(K*M*log2 R) khoảng 10^7
Và ở bài toán trên chúng ta không cần khai báo dữ liệu lấn khỏi M,N một khoảng R thêm nữa, chúng ta chỉ cần ở lúc áp dụng công thức, nếu là biên bên phải thì đặt min(vt+1,n+1) với vt là vị trí biên bên phải của hình tròn, tương tự bên trái thì ta đặt max(0,vt1) với vt1 là vị trí biên bên trái của hình tròn. tương tự thì dòng chúng ta cũng chỉ duyệt trong bảng.
Sau khi thực hiện công thức cho k điểm, ta chỉ cần dùng 2 dòng for cộng dồn theo dòng như sau, và tìm kết quả bài toán trong O(M*N)
for i:=1 to m do
for j:=1 to n do
A[i,j]:=a[i,j-1]+a[i,j];
Lưu ý thêm: ở phần chặt nhị phân chúng ta không cần rút căn tính khoảng cách thật giữa 2 điểm, mà chúng ta chỉ cần bình phương bán kính R và so sánh nó với sqr(x-u)+sqr(y-v) với x,y và u,v là 2 điểm.
Lưu ý M và N ở trên đã được đọc vào khác với đề bài.
Code tham khảo cho ý tưởng trên
const fi='';
nmax=30000;
mmax=1000;
type data=longint;
var
f:text;
A:array[0..mmax+1,0..nmax+1] of int64;
n,m,k:data;
x,y:data;
r,b:int64;
function min(a,b:data):data;
begin
if a<b then exit(a);
exit(b);
end;
function max(a,b:data):data;
begin
if a>b then exit(a); exit(b);
end;
procedure add(x,y:data; r,b:int64);
var i,j,giua,dau,cuoi,vt,d,c:data;
tmp,bk:int64;
begin
bk:=r*r;
d:=max(x-r,1);
c:=min(x+r,m);
for i:=d to c do
begin
dau:=y;
vt:=y;
cuoi:=y+R+1;
while dau<=cuoi do
begin
giua:=(dau+cuoi) shr 1;
tmp:=sqr(x-i)+sqr(y-giua);
if bk=tmp then
begin
vt:=giua;
break;
end;
if bk>tmp then
begin
dau:=giua+1;
vt:=max(vt,giua);
end
else
cuoi:=giua-1;
end;
dec(a[i,min(vt+1,n+1)],b);
inc(a[i,max(y-abs(vt-y),0)],b);
end;
end;
procedure xuli;
var i,j,sl:data;
res:int64;
begin
for i:=1 to m do
for j:=1 to n do
A[i,j]:=a[i,j-1]+a[i,j];
res:=0;
sl:=0;
for i:=1 to m do
FOR J:=1 TO N DO
if res<a[i,j] then
begin
res:=a[i,j];
sl:=1;
end
else
if res=a[i,j] then
inc(sl);
writeln(res);
writeln(sl);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
read(f,n);
read(f,m);
read(f,k);
for i:=1 to m do
for j:=1 to n do
A[i,j]:=0;
for i:=1 to k do
begin
read(f,x,y,r,b);
add(x,y,r,b);
end;
close(f);
end;
begin
docfile;
xuli;
end.3. Cải tiến 2
– Ở bài trên chúng ta không cần chặt nhị phân, bởi vì ta có bán kính R, và chúng ta sẽ duyệt qua tối đa 1000 dòng, gọi dòng được xét là i, với i = x-r …x+r , dựa vào công thức pytago ta có sqrt( R^2 – (i-x)^2) chính là khoảng cách từ cột y của tọa độ I(x,y) đến biên của hình tròn có (dòng i, cột sqrt( R^2 – (i-x)^2)), như vậy độ phức tạp cho K điểm phát wifi là O(K*M) giảm được log2 30000.
const
fi='';
fo='';
nmax=30000;
mmax=1000;
type data=longint;
var
f:text;
A:array[0..mmax+1,0..nmax+1] of int64;
n,m,k:data;
x,y:data;
r,b:int64;
function min(a,b:data):data;
begin
if a<b then exit(a);
exit(b);
end;
function max(a,b:data):data;
begin
if a>b then exit(a); exit(b);
end;
procedure add(x,y:data; r,b:int64);
var i,j,giua,dau,cuoi,vt,d,c:data;
tmp,bk:int64;
begin
bk:=r*r;
d:=max(x-r,1);
c:=min(x+r,m);
for i:=d to c do
begin
vt:=y+trunc(sqrt(bk-sqr(x-i)));
dec(a[i,min(vt+1,n+1)],b);
inc(a[i,max(y-abs(vt-y),0)],b);
end;
end;
procedure xuli;
var i,j,sl:data;
res:int64;
dem:data;
begin
dem:=0;
res:=0;
sl:=0;
for i:=1 to m do
for j:=1 to n do
begin
A[i,j]:=a[i,j-1]+a[i,j];
if res<a[i,j] then
begin
res:=a[i,j];
sl:=1;
end
else
if res=a[i,j] then
inc(sl);
end;
assign(f,fo); rewrite(f);
writeln(f,res);
writeln(f,sl);
close(f);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
read(f,n);
read(f,m);
read(f,k);
for i:=1 to m do
for j:=1 to n do
A[i,j]:=0;
for i:=1 to k do
begin
read(f,x,y,r,b);
add(x,y,r,b);
end;
close(f);
end;
begin
docfile;
xuli;
end.
