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

Do you need help?

HW2 test 4 caso particolare

j
jbox65 (530 points)
4 7 10
in HW2 obbligatorio by (530 points)
edited by
Ma per passare il test 4 si può creare un if che tratta quel caso particolare? Perchè mi è stato dato come consiglio per passarlo di procedere in questo modo, ma non dovrebbe essere costruito per casi generali l'algoritmo?

EDIT: Per test 4 intendo l'esempio 5, quello con gli swap.
649 views

7 Answers

E
Edward (25950 points)
3 4 172
by (26.0k points)

Anche a me è stato dato come consiglio (da qualcuno che non ha capito nulla del mio algoritmo) di controllare che non ci siano stati sorpassi per passare il test4.

Ti posso assicurare che non è necessario farlo per superarlo.

Tra le regole dell'homework c'è scritto:

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

Io eviterei.

È vero che ci possono essere input nella quale non ci siano sorpassi, ma quindi che succede se nel mezzo ti mette un sorpasso? Questo rientrerebbe nello sfruttare una caratteristica dell'input.

j
jbox65 (530 points)
4 7 10
by (530 points)
Purtoppo pure io ho ricevuto consigli solo da chi non ha capito come funzionava il mio algoritmo con i dizionari, ho sperato in un consiglio con una soluzione alternativa più efficente, ma purtoppo mi è andata male.
AlessandraIzzo (6010 points)
6 6 30
by (6.0k points)
Idem, 3 su 3 non hanno capito il mio algoritmo, pur avendolo spiegato con un certo dettaglio. Consigli completamente inutili (anzi, sbagliati) e voti senza senso.
Christian (15220 points)
3 4 77
by (15.2k points)

Ciao, diciamo che non credo sia il consiglio migliore :)
Qui si è già parlato proprio di questo approccio al test 4.

plm (18850 points)
13 15 118
by (18.9k points)
In realtà l'algoritmo dovrebbe essere molto generale, ma ad esempio puoi fare in modo di controllare se degli eventi si ripetano molte volte e lavorare di conseguenza, in una generazione random è possibile che ci siano 100 sorpassi di fila
n
n.rossi (650 points)
3 4 9
by (650 points)
Spiegaci cosa hai fatto così eventualmente possiamo darti una mano nel migliorare.
j
jbox65 (530 points)
4 7 10
by (530 points)
Io ho lavorato con i dizionari e i set, passo tutti i test tranne il 4 (esempio 5, quello dove swappano tutti), purtoppo non ho avuto suggerimenti da parte di chi li ha passati tutti e 16 e sono alla ricerca di un metodo più efficente del mio (senza usare casi particolari).
n
n.rossi (650 points)
3 4 9
by (650 points)
Io credo che lavorando con i dizionari i test vengono tutti fuori con qualsiasi input, io gli insiemi non li ho utilizzato per il semplice fatto che per come ho costruito il dizionario non mi servono, attualmente passo tutti i test in locale, ma il 5 sulla VM fallisce per
0.65 ms e dato che nessuno mi ha suggerito soluzioni, sto cercando in autonomia qualcosa. Comunque descrivimi cosa hai fatto e vedo se posso aiutarti.
a
a.pietroluongo (11250 points)
20 39 131
by (11.3k points)
edited by
[quote="jbox65"]Ma per passare il test 4 si può creare un if che tratta quel caso particolare?[/quote]
No.
mi sembra che sia stato detto anche da Spognardi nelle esercitazioni.
M
MatteoB (1690 points)
10 16 21
by (1.7k points)
Ovviamente l'algoritmo che andiamo a "costruire" deve funzionare per tutti i casi che si presentano nei test e non, e quindi quando si crea l'algoritmo bisogna pensare in linee generali prevedere tutti i casi possibili che ci potrebbero essere, in modo tale che quando va in esecuzione funzioni per tutti i test che poi andranno a testare il tuo algoritmo.

Implementare una if che prevede quel caso specifico potrebbe avere degli effetti collaterali, potrebbe si velocizzare quel test ma allo stesso tempo potrebbe rallentare altre parti
J
Jan Rogala (7260 points)
4 4 37
by (7.3k points)
Non penso si un grandissimo problema dato che è lecito farsi domande sul come migliorare un algoritmo in base ad un determinato input. Però in questo caso per l'esempio 5 in non vedo nessun caso particolare, ovvero si la lista di partenza viene completamente ribaltata e poi mano a mano vengono cancellati molti concorrenti, perciò se riesci a creare un qualcosa a partire da cio molto probabilmente creerai qualcosa che abbia a che fare con la periodicità delle operazioni, il che questo non è consentito da regolamento. Però un caso particolare che potrebbe succedere è quello dove non avvengono sorpassi, li se riesci a trovare qualcosa di efficiente puoi sfruttare quella condizione, poichè non usa una periodicità ma una caratteristica dell'input. Attenzione, molto probabilmente andrai a compromettere i test che non hanno questa caratteristica, perchè dovranno fare un controllo in piu