Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

domanda sull'hw2

g
giuseppebellantone (290 points)
2 2 3
in HW2 obbligatorio by (290 points)
recategorized by
mi chiedevo se per velocizzare il programma per passare il test: test_1_esempio4 si potesse considerare il caso in cui nella gara non ci fossero sorpassi, il caso, dunque, nel quale nella lista1 non siano presenti elementi con il carattere 's'
828 views

5 Answers

E
Edward (25950 points)
3 4 172
by (26.0k points)
Penso tu possa provarci, ma non credo ti aiuti molto.

Io invece sto avendo problemi con il test_1_esempio5, sul mio pc ci mette 1.1s, ma sulla vm va in timeout :(
AndreaGasparini (18850 points)
7 12 120
by (18.9k points)

Come è stato specificato dal professore nel post dell'Homework:

  • ATTENZIONE: i vostri programmi NON DEVONO sfruttare eventuali periodicità o caratteristiche strutturali degli input, ma devono essere applicabili a qualsiasi input valido.

Più che altro anche sfruttando questa "ottimizzazione" ti ricordo che verranno poi effettuati degli ulteriori test segreti che potrebbero rivelarsi essere nuovi casi particolari come questo e che magari il tuo algoritmo non risolverebbe perché invece di adottare una soluzione generale più efficiente l'hai adattato agli input forniti dal grader.

E
Edward (25950 points)
3 4 172
by (26.0k points)
Diciamo che non sfrutta una caratteristica dell'input, ma semplicemente una cosa che può effettivamente accadere, ossia che non ci siano sorpassi.

Il fatto è che dubito questa cosa possa migliorare l'efficienza del programma.
AndreaGasparini (18850 points)
7 12 120
by (18.9k points)

Il problema è che, da quello che mi sembra di capire, attualmente non supera il test_1_esempio4  e questa sarebbe la soluzione per superarlo, non per migliorarne l'efficienza, perciò il consiglio era più che altro di ragionarci un altro po' su per trovare una soluzione migliore

J
Jan Rogala (7260 points)
4 4 37
by (7.3k points)
Qua non hai torto, però è se in una gara vi sono dei sorpassi potrebbe andare a influire sui tempi degli altri test. Comunque si può fare, ma non è molto consigliato
plm (18850 points)
13 15 118
by (18.9k points)
Il programma non rallenta se aggiungi delle opzioni per le quale consideri degli eventi particolari.
f
fraore (790 points)
2 5 13
by (790 points)
Secondo me, da quello che ho visto durante le lezioni, l'unico modo per ridurre i tempi di ricerca di parecchie misure di grandezza è la ricerca binaria. Inizio seriamente a pensare che anche nell HW2 in qualche maniera vada usata nel momento in cui bisogna recuperare gli indici degli elementi nelle liste più grandi dei test 4 e 5.

Qualcuno ha pensato ad una soluzione del genere?
LUPOSaymon (2730 points)
2 3 27
by (2.7k points)

Bisogna sempre evitare, come gia detto dal professore 

ATTENZIONE: i vostri programmi NON DEVONO sfruttare eventuali periodicità o caratteristiche strutturali degli input, ma devono essere applicabili a qualsiasi input valido.

detto ciò, bisogna stare attenti e cercare di generalizzare un problema. Nel tuo caso, mi sembra fin troppo specifico per risolvere un singolo test; il professore potrebbe tranquillamente aggiungere nello stesso test un sorpasso , aggirando la tua risoluzione del problema. Piuttosto, sforzati a capire, provare e vedere se esiste un altro algoritmo che riesca a fare il minor numero di accessi e modifiche alle liste, cicli, controlli ecc.

Good luck :D