Studio amico, ABC

[lukecavabarrett]

Non devi implementarla, è già definita dentro la classe pair.
Vai su cplusplus.com per vedere la documentazione di ogni cosa contenuta nella STL

[frakkiobello]

OK, ma mi da comunque questi errori che non so come risolvere
https://pastebin.com/25mNVaES
Non capisco perche ma credo ci siano problemi con la funzione find

[dp_1]

L’errore è che tu utilizzi un set<pair<int, int> >, quindi la ricerca vuole un pair<int, int> come elemento da trovare. Se non ho capito male quello che vuoi ottenere, ti consiglio invece di usare una map<int, int>, che ti permette di cercare per il primo valore e trovare il secondo. In generale, un set ha solo le chiavi, mentre una map associa ad ogni chiave un valore.

btw, sicuro che ti serva un set/map e non basti un array?

[lukecavabarrett]

io in checksum usai una std::map<int,int> o forse std::unordered_map<int,int>

[dp_1]

Io un ignorantissimo array ¯\_(ツ)_/¯

[frakkiobello]

Ma perché per ogni testcase mi dice:
Soluzione errata: non è stato identificato un checksum invalido!

https://pastebin.com/2p70WMjp

[dp_1]

Prendiamo per esempio il caso in cui arriva prima il 7 e poi il 14. Il 7, essendo primo, lascerà tmp vuoto e quindi ci inserisci 7 stesso. Quando arriva il 14, in tmp inserisci solo 2, visto che 7 > \sqrt{14} ignori completamente il fattore 7, quindi dici che il 14 è un checksum valido quando in realtà non lo è.

[frakkiobello]

for(int i=2;i<=radice;i++)
    if(checksum%i==0)
    {
        tmp.push_back(make_pair(i, checksum));
        tmp.push_back(make_pair(checksum/i, checksum));
    }

anche con questa modifica da tutti i pacchetti invalidi
ma prendendo il primo caso d’esempio:
6 10
10 7 4 9 5 6
l array
2 5 e li mette a vero
poi con il 7 trovando tmp.size()==0 lo inserisce
2 5 7
poi con il 4 mette in coda il 2 poi quando va a svuotarla cede che il 2 è gia vero e allora ritorna 10 no?

[jkm99zambo]

Beh, ma sinceramente non era nemmeno necessario riordinare, bastava accumulare tutti i valori in un array di 10 elementi e poi fare i controlli direttamente su quei valori

[jkm99zambo]

Io sto usando una map, ma (a parte che fuori dai casi di esempio mi da un sacco di errori dove avrò sbagliato qualcosa di stupido…) ho un out of time non da nulla negli ultimi test case.
Ora mi sto chiedendo se ricercare tutti i divisori, buttarli dentro il dizionario e cercarli al suo interno non sia sbagliato

[lukecavabarrett]

I divisori di N sono al più \log_{2} N. Non credo il TLE sia dovuto a ciò, piuttosto: quanto impieghi a scomporre ogni intero?

[dp_1]

Yup, hai ragione. Le due opzioni sono praticamente equivalenti in questo caso.

[jkm99zambo]

Ok, forse, accorgendomi che dava errori, sono andato in modo ignorante a cercare N divisori. Alla fine sto andando a cercarli da 2 a N, e probabilmente é questo che mi dà il TLE. Oggi pomeriggio rifaccio quella parte lì e vedo se trovo gli errori. Grazie

[frakkiobello]

Io ancora non riesco a capire il problema del mio codice: https://pastebin.com/me6RmaH1
Ho corretto qualche piccolo errore che era presente nel codice(alcuni anche molto imbarazzanti )

Ho sostituito principalmente la deque dove inserivo i fattori primi che compongono ogni numero con un set, per una motivazione ben precisa per esempio nel caso del 9, io scomponevo ed inserivo nella mia deque 2 3 e quando poi andavo a verificare se quel checksum era gia stato usato: con il primo funzionava ma il secondo trovava la variabile booleana già a true e quindi stampava 9, quando in realtà non dovrebbe stampare nulla, ma questo l ho risolto.
Adesso non riesco a capire dove è l’errore (nel trovare gli errori nei codici sono veramente scarso), perché credo che il mio algoritmo lavori nel modo corretto, come già detto io scompongo ogni numero in fattori e se quel fattore era già stato trovato allora dico il nome del pacchetto che lo ha trovato in precedenza, ma quello che non riesco a capire del tutto è come è possibile che si verifichino entrambi gli errori: ossia “Soluzione errata: un checksum valido è stato considerato invalido!” e “Soluzione errata: in un checksum invalido è stato indicato un riferimento a un pacchetto che non creava problemi per tale checksum”.

Qualche aiutino?

[filippos]

@frakkiobello

Qualche aiutino?

Non sarebbe più corretto aprire un’altra discussione, in cui magari linkare questa?
Così almeno è chiaro per tutti quelli che cercano informazioni sul problema checksum.

Comunque credo tu debba stare attento a quando vai ad inserire i valori nel set, magari rileggendo cosa dice il testo a riguardo dei numeri a cui devi fare riferimento per la validità di ogni singolo checksum

[peppe17]

per favore potresti spiegarmi come funzionano le ultime 2 righe di codice?

[frakkiobello]

Se ti riferisci a

 for(int i = 1; i < 11; i++) for(int j = 0; j < freq[i]; j++)
        *arr++ = i;

In pratica per ogni valore i da 1 a 10, effettua per freq[i] volte (dove freq[i] rappresenta quante volte era presente i nell’array originale) questa istruzione: *arr++ = i;

• arr rappresenta un puntatore alla prima posizione libera (infatti inizialmente rappresenta l’inizio dell’array) .
• *arr rappresenta il valore contenuto nella cella di memoria puntata da arr.
• fare arr++ significa spostarsi alla cella di memoria successiva (sapendo che l’array è memorizzato in maniere contigua in memoria significa spostarsi sull’elemento successivo)

Quindi nel suo complesso quell’istruzione mette nella cella dell’array corrente il valore i e poi passa alla cella successiva.

[peppe17]

@dp_1

void countingsort(int *arr, int N)
{
    int freq[11];
    for(int i = 1; i < 11; i++) freq[i] = 0;
    for(int i = 0; i < N; i++) freq[arr[i]]++;
    for(int i = 1; i < 11; i++) for(int j = 0; j < freq[i]; j++)
        *arr++ = i;
}

non capisco perchè fare il ++ nell’array

[frakkiobello]

Quell’istruzione è l’equivalente di fare:
*arr=i che setta la cella di memoria attuale ad i.
arr++ ossia passa alla cella successiva dell’array. Se non lo facesse allora tutti i valori verrebbero inseriti nella prima posizione.

[peppe17]

quindi PRIMA assegna e poi passa alla cella successiva è chiaro adesso