[Tutti] Contest: Esercizio per le vacanze

[gugoXX]

Ecco un bell'esercizio per le vacanze.
Semplice e veloce, quando si trova il modo...

Come al solito, lasciamo tempo per pensare agli altri, nel caso in cui la soluzione ci fulminasse in fretta.

Sia dato una array di numeri interi, di lunghezza indefinita.
Si vuole ottenere come risultato un array di pari lunghezza, con ciascuna cella valorizzata tale per cui essa sia il prodotto di tutte le celle dell'array originale, tranne la propria cella corrispondente.
Es:

Array Originale:  1  5  6  3  4

Array risultate di 5 elementi.
Nella prima cella si vorrebbe avere il prodotto dei valori 5*6*3*4
Nella seconda cella invece 1*6*3*4
(il secondo, ovvero il 5, corrispondente alla nostra posizione, non si vuole)
Nella terza cella invece 1*5*3*4
etc.

Array risultato = 360 72 60 120 90
(Sempre se non ho fatto i soliti errori manuali)

Bene.
Ma c'e' un problema.
Non siamo sul nostro processore preferito.
Siamo sull'utlimissimo e innovativo processore progettato da Z80Fan, cdimauro, cionci e tutti gli altri.
Nella foga di pensare agli indirizzamenti, ai registri, ai bus e al resto, si sono dimenticati di focalizzarsi sulla ALU.
E in questa prima versione di processore si sono dimenticati semplicemente della DIVISIONE.
La divisione non la possiamo utilizzare mai.
Ne' all'inizio, ne durante, ne alla fine ne in alcun minimo step, perche' eseguendo la divisione del nostro linguaggio preferito viene sollevata un'eccezione macchina.

Qui l'array originale

2 1 3 1 2 2 3 3 4 3 3 1 1 4 4 4 2 2 4 4 4 2 2 4 2 3 1 1 3 3 2 1 3 4 3 4 2 1 4 1 3 1 4 4 1 2 1 2 4 1 2 4

Non facciamoci ingannare dai valori bassi degli elementi. Potrebbero essere a priori anche alti.
Sono bassi perche' gia' cosi' i risultati sono valori parecchio grandi, e infatti occorre restituire un array di elementi almeno a 64bit per poter ospitare correttamente tutti i risultati.

Inoltre il nostro responsabile e' uno schiavista da piantagione.
Si richiede che il risultato sia geenrato mediante un algoritmo di complessita' O(N)
Ma per iniziare ciascuno provi a buttare giu' la soluzione come riesce...

