Qualcuno ha risolto il problema verifiche? Non riesco a capire perché non mi da il punteggio pieno. Il problema risolto e sottomesso mi fa passare
• Subtask 1 [10 punti]: Casi d’esempio.
• Subtask 2 [40 punti]: N = 1, ovvero c’è solo una verifica in tutto l’anno.
solo parzialmente, il Subtask 3 [50 punti]: Nessuna limitazione specifica.
Questo il codice: verifiche.pdf (117,8 KB)
Piuttosto che postare solamente il codice è più comodo se provi anche a spiegare a parole cosa fa il programma/algoritmo implementato.
Comunque, il tuo codice non riesce a risolvere correttamente nessuno dei casi in cui viene assegnata più di una verifica e queste possono essere superate dagli studenti (l’output -1 è sbagliato).
Provi a spiegarci meglio che puoi il ragionamento su cui hai basato il programma. Inoltre può aiutarti provare a risolvere alcuni testcase con 2 o più verifiche, così da capire come si comporta il tuo codice in questi casi
Ho provato con alcuni testcase con 2 o 3 verifiche. Con il ragionamento che ho fatto sembra che tutto funziona.
Mi fai la cortesia di darmi due esempi di testcase con 2 o più verifiche, il primo che rispetta i vincoli e il secondo che mi da -1.
Il ragionamento fatto da me é questo:
nella prima riga del test case troverò sempre tre numeri:
numero verifiche, giorni per memorizzare un argomento, numero argomenti
nella seconda riga troverò tanti numeri quante sono le verifiche, questi numeri dovranno essere in ordine crescente e la distanza tra un numero ed un altro a partire dalla prima coppia dovrà essere >= del numero di argomenti (se viene rispettato questo vuol dire che il numero minimo di giorni per trovarsi pronti alle verifiche é N*K ovvero numero di verifiche moltiplicato numero di argomenti. se questo non viene rispettato ovviamente l’output sarà -1.
Sbaglio sicuramente qualcosa. Probabile che ancora con ho capito la traccia.
Spero di aver spiegato cosa fa il mio codice che cmq come ti dicevo supera il subtask2.
Più che darmi la soluzione sarei felice se mi mandi un paio di tast case con output che il mio programma non verifica correttamente.
Grazie
Sì, il problema penso stia proprio nella comprensione del testo del problema.
Gli studenti una volta superata una verifica non dimenticano gli argomenti studiati fino a quel punto, continuano a ricordarli e possono usarli per più verifiche (a patto che non siano ancora trascorsi T giorni.
Ad esempio, se devo conoscere almeno 5 argomenti per tre verifiche, nei giorni 3, 4 e 6, il numero minimo di giorni da studiare dipende dalla permanenza T:
con T < 5, l’output sarà -1 perché anche studiando tutti i giorni è impossibile conoscere 5 argomenti contemporaneamente
con T = 5, dovrò studiare nei giorni -2 , -1 , 0 , 1, 2 per poter superare la prima verifica; nel giorno 3 per superare la seconda e nei giorni 4 e 5 per superare anche l’ultima verifica. Questo perché è necessario sfruttare tutti e 5(K) i giorni precedenti a una verifica per superarla
con T > 5, ho più libertà perché per ciascuna verifica ho una finestra più grande di tempo valida per contare gli argomenti conosciuti. Ad esempio con T = 7, se studio come prima a ridosso della prima verifica non ho bisogno di studiare il giorno 3 per superare la seconda verifica perché l’argomento studiato il giorno -2 è ancora ricordato dallo studente.
Un test case che il tuo programma non risolve può essere questo:
Ti ringrazio dei suggerimenti. Effettivamente non avevo ben capito i vincoli del problema. Ho provato come si dice “in tutte le salse”.
Non capisco come mai non riesco a far girare tutti i testcase disponibili.
Questi gli output errati:
i test case che mi hai dato sono passati.
Ci sono altre testcase particolari da provare che possono aiutarmi a trovare la soluzione completa?
Ciao e ancora grazie per l’aiuto.
Ciao,
i suggerimenti che mi hai dato sono stati utili. Il ragionamento che ho fatto é:
se T<K allora -1;
altrimenti
parto sempre K giorni prima della prima prova per cui il giorno della prima prova conosco tutti gli argomenti. E’ chiaro che questo lo dovrò verificare per tutti gli altri giorni delle verifiche previste.
se per ogni coppia di giorni verifiche:
giornosuccessivo-giornoprecedente>T allora devo aggiungere K giorni per studiare tutto prima del giorno della prova.
Quando invece questa condizione risulta falsa allora vuol dire che i giorni di studio variano da 1 a K dipende dalla distanza giornosuccessivo-giornoprecedente.
Questo é tutto. Sulla carta sembra che tutto funzioni, ma é probabile che per alcuni casi il ragionamento fatto non va bene.
Per essere un problema di difficoltà 1 … direi che … si incomincia proprio bene. Ma questo mi diverte.
Questo è lo spirito giusto [quote=“filippotrotta, post:7, topic:4055”]
Questo é tutto. Sulla carta sembra che tutto funzioni, ma é probabile che per alcuni casi il ragionamento fatto non va bene.
[/quote]
Ho capito il tuo ragionamento, però c’è ancora un dettaglio da sistemare. Prova a considerare questo esempio
Il mio codice produce come soluzione 6
L’errore sta nel come conti i giorni di studio “riutilizzabili”.
Prova magari a rileggere il testo ancora una volta, se non ti è comunque chiaro ti riporto il ragionamento per l’esempio di prima
[spoiler]
Ho una verifica il giorno 4, devo studiare almeno 4 giorni nei 5 precedenti [-1 ... 3]. Siccome non ho ancora mai studiato, studio nei quattro giorni più vicini possibile (0, 1, 2, 3)
Ho una verifica il giorno 5, devo studiare almeno 4 giorni nei 5 precedenti [0 ... 4].
Siccome ho già studiato nei giorni (0, 1, 2, 3) non ho bisogno di studiare ulteriormente.
Ho una verifica il giorno 7, devo studiare almeno 4 giorni nei 5 precedenti [2 ... 6].
Siccome ho già studiato nei giorni (2, 3) mi basterà studiare altri due giorni (5, 6) che sommati ai due di prima mi portano a 6 [/spoiler]
Penso che i test case che hai postato siano tutti giusti, prova a spiegare cosa fa adesso il tuo programma o a inviare il codice perché solo da questi esempi corretti è difficile azzeccare l’errore
Non ho capito bene l’utilizzo della variabile f nel tuo codice, comunque penso che consideri ancora male il numero di giorni di studio riutilizzabili per ciascuna verifica. Se nel giorno X conosco K argomenti, per sapere quanti ne conoscerò nel giorno X + N non mi basta valutare la differenza tra queste due date, perché potrei non aver studiato nei giorni più prossimi alla verifica.
Un testcase che il tuo codice non risolve può essere questo:
4 7 4
10 12 13 16
Con il tuo codice dovrebbe dare come risultato 6 (piuttosto che 7), ma potrei anche essermi sbagliato io nel completare il codice dato che nel file non è inclusa la funzione main e la dichiarazione di alcune variabili globali.
Anche se è una strategia diversa da quella che stai seguendo tu, ti lascio uno spunto per una soluzione corretta
Considerando i limiti piccoli del problema (1 ≤ N, T, K ≤ 1 000), perché non memorizzare uno ad uno tutti i giorni in cui è necessario studiare?
hai ragione probabilmente faccio troppe acrobazie.
Effettivamente il test case che mi hai dato non dava 7 ma 6. Adesso mi da 7 perché non dovevo decrementare il contatore c di 1.
la variabile f mi é servita perché solo in un caso non devo partire da K giorni ma da K-1 giorni.
Ci sono parecchie situazioni da considerare e per questo ritengo che non sia un problema con difficoltà 1. A meno che non ci sia una soluzione più semplice che non riesco a trovare.
Anche contando giorno per giorno come tu dici, comunque i controlli bisogna farli perché ci saranno dei giorni che non dovrò studiare.
Non mi arrendo. Penso di annullare tutto e cambiare strategia.
Grazie per i consigli utili che mi dai.
Ciao, chi ti scrive è colui che ha scritto il testo del problema
Teoricamente non avevo assegnato nessuna scala di difficoltà al problema (che comunque non è troppo difficile…).
Purtroppo, fino a poco tempo fa, il “generatore” dei pdf includeva di default “Difficoltà: 1” oppure “Difficoltà: None” se l’autore non specificava un livello di difficoltà per il problema. Ora questo problema è stato sistemato e in futuro non dovrebbe più capitare questo inconveniente.
Ciao Filippo,
finalmente ho potuto provare il tuo algoritmo.
Ho utilizzato un array di bool inizializzandolo a false.
Ho quindi contato i giorni di studio mettendoli a true, ma evidentemente…
Ovviamente funziona su tutti i test case che abbiamo condiviso.
In un caso come questo, sarebbe molto più semplice se tu condividessi il tuo codice sorgente e/o l’algoritmo nel dettaglio per poter capire come mai alcuni testcase specifici potrebbero non funzionare
L’algoritmo era stato impostato bene, ma essendo la macchia “poco intelligente” non si era accorta che il vettore di bool inizializzato a 2*MAXN, quando andavo, alla fine per leggere i true arrivava fino a MAXN. Piccole distrazioni, recuperabili subito. Se non ci fosse stato l’input della tua idea di soluzione, probabilmente ci sarei arrivato ma più tardi.
Purtroppo quando si accetta per buona, una soluzione che fa girare il programma, non si prendono in considerazione altre. Questo mi ha fatto perdere tempo.
Questo scambio di battute con suggerimenti utili mi serviranno per far capire agli allievi quale deve essere lo spirito della partecipazione alla gara, ma soprattutto imparare a condividere i propri saperi.