Buongiorno,
sto provando a risolvere il problema Chess tournament. Riesco ad ottenere solo 58/100. La mia soluzione impiega troppo tempo per l’ultimo subtask, quello senza limitazioni specifiche.
Per trovare il match più interessante utilizzo due cicli for annidati. Per rendere più veloce la computazione ho introdotto qualche euristica, ma non è sufficiente. Ad esempio nel primo ciclo for non controllo l’ultimo giocatore perché viene già controllato tramite il secondo ciclo for e nel secondo ciclo for parto ad analizzare dal giocatore nella posizione (i+1) per evitare di avere match fra gli stessi giocatori (0 vs 0 o 1 vs 1, …)
Allego il codice:
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main(){
ifstream cin("input.txt");
ofstream cout("output.txt");
ios::sync_with_stdio(false);
int N;
cin >> N;
vector<int> S(N);
for(int i = 0; i < N; i++) {
cin >> S[i];
}
int val;
int max_interesse = 0;
for (int i=0; i<N-1; i++){
for (int j=i+1; j<N; j++){
val = abs(S[i]-S[j])+abs(i-j);
if (val > max_interesse){
max_interesse = val;
}
}
}
cout << max_interesse << endl;
return 0;
}
Chi potrebbe aiutarmi a capire come approcciarmi al problema per ottenere 100/100?
Per parecchio tempo non andavo oltre i 58/100 ed avevo anche lasciato perdere; poi ho usato alcuni accorgimenti, migliorie ed ha funzionato anche se non me l’aspettavo. Per una soluzione convincente bisogna aspettare qualche dritta dai migliori tre solutori.
Comunque le migliorie, risultate vincenti, rispetto al mio da 58/100 che poi è simile a quello che hai postato sono:
Terminare l’esecuzione del processo prima di mandarlo in time out e stampare il risultato ottenuto fin li.
in fase di lettura dei dati trovare Smax, Smin e dove sono posizionati e trovare il valore della formula con questi dati
trovare il valore della formula in corrispondenza degli estremi ed assegnare al risultato (max_interesse) come valore iniziale il massimo dei valori trovati.
Uscire da entrambi i cicli quando è chiaro che i valori che troveremmo andando avanti non possono superare il valore fin qui trovato (quello che tu chiami max_interesse); per poter lavorare così anche col ciclo interno l’ho fatto andare all’indietro così i-j va a ridursi invece di crescere.
ultima cosa, credo non molto importante, invece di abs(i-j) ho messo j-i.
Andando per tentativi ho scoperto che si poteva terminare ben prima del tempo massimo.
Intanto grazie per la risposta!
Sono riuscito ad implementare i consigli 2/3/5.
Non capisco come fare a terminare l’esecuzione prima che lo script vada in timeout.
Che condizione devo imporre?
Per quanto riguarda il consiglio 4: ho capito l’idea risolutiva, ma non mi è chiaro quando precisamente terminare il ciclo interno.
Per il punto 1 guardati la funzione clock() troverai tantissimi esempi adatti ad ottenere ciò che ti serve.
per il punto 4:
chiamiamo Smax il valore massimo di S, Smin il minimo di S e diff=Smax-Smin
se risulta diff+j-i<=max_interesse (quello che hai trovato fin qui) che fai?
Esiste anche una soluzione in tempo lineare (senza cicli annidati)
Hint 1: esiste un modo (piuttosto banale) per far si’ che la distanza da un riferimento fisso (puoi prendere lo 0) e lo stile siano contati in un unico valore
Soluzione dell’hint 1: int W[N]; for (int i = 0; i < N; i++) W[i] = S[i] + i
Hint 2: se un giocatore in posizione j (a destra) ha uno stile maggiore di uno in posizione i (a sinistra), allora S[j] - S[i] + j - i = W[j] - W[i]
Hint 3: nel caso in cui nella coppia piu’ interessante il giocatore con lo stile piu’ alto sia a destra, la coppia migliore ha punteggio max(W) - min(W) (se sei pigro usi minmax_element, altrimenti lo calcoli a mano)
Hint 4: siccome il giocatore con lo stile piu’ alto della coppia piu’ interessante potrebbe trovarsi a sinistra, ripeti lo stesso algoritmo usando W[i] = S[i] - i
Buonasera, ho provato a risolvere lo stesso problema, implementando i consigli forniti in questa discussione. Ho ottenuto un miglioramento: 11/16 della subtask 4 sono stati completati con successo. Sfortunatamente, però 5 di questi (018 / 019 / 025 / 026 / 027) continuano a restituire “Execution timed out” a causa di un tempo di esecuzione compreso tra i 1.599s ed i 1.603s. Potreste aiutarmi? Vi ringrazio in anticipo. Qui di seguito allego il codice:
