Salve a tutti,
Ho appena provato a sviluppare l’algoritmo risolutivo del problema “Allineamento Magnetico (magneti)”…
Nel test che ho fatto, guadagno 10/100 e in ogni subtask prendo pochi output non corretti, tranne nell’ultimo in cui prendo solo Execution Timed Out…
Qui c’è il mio codice : https://pastebin.com/Xtyabmf7.
Grazie.
Prova a descrivere quello che fai il tuo algoritmo anche se guardando la soluzione che ho implementato io è molto “specifica”.
Nel tuo programma conti quante volte un magnete è diverso dal primo, ma potrebbe essere che nella soluzione ottimale sia il primo da girare.
Riguardo all’ultimo subtask la causa è questa:
char descrizione[10000];
N può arrivare fino a 10^5.
Grazie,
come mi consigli di ottimizzare il codice ?
Tu hai \frac{N}{4} magneti ed esegui K rotazioni, adesso può capitare che sia meglio girare tutti quelli uguali al primo ovvero \frac{N}{4}-K, quindi la risposta sarà il minori di questi due numeri.
Se per N/4 - K intendi questo ( https://pastebin.com/LE5hAPdZ )
Fa gli stessi output non corretti di prima…
Se no non ho capito cosa intendi dire con N/4 - K
Allora N/4 è il numero di magneti poiché ogni magnete viene rappresentato da 4 caratteri (+-).
Se tu giri tutti i magneti diversi dal primo ne giri K, se invece giri tutti quelli uguali al primi, giri il numero di magneti in totale meno quelli che avresti girato se fossero diversi dal primo ovvero \frac{N}{4}-K.
Il codice è giusto, basta che scrivi:
return std::min(k,N/4-k);
Poi ovviamente -come ho detto prima- devi cambiare 10^4 con 10^5:
char descrizione[100000];
Cambiando il return ottengo il 70/100 solo per via degli Execution killed with signal 11… Nonostante io abbia accorciato la dimensione di descrizione[10000]; in descrizione[1000];
Non devi accorciarla, devi aumentarla scrivi così:
char descrizione[100000];