H - Pasangan Paling "Wah"
(pembahasan oleh Felix Halim)
Ada setidaknya 2 cara untuk menyelesaikan soal wah:
1. Brute Force O(N^2 * log(N))
Basically melakukan apa yang diminta oleh soal. Generate N x N co-ce pairs dan calculate wah value untuk setiap pair. Lalu sort N^2 pair ini dan iterate dari yang wah value paling besar: Untuk setiap pasangan co-ce yang masih single dua duanya, maka pasangkan (output). Cara ini tentu saja akan mendapat Time Limit Exceeded.
2. Sort O(N log N) + Greedy O(N)
Sort semua value dari co beserta index nya ascending, begitu pula untuk ce. Untuk mencetak pasangan paling wah, kita hanya perlu mengecek 2 tipe pasangan:
- co dengan value kecil dipasangkan dengan ce value besar.
- co dengan value besar dipasangkan dengan ce value kecil.
Jika ada co/ce dengan value sama, ambil yang index terkecil (jangan lupa ini!)
Dari dua kemungkinan pasangan tersebut, kita tinggal print yang pasangan wah nya terbesar. Algoritma pemasangan greedy ini jalan dalam O(N).
Implementasi pemasangan greedy ini sedikit merepotkan dalam mencari co/ce dengan value terbesar tapi memiliki index terkecil. Bagi mereka yang sudah menguasai STL, maka implementasinya akan gampang dilakukan dengan <set> of pair<int,int>. Bagi mereka yang belum menguasai STL, maka implementasinya akan sedikit lebih susah menggunakan index, dan mempunyai resiko bug yang tinggi.
| Solusi C/C++ (oleh Felix Halim) |
#include <stdio.h>
#include <stdlib.h>
int back(int X[][2], int i, int n){
while (i>0 && X[i-1][0] != -1 && X[i-1][0] == X[i][0]) i--;
if (X[i][0] != -1) return i;
if (i+1<n && X[i+1][0] != -1) return i+1;
while (i>0 && (X[i][0] == -1 || X[i-1][0] == X[i][0])) i--;
return i;
}
int X[10000][2], Y[10000][2];
int cmp(const void *a, const void *b){
int *x = (int*) a, *y = (int*) b;
if (x[0] != y[0]) return x[0] - y[0];
return x[1] - y[1];
}
int main(){
for (int n; scanf("%d",&n)!=EOF; ){
for (int i=0; i<n; i++) scanf("%d",&X[i][0]), X[i][1] = i;
for (int i=0; i<n; i++) scanf("%d",&Y[i][0]), Y[i][1] = i;
qsort(X, n, sizeof(X[0]), cmp);
qsort(Y, n, sizeof(Y[0]), cmp);
for (int i=0, x1=0, x2=n-1, y1=0, y2=n-1; i<n; i++){
while (x1<n && X[x1][0]==-1) x1++;
while (y1<n && Y[y1][0]==-1) y1++;
x2 = back(X, x2, n);
y2 = back(Y, y2, n);
int *co1 = X[x1], *co2 = X[x2], *ce1 = Y[y1], *ce2 = Y[y2];
int co1ce2 = (co1[0] - ce2[0]) * (co1[0] - ce2[0]);
int co2ce1 = (co2[0] - ce1[0]) * (co2[0] - ce1[0]);
int cmp = co2ce1 - co1ce2; // wah value terbesar
if (cmp==0) cmp = co1[1] - co2[1]; // index co terkecil
if (cmp==0) cmp = ce2[1] - ce1[1]; // index ce terkecil
if (cmp < 0){
co1[0] = ce2[0] = -1;
printf("%d %d %d\n",co1[1],ce2[1],co1ce2);
} else {
co2[0] = ce1[0] = -1;
printf("%d %d %d\n",co2[1],ce1[1],co2ce1);
}
}
puts("");
}
}
|
| Solusi Pascal (oleh Eko Wibowo) |
type
node = record
value, idx : longint;
end;
tlist = array[1..10000] of node;
var
t, n, i, x1, x2, y1, y2, co2ce1, co1ce2, cmp : longint;
x, y : tlist;
function isSmaller(a,b : node):boolean;
begin
if (a.value <> b.value) then isSmaller := a.value < b.value
else isSmaller := a.idx < b.idx;
end;
// diambil dari contoh pada free-pascal
procedure sort(var a : tlist; l, r : longint);
var i, j : longint;
x, y : node;
begin
i:=l;
j:=r;
x:=a[(l + r) div 2];
repeat
while isSmaller(a[i], x) do i := i + 1;
while isSmaller(x, a[j]) do j := j - 1;
if i <= j then
begin
y := a[i];
a[i] := a[j];
a[j] := y;
i := i + 1;
j := j - 1;
end;
until i > j;
if l < j then sort(a,l,j);
if i < r then sort(a,i,r);
end;
function back(v : tlist; i, n : longint) : longint;
begin
while (i > 1) and (v[i-1].value <> -1) and (v[i-1].value = v[i].value) do i := i-1;
if (v[i].value <> -1) then back := i
else if (i + 1 <= n) and (v[i + 1].value <> -1) then back := i + 1
else
begin
while (i > 1) and ((v[i].value = -1) or (v[i-1].value = v[i].value)) do
i := i - 1;
back := i;
end;
end;
begin
read(t);
while (t > 0) do
begin
t := t - 1;
read(n);
for i := 1 to n do
begin
read(x[i].value);
x[i].idx := i;
end;
for i := 1 to n do
begin
read(y[i].value);
y[i].idx := i;
end;
sort(x,1,n);
sort(y,1,n);
x1 := 1;
x2 := n;
y1 := 1;
y2 := n;
for i := 1 to n do
begin
while (x1 <= n) and (x[x1].value = -1) do x1 := x1 + 1;
while (y1 <= n) and (y[y1].value = -1) do y1 := y1 + 1;
x2 := back(x,x2,n);
y2 := back(y,y2,n);
co1ce2 := sqr(x[x1].value - y[y2].value);
co2ce1 := sqr(x[x2].value - y[y1].value);
cmp := co2ce1 - co1ce2;
if (cmp=0) then cmp := x[x1].idx - x[x2].idx;
if (cmp=0) then cmp := y[y2].idx - y[y1].idx;
if (cmp < 0) then
begin
x[x1].value := -1;
y[y2].value := -1;
writeln(x[x1].idx-1,' ',y[y2].idx-1,' ',co1ce2);
end
else
begin
x[x2].value := -1;
y[y1].value := -1;
writeln(x[x2].idx-1,' ',y[y1].idx-1,' ',co2ce1);
end;
end;
writeln();
end;
end.
|
|