Suggerimento per Shishi pre_oii?

Aiuto
1

Ciao, è da un po’ che sono fermo su questo problema e non riesco seriamente a capire come risolverlo.
Leggendolo ricorda molto Knapsack, il fatto è che non riesco a capire come minimizzare le occorrenze o anche solo come tenerne conto per fare scelte successive.

Qualche suggerimento?

Grazie

2

Ciao, il problema è tutt’altro che scontato.
È un buon esercizio risolvere dei parziali con una dp.

Per la soluzione da 100 si può usare un bitset di dimensione B+1 dove mybitset.test(k) indica se la somma k è ottenibile. Iteri finché ottieni B o finché aggiungere un elemento non ti rende possibile nessuna nuova somma. Con qualche altro accorgimento entra nel time limit.

In fondo a questo blog trovi altre idee e la soluzione ufficiale.

3

Aggiungo che la soluzione ufficiale è descritta in modo dettagliato nella wiki: https://wiki.olinfo.it/it/2020/pre-oii/sushi

2 Mi Piace
4

Innanzitutto grazie per le risposte, però non ho compreso totalmente la solzione, per questo ho ancora qualche domanda ahah

Tutto quello che segue è basato sulla soluzione ufficiale:

Allora di base io ho capito che per fare questo problema l’idea iniziale è di provare tutte le combionazioni possibili, o meglio, avendo portate infinite, prima vedo se con 1 di ognuna posso arrivare alla somma, poi con 2 di ognuna, poi con 3 ecc.

Il problema però dell’approcio utilizzato sopra è che arriva solo a 69/100 perché risulta troppo lento. Allora iniziano le ottimizzazioni e qui comincio a perdermi:

  1. La prima ottimizzazione si basa su questo lemma che in se e per se ha un senso, il fatto è che poi comincia ad aggiungere al knapsack potenze di due di ogni ogetto e afferma che “In questo modo otteniamo un knapsack equivalente che tuttavia ha un numero di oggetti molto più piccolo”.

Ma come fa ad avere un numero di oggetti più piccolo? Cioè sto aggiungendo potenze di due e prima o poi supererò la potenza desiderata, quindi sto aggiungendo più oggetti del dovuto in teoria.

  1. La seconda ottimizzazione mi è più chiara, anche se non in tutti i suoi passaggi. Infatti l’idea che dovebbe esserci dietro è la seguente: se, nel’iterazione precedente, avevo aggiunto al knapsack 2^j oggetti e non ero arrivato alla soluzione, e in questa iterazione aggiungo 2^(j+1) oggetti e arrivo alla soluzione, allora il numero di oggetti necessario per formare la somma (e quindi la soluzione stessa) è compreso tra 1+2+...+2^j e 1+2+...+2^j+2^(j+1). Quindi basta fare una ricerca binaria(?) per trovarlo.

Quindi cosa c’entra la ricerca esponenziale? Non capisco…
E perché non è possibile formare la somma desiderata con 1+2+...+2^k+ 2^(k+1), mentre con 1+2+...+2^k sì? Se la posso formare con R oggetti allora la posso formare anche con R+1, è detto all’inizio (La somma che non si può fare con 2^(k+1) oggetti è detto nella terza riga della seconda ottimizazione)

Il bitset invece sono riuscito a capirlo e non lo avevo mai visto implementato per knapsack, molto carino e molto veloce, me lo sono segnato.

Grazie a chiunque abbia la pazienza e la voglia di rispondere a queste domande ahaha

5

Riguardo alla prima domanda, considera di avere 7 copie di ciascun piatto. La strategia banale è quella di inserire ciascuna copia del piatta una alla volta ottenendo un totale di 7 \cdot N oggetti. Tuttavia se anziché inserire le 7 copie le raggruppiamo formando potenze di 2, otteniamo solo 3 oggetti: A[i], 2 \cdot A[i] e 4 \cdot A[i] per un totale di 3 \cdot N oggetti. Se però nella soluzione ottimale il numero di occorrenze del piatto non è una potenza di 2 posso comunque trovare una combinazione equivalente:

  • 3 piatti: A[i] + (2 \cdot A[i]);
  • 5 piatti: A[i] + (4 \cdot A[i]);
  • 6 piatti: (2 \cdot A[i]) + (4 \cdot A[i]);
  • 7 piatti: A[i] + (2 \cdot A[i]) + (4 \cdot A[i]).

Generalizzando, anziché avere R copie di ciascun piatto possiamo usarne solo \log_2(R).

Riguardo la seconda domanda, effettivamente c’era un piccolo errore nella soluzione che ho corretto al volo. Comunque, una volta che hai trovato il valore k basta, come hai detto, fare una ricerca binaria tra 1+2+\ldots+2^k e 1+2+\ldots+2^{k+1}, però bisogna prima determinare il valore di k e qui entra in gioco la ricerca esponenziale. “ricerca esponenziale” è solo un modo per dire “prova 1, 1+2, 1+2+4, ecc, poi fai una ricerca binaria”.

1 Mi Piace
6

Ok, adesso mi è tutto più chiaro, grazie mille