Buongiorno, ho elaborato una soluzione per il problema Specchi, ma la mia soluzione impiega 3,2 secondi in alcuni casi, ed il limite è 3 secondi. La mia idea è stata creare una matrice, aggiungere gli specchi richiesti e una volta chiamata la funzione calcola, spostarsi nella matrice modificando il percorso nel caso vengano trovati degli specchi. Potete consigliarmi soluzioni migliori?
3 Mi Piace
Il problema è la complessità, se l’esecuzione supera i 3 secondi il programma viene killato (quindi viene visualizzato un tempo leggermente superiore anche se in realtà impiegherebbe molto di più)
MrBrionix
4 Mi Piace
Suggerisco l’utilizzo di un BBST + skiplist per cominciare
4 Mi Piace
Scusa l’ignoranza, ma cosa sarebbe?
Sono 2 strutture dati: BBST sta per Balanced Binary Seach Tree, ovvero albero binario di ricerca bilanciato, mentre la skip list è sostanzialmente una lista ordinata che permette di eseguire inserimenti, ricerche e cancellazioni in tempo logaritmico, proprio come in un BBST.
In ogni caso, la tua soluzione dovrebbe avere complessità O(QRC), che è troppo visti i constraint imposti dal problema. Inoltre è strano che tu riesca ad allocare una matrice abbastanza grande dal momento che nel caso pessimo e supponendo che tu l’abbia dichiarata come matrice di char dovrebbe occupare circa 10 GB di memoria. 
1 Mi Piace
Mh, non ne ho mai sentito parlare, non è che potresti farmi un esempio di implementazione?
Le implementazioni sono abbastanza complesse e pressoché impossibili da ricordare se non conosci la teoria alla base di queste strutture. Inoltre, per quanto riguarda i BBST ne esistono moltissimi (AVL, red-black, scapegoat…), in particolare io utilizzo i treap spiegati in questa guida che ha anche una seconda parte.
In ogni caso, se sei all’inizio sarebbe meglio che iniziassi studiando qualche struttura più semplice, dal momento che quelle appena citate sono molto potenti e interessanti ma inutili per la maggior parte degli esercizi di competitive programming (almeno per quanto riguarda quelli semplici o di media difficoltà). Infatti la STL del C++ contiene già svariate classi che offrono le funzionalità di base di un BBST (std::set e std::map), mentre la necessità di implementarne uno da 0 si presenta solo in casi particolari quando i metodi messi a disposizione dalla STL si rivelano insufficienti, come nell’esercizio vasi2.
Tra le strutture dati che ti consiglio di imparare, in quanto estremamente utili, ci sono Fenwick Tree e Segment Tree, inoltre faresti bene ad imparare il funzionamento dei Max/Min-Heap necessari per poi passare ai Treap. Mi rendo conto che è parecchia roba ma con calma prima o poi si riesce a fare tutto. 
2 Mi Piace
Ok, grazie. Un’ultima domanda, come può un albero di ricerca binario essere utile in questo problema? Non capisco bene il nesso con la matrice.
Sinceramente non so dirti con certezza in che modo possa essere utile perché provai a risolvere quel problema quasi due anni fa quando avevo ancora pochissime conoscenze riguardo ad algoritmi e strutture dati. Comunque, l’idea della matrice è da abbandonare completamente perchè come ti ho già detto occuperebbe troppa memoria! Io ricordo che “all’epoca” creai un grafo dove i nodi erano gli specchi e inserivo un arco tra due specchi A e B nel caso in cui lo specchio A riflettesse la luce sullo specchio B e viceversa. Inoltre inserivo 2(R+C) nodi fittizi che rappresentavano le entrate (e di conseguenza anche le uscite) del raggio di luce. Quindi, ogni volta in cui veniva spedito un raggio di luce facevo una visita del grafo stando attento a rispettare le direzioni fino a quando non giungevo su uno dei nodi del bordo griglia. Tuttavia, questa soluzione (con l’aggiunta di alcune ottimizzazioni) mi ha permesso di fare solo 80/100 punti, perchè nel caso pessimo la complessità del mio algoritmo era O(Q2) o O(Q2log(RC)) (non ricordo). Detto questo, suppongo che l’utilizzo degli alberi penso potesse essere quello di percorrere il cammino nel grafo più velocemente, skippando alcuni nodi inutili, anche se non ne sono sicuro perché come già detto, non ho più provato a risolverlo dopo quella volta. 
1 Mi Piace
Comunque non per smorzare gli animi però tenete anche conto del fatto che, in gara, nessuno ha fatto più di 80 punti su specchi… 
anzi, guardando la classifica di quell’anno potete vedere che tra le 5 medaglie d’oro c’è anche chi ha fatto 0 in quel task… quindi @Domilanza2002 se il tuo scopo è allenarti per le OII valuta se magari ha senso mettere un attimo da parte i BBST e cercare intanto di fare 80/100 e poi magari passare a un altro task 
3 Mi Piace
Dato che mi sono qualificato per le nazionali ho voluto provare a fare i problemi dell’anno scorso, anche se ancora devo rivedere meglio la teoria dei grafi e la programmazione dinamica. Oltre programmazione dinamica, teoria dei grafi(BFS,DFS,dijkstra),ricorsione,puntatori e struct cosa mi consigliate di studiare? E per quanto riguarda le strutture dati quali mi consigliate di imparare ad utilizzare?
Per o grafi ti consiglio di aggiungere Union Find Disjoint Sets(che può tornarti utili anche in altri contesti), Minimum Spanning Tree, e qualcosa sugli alberi come LCA.
Per la programmazione dinamica l’unico consiglio è quello di esercitarti molto ;D.
Poi cerca di guardare i Segment Tree ed i Fenwick Tree che sono utilissimi.
Allenati anche a risolvere problemi che magari ti richiedono anche 2 o 3 orette considerando che alla finale avrai molto tempo.
2 Mi Piace
Oltre a ciò che ti ha già detto @frakkiobello ti consiglio di imparare ad usare i container della STL e le funzioni della libreria algorithm (ovviamente non tutte ma almeno le principali come lower_bound e upper_bound che funzionano come una ricerca binaria).
Inoltre, nel caso non lo avessi notato, il portale di allenamento ti permette di filtrare i problemi in base alle tecniche richieste per risolverli (anche se questo ti spoilera in parte la soluzione del problema può essere comunque utile per allenarsi), ad esempio DP sta per programmazione dinamica, DS per strutture dati, ecc.
P.S.
Non provare a stabilire la difficoltà di un problema attenendoti ai punti che ti darebbe se riuscissi a risolverlo perchè ci sono alcuni problemi molto difficili, come ad esempio specchi, che valgono poco perchè molte persone sono riuscite a risolvere i subtask e ottenere un punteggio parziale! 
2 Mi Piace
Esattamente, il punteggio inganna parecchio, puoi prendere quel punteggio come: “quanto è facile far tanti punti”, per vedere quanto è facile/difficile risolverlo è più indicativa la scheda statistiche.
1 Mi Piace
Scusate la domanda dopo 4 anni dalla discussione ma in questo caso come si potrebbe a livello di codice memorizzare il grafo, visto che non c’è a prescindere un numero preciso di archi?
Un’idea che mi era venuta ma non so quanto sia furba è usare una mappa e come chiave una pair<int, int> che rapprensentano le coordinate dello specchio sulla griglia e come valore di nuovo una set di pair