Algoritmi

[pat871]

Ho un paio di problemi che mi danno del filo da torcere...
1) Abbiamo due Arrays A e B di lunghezza n. Consideriamo tutte le coppie $(A, B[j])$ per $1 \le i,j \le n$ e definiamo la GRANDEZZA di ogni coppia $(A, B[j])$ come $A + B[j]$. Mostrare come si possa in tempo $O(n)$ trovare le $n$ coppie più grandi in A e B.

2) Abbiamo un Array con valori interi A della lunghezza n.
Per $1 \le i < j \le n$ definiamo $mi nEl ement(i,j) := \min_{1\le x\le j} {A[x]}$. Mostrare come si possa in tempo $O(n* log(n))$ costruire una struttura di dati, che permetta di richiamare $mi nEl ement(i,j)$ per qualsiasi $i$ e $j$ ($1 \le i < j \le n$) con un tempo costante $O(1)$.

[vl4dster]

Se non ho interpretato male (mi sembrano troppo semplici...?):

1) *** edit*** ho detto una idiozia

2) Questo sinceramente non lo capisco:
basta ordinare il vettore in $O(n\log n)$, e poi in $O(1)$ ritorni $"minElementi"(i,j)=A$ (assumendo
un ordine crescente di $A$)

[pat871]

Per il secondo che algoritmo uso per ordinare l'Array? Il Mergesort? Come creo una struttura di dati adatta?

sono negato in queste cose, non mi vengono mai in mente le idee

[fields1]

"vl4d":Se non ho interpretato male (mi sembrano troppo semplici...?):

1) Trova il massimo di uno dei due vettori in $O(n)$, diciamo in $A[M]$
allora le coppie sono le $(A[M], B[k])$ per $1\leq k\leq n$, "costruibili" sempre in $O(n)$

Non è detto che quelle trovate da te siano le $n$ coppie più grandi. Ad esempio: $A=(3,4,11)$ e $B=(4,7,13)$

[vl4dster]

ups l'ho liquidato troppo presto

per il secondo puoi usare mergesort, quicksort, heapsort... per l'heapsort devi usare
uno heap ma non penso che il "senso" dell'esercizio sia questo... sei sicuro che non chieda
qualcos'altro ?

[vl4dster]

es1)
1) Trasforma A e B in uno max-heap (tempo $O(n)$)
2) Estrai da A e da B $"ceiling"(\sqrt(n))$ elementi, risistemando ogni volta l'heap (tempo $O(\sqrt(n) \log n)$)
3) Costruisci le $O(n)$ coppie piu' grandi dagli $O(\sqrt(n))$ elementi piu' grandi in tempo $O(n)$ prendendo
$(A[max], B[max])$, $(A[max-1], B[max])$, $(A[max], B[max-1])$, $(A[max-1], B[max-1])$, $\ldots$

Ovviamente, se le vuoi in ordine, ad ogni diagonale del tipo: $(A[max-(i+1)], B[max-i])$, $(A[max-i], B[max-(i+1)])$
devi prendere prima la piu' grande, e se arrivi all'n-esima coppia su una diagonale dello stesso tipo devi prendere
solo la piu' grande. In questo modo la piu' piccola coppia che trovi e' comunque piu' grande di tutte quelle che lasci
fuori, e questo prova che quelle trovate sono le $n$ coppie piu' grandi.

Spero che questa volta vada bene... ultimamente sono parecchio fuso...