Bene, niente divisioni (mai) e buon lavoro (e buone vacanze, io domani saro' a galleggiare sul mar Rosso)

[Rsk]

Originariamente inviato da gugoXX

Ecco un bell'esercizio per le vacanze.
Semplice e veloce, quando si trova il modo...

Come al solito, lasciamo tempo per pensare agli altri, nel caso in cui la soluzione ci fulminasse in fretta.

Sia dato una array di numeri interi, di lunghezza indefinita.
Si vuole ottenere come risultato un array di pari lunghezza, con ciascuna cella valorizzata tale per cui essa sia il prodotto di tutte le celle dell'array originale, tranne la propria cella corrispondente.
Es:

Array Originale:  1  5  6  3  4

Array risultate di 5 elementi.
Nella prima cella si vorrebbe avere il prodotto dei valori 5*6*3*4
Nella seconda cella invece 1*6*3*4
(il secondo, ovvero il 5, corrispondente alla nostra posizione, non si vuole)
Nella terza cella invece 1*5*3*4
etc.

Array risultato = 360 72 60 120 90
(Sempre se non ho fatto i soliti errori manuali)

Bene.
Ma c'e' un problema.
Non siamo sul nostro processore preferito.
Siamo sull'utlimissimo e innovativo processore progettato da Z80Fan, cdimauro, cionci e tutti gli altri.
Nella foga di pensare agli indirizzamenti, ai registri, ai bus e al resto, si sono dimenticati di focalizzarsi sulla ALU.
E in questa prima versione di processore si sono dimenticati semplicemente della DIVISIONE.
La divisione non la possiamo utilizzare mai.
Ne' all'inizio, ne durante, ne alla fine ne in alcun minimo step, perche' eseguendo la divisione del nostro linguaggio preferito viene sollevata un'eccezione macchina.

Qui l'array originale

2 1 3 1 2 2 3 3 4 3 3 1 1 4 4 4 2 2 4 4 4 2 2 4 2 3 1 1 3 3 2 1 3 4 3 4 2 1 4 1 3 1 4 4 1 2 1 2 4 1 2 4

Non facciamoci ingannare dai valori bassi degli elementi. Potrebbero essere a priori anche alti.
Sono bassi perche' gia' cosi' i risultati sono valori parecchio grandi, e infatti occorre restituire un array di elementi almeno a 64bit per poter ospitare correttamente tutti i risultati.

Inoltre il nostro responsabile e' uno schiavista da piantagione.
Si richiede che il risultato sia geenrato mediante un algoritmo di complessita' O(N)
Ma per iniziare ciascuno provi a buttare giu' la soluzione come riesce...

Bene, niente divisioni (mai) e buon lavoro (e buone vacanze, io domani saro' a galleggiare sul mar Rosso)

Per ora mi viene in mente solo una versione O(2N)
Ci penserò meglio quando sarò ispirato

[VICIUS]

Fare la divisione usando altre funzioni non è un problema. L'o(n) invece sembra più impegnativo come requisito. Per ora ho ancora due cicli. Uno per il totale e l'altro in cui divido.

[cionci]

Originariamente inviato da Rsk

Per ora mi viene in mente solo una versione O(2N)
Ci penserò meglio quando sarò ispirato

O(2N) è O(N)
Anche a me viene in mente così...

[cionci]

Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro

[ndakota]

Oddio non capisco.. Ho un bug che mi fa sclerare. Se metto l'array da cinque elementi, uguale al tuo, ho i risultati uguali. Se metto quello lungo, ottengo tutti zeri Qualcuno riesce a capire cosa potrebbe essere senza guardare il codice? Contenst nel contest

EDIT: dimenticato di dire che l'ho scritto in java.

[Rsk]

Originariamente inviato da cionci

Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro

La mia stessa idea
è O(N) sia per quanto riguarda la complessita computazionale sia per la quantità di memoria occupata

[WarDuck]

Forse ho trovato la soluzione anche io, tra un po' implemento il codice e vediamo cosa esce con l'array grande .

[gugoXX]

Originariamente inviato da ndakota

EDIT: dimenticato di dire che l'ho scritto in java.

Sei probabilmente in overflow perche' stai usando interi a 32bit.
Ne servono almeno 64bit

Originariamente inviato da cionci

Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro

Mi sa che hai beccato una soluzione corretta.

[cionci]

Originariamente inviato da gugoXX

Mi sa che hai beccato una soluzione corretta.

Se ho copiato bene il vettore di partenza:

Spoiler:

Res[0] = 779100745302540288 Res[1] = 1558201490605080576 Res[2] = 519400496868360192 Res[3] = 1558201490605080576 Res[4] = 779100745302540288 Res[5] = 779100745302540288 Res[6] = 519400496868360192 Res[7] = 519400496868360192 Res[8] = 389550372651270144 Res[9] = 519400496868360192 Res[10] = 519400496868360192 Res[11] = 1558201490605080576 Res[12] = 1558201490605080576 Res[13] = 389550372651270144 Res[14] = 389550372651270144 Res[15] = 389550372651270144 Res[16] = 779100745302540288 Res[17] = 779100745302540288 Res[18] = 389550372651270144 Res[19] = 389550372651270144 Res[20] = 389550372651270144 Res[21] = 779100745302540288 Res[22] = 779100745302540288 Res[23] = 389550372651270144 Res[24] = 779100745302540288 Res[25] = 519400496868360192 Res[26] = 1558201490605080576 Res[27] = 1558201490605080576 Res[28] = 519400496868360192 Res[29] = 519400496868360192 Res[30] = 779100745302540288 Res[31] = 1558201490605080576 Res[32] = 519400496868360192 Res[33] = 389550372651270144 Res[34] = 519400496868360192 Res[35] = 389550372651270144 Res[36] = 779100745302540288 Res[37] = 1558201490605080576 Res[38] = 389550372651270144 Res[39] = 1558201490605080576 Res[40] = 519400496868360192 Res[41] = 1558201490605080576 Res[42] = 389550372651270144 Res[43] = 389550372651270144 Res[44] = 1558201490605080576 Res[45] = 779100745302540288 Res[46] = 1558201490605080576 Res[47] = 779100745302540288 Res[48] = 389550372651270144 Res[49] = 1558201490605080576 Res[50] = 779100745302540288 Res[51] = 389550372651270144

[cionci]

Certo che sono proprio malato...

    const int v[] = {2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
               3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
               4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
               2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
               3, 1, 4, 4, 1, 2, 1, 2, 4, 1, 2, 4};

    const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
    const int last =  size - 1;

    long long prod[size];
    long long res[size];

Non è colpa mia...non si poteva usare la divisione

[marco.r]

Originariamente inviato da cionci

Certo che sono proprio malato...

    const int v[] = {2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
               3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
               4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
               2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
               3, 1, 4, 4, 1, 2, 1, 2, 4, 1, 2, 4};

    const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
    const int last =  size - 1;

    long long prod[size];
    long long res[size];

Non è colpa mia...non si poteva usare la divisione

La divisione non serve

[cionci]

Originariamente inviato da marco.r

La divisione non serve

"The sizeof operator yields the size of its operand with respect to the size of type char."

[Tommo]

Fatto, ma non mi riesce di non andare in overflow in C
E' che non mi basta la voglia di creare un progetto x64 per espandere gli unsigned long.

Cmq m'è venuto lungo una decina di righe, 2N come esecuzione e N come memoria (se consideriamo che il risultato lo scrivo nell'input).

[cionci]

Un tipo a 64 bit ce l'ha sicuramente il tuo compilatore
Su gcc a 32 bit ad esempio c'è long long...

[WarDuck]

Fatto, adesso devo fare un programma che controlli i risultati con quelli di cionci

[cionci]

Originariamente inviato da WarDuck

Fatto, adesso devo fare un programma che controlli i risultati con quelli di cionci

Su...è semplice. Il prodotto di tutti è quello che hai nelle posizioni dove c'è l'1...nelle altre basta che sia la metà, un terzo o un quarto...

[WarDuck]

Originariamente inviato da cionci

Su...è semplice. Il prodotto di tutti è quello che hai nelle posizioni dove c'è l'1...nelle altre basta che sia la metà, un terzo o un quarto...

Si ma a me vengono sfalsati, sarà che uso un algoritmo tutto mio

[gugoXX]

Occhio che l'algoritmo deve funzionare anche con il test di prova

E anche con array tipo
4 233 1313131 233 14 4443

(Overflow a parte)

[Tommo]

Originariamente inviato da cionci

Un tipo a 64 bit ce l'ha sicuramente il tuo compilatore
Su gcc a 32 bit ad esempio c'è long long...

long long?

It's magic (cit.)

Comunque ora funziona, mi vengono i tuoi stessi risultati.
Cmq non ho fatto controllando le frazioni, io l'ho risolto in 2N con un doppio accumulatore... così dovrebbe funzionare con qualsiasi numero fornito in input.

In fondo questo problema, quando si rimuove la divisione, diventa una classica Reduction, che dà tanti grattacapi nelle architetture parallele