Ho capito l’algoritmo in sé, è molto semplice. Sostanzialmente faccio backtrack dei mosaici finché non trovo la configurazione ideale.
Il codice è molto simile alla soluzione ufficiale (ho controllato poi). La cosa che mi chiedo è perché allora continuo ad avere in 3 subtask un TLE di 10.99 s
Un primo consiglio che ti darei è di salvare le piastrelle utilizzate in un array di bool invece che un bitset, dovrebbe essere un po più veloce. Poi oltre ai vettori che in base al lato sinistro o superiore ti da le piastrelle ne aggiungerei uno che in base ad entrambe (lato sinistro e superiore) ti ritorna le piastrelle. Dovrebbe velocizzare l’esecuzione.
Dario
Ho provato con e senza bitset, il tempo è lo stesso.
Ho provato a non sfruttare le adiacenze, e fare un semplice pruning se un mosaico x non corrisponde a quello superiore o quello a sinistra, ma i tempi sono gli stessi.
Per quella inferiore o a destra, non vedo come. Io tendo a scendere dall’angolo in alto a sinistra a quello in basso a destra. A meno che non mi consigli di muovermi a spirale o avanti-indietro come snake non ne vedo utilità. E comunque dubito che muovermi in direzioni diverse migliori la complessità
Quello che intendevo con lato sinistro e superiore era:
Dato il lato sinistro e/o il lato superiore, ritorna tutte le piastrelle che hanno i lati come richiesto
Quindi se chiedessi sinistro=0xCAFEBABE e superiore=0xDEADBEEF otterrei tutte le piastrelle che hanno come sinistro 0xCAFEBABE e come superiore 0xDEADBEEF. Quindi quando vai a prendere tutte le possibili piastrelle da considerare per una data posizione prendi il lato inferiore della piastrella subito sopra e il lato destro della piastrella subito a sinistra, poi ottieni rapidamente quali sono le possibili piastrelle che possono andare nella posizione che stai considerando.
Per gestire i casi in cui manca la piastrella superiore (siamo nella prima riga) o quella a sinistra (siamo nella prima colonna) puoi crearti due array che associano solo il lato sinistro o superiore a tutte le piastrelle che lo hanno. Ovviamente per la prima piastrella, che non si può basare su nessun’altra, devi provare tutte le possibilità.
Considera che per ogni lato di una piastrella ci sono 2^10 = 1024 possibilità, mentre in totale puoi avere solo 50 piastrelle, quindi normalmente questa ricerca ti permetterebbe di ottenere una singola piastrella per ogni posizione (ovviamente in base alle piastrelle già posizionate) invece di doverle provare tutte e 50.
Nota: in questo post assumo, per semplicità, che posizioni le piastrelle a partire da in alto a sinistra lavorando riga per riga. Se l’ordine che usi è differente non dovrebbe essere difficile adattare quanto scritto.
Scusami ma non ti seguo.
Non è quello che ho fatto con il vettore di adiacenze?
Si, e quello che ti sto consgliando di fare è utilizzare anche una matrice di adiacenze che dati entrambi i lati (e non solamente uno come fai nei due vettori) ti dia le piastrelle da utilizzare. Ho provato a modificare la mia soluzione in modo da non utilizzare la matrice e va fuori tempo limite sugli ultimi testcase.
Buona idea. Non avevo capito.
Comunque… ho provato a sottomettere la soluzione ufficiale; ha preso come ci si aspetterebbe il massimo.
la mia è molto simile, l’unica differenza è che io uso una struct di 4 variabili short, mentre nell’altro si usano 4 vettori indipendenti, uno per ogni dimensione… che sia questo a farmi andare fuori tempo limite? probabilmente perché a basso livello fa tante volte pushing di 4 variabili diverse al posto di una…? boh.
(ho provato la mia soluzione prima di leggere l’ufficiale, tranquilli mi sono impegnato 
)
Provo a fare come dici tu, dovrei ottimizzare un bel po’.
Non credo sia il modo in cui salvi le piastrelle, io le ho definite con una struct di 4 interi come te:
struct Matrix
{
int top, bottom;
int left, right;
};
A proposito, dove sono le soluzioni ufficiali?
Infatti. Ho provato a salvare le piastrelle con vettori paralleli, e non ho ottenuto alcun miglioramento.
Ho capito cos’era che rallentava il runtime: il reference… Non l’avrei detto che era per questa sciocchezza. Togliendolo ottengo 100/100
Ora provo a fare l’intersect e vedo come va
Ho provato e ho diminuito ancora il runtime.
Adesso mi chiedo cos’altro possa applicare per diminuire ancor di più il runtime