Ciao a tutti, sto provando a risolvere police 6 sulla piattaforma di allenamento.
Non riesco a ottenere 100/100 perchè vai TLE.
La mia soluzione consiste in un vettore di lunghezza pari a L, e ogni checkpoint incrementa di 1 nel suo raggio di azione.
Alla fine trovo il minimo nel vettore
Come potrei migliorare la soluzione?
1 Mi Piace
Ciao,
Il problema sta nel fatto che non puoi scorrere l’intera lunghezza L perche’ e’ troppo grande per essere calcolata
Generalmente nelle gare di programmazione puoi permetterti di fare all’incirca 10^8 operazioni senza andare fuori tempo, ma dai constraints puoi notare che L puo’ raggiungere anche il 10^9
Ti faccio quindi notare (hint) che non e’ necessario controllare ogni singolo valore da 0 a L, bensi’ puoi anche solo determinati punti con una caratteristica particolare (spoiler: sono 2*n)
Credo di aver capito: ogni checkpoint ha un lato destro e un lato sinistro
quindi mi basta creare un vettore di dimensione 2*N
Giusto??
Esattamente, adesso si tratta di trovare un modo per associare a ogni posizione da 0 a L un indice corrispondente che va pero’ da 0 a 2*N (compito non facilissimo, ma che non richiede conoscenze particolari oltre a set/mappe per essere fatto) e per il resto il programma che prima andava in tle dovrebbe darti 100/100
Si può fare anche senza set e mappe bastano dei normali array: uno per gli estremi sinistri uno per quelli destri e poi si fa il … ed è una versione veloce che gira anche in C.
Ci ho pensato ma non mi viene niente in mente…potresti darmi qualche altro indizio??
Quei due array sono ordinati crescenti, facendo il merge di questi due si ottiene un terzo ordinato crescente nel quale bisogna distinguere gli inizi delle zone di copertura dai termini delle stesse.
Tieni presente che un checkpoint piazzato in x1 copre una zona che va da x1-M a x1+M estremi inclusi e, per tutte le x comprese in quell’intervallo, aumenta di 1 la quantità di checkpoint che le copre.
Si usa poi un contatore delle coperture che si incrementa quando incontra l’inizio di una zona di copertura di un checkpoint e si decrementa quando …