Salve, scrivo per chiedere un consiglio sul problema “Washing Socks” (https://training.olinfo.it/#/task/ois_socks/statement) che ho trovato sul sito. Ho tentato diversi approcci in C, ma in tutti supero i limiti di tempo nell’ultimo test dei subtask 3 e 5. Mi rivolgo a voi da inesperto alle prime armi per ricevere pareri; allego di seguito il mio codice, con domande in commento. Mi scuso se queste sono troppo ingenue!
#include <stdio.h>
#include <stdlib.h>
static unsigned counter = 0;
int main(){
unsigned N, C, *c, x, i; // Il tipo scelto è sensato, visti i limiti dettati nel problema?
scanf("%u%u", &N, &C);
c = (unsigned*) calloc(C, sizeof(unsigned)); // Ha senso allocare memoria dinamica? O rallenta troppo in gara?
while(N--){
scanf("%u", &x);
++x;
for(i=0; i<C; i++) // Questa parte è sicuramente debole, posto in seguito un'altra versione
if( !c[i] || c[i]==x ){
counter+=i;
c[i] = x;
break;
}
}
printf("%u", counter);
return 0;
}
Per decidere se il tipo è corretto, valuta quanto grandi possono diventare i valori assunti dalle variabili nel caso peggiore. In questo problema mi pare che la variabile più “problematica” sia counter: quanto può valere nel caso peggiore? (Ovviamente è necessario risolvere il quesito preliminare: individuare qual è il caso peggiore).
A meno di situazioni in cui è necessario litigare con i puntatori, non ha senso complicarsi la vita usando l’allocazione dinamica. Un vettore statico dimensionato correttamente (seguendo i valori massimi, specificati nelle assunzioni del testo) è più che sufficiente e semplifica la vita, soprattutto in gara, evitandoti errori subdoli.
Grazie mille per la risposta; purtroppo il compilatore non mi alloca un vettore c della dimensione massima detta nel testo, ossia 1’000’000’000, e dunque ho pensato di arrangiarmi con la memoria dinamica per risolvere almeno i casi con C non troppo elevati. A questo punto penso di aver capito cosa devo cercare di risolvere: essendo N<=100000, allora i colori distinti delle calze saranno per forza <=N. Tenterò una soluzione diversa!
In generale non puoi allocare un vettore così grande come variabile locale perché supererebbe la dimensione massima dello stack. Pur non essendo buona pratica, nell’ambito della programmazione competitiva puoi sfruttare il fatto che le variabili globali (“fuori dal main”) non hanno questo vincolo.
A prescindere da questo, allocare un miliardo di interi richiede circa 4GB!
Utilissimo, grazie! Ho ricevuto comunque un errore nella compilazione, ma resta una buona informazione. Piuttosto, ho realizzato che una cosa sensata (magari ovvia!) per il problema è mappare i colori delle calze. Mi sono allora spostato sul C++ e ho riscritto la soluzione, e sebbene mi sembri corretta, il giudice dichiara errato l’output nell’ultimo test dei subtask 3 e 5 – vedrò di aggiustarla. Piuttosto, dover stilare daccapo le strutture dati necessario in C mi sembra infattibile durante il tempo di gara. Esistono soluzioni di poche linee di codice che non scomodino la STL del C++?
EDIT. La soluzione in C++ è ora corretta! Resta la domanda: è fattibile il problema in C?
Come ti ha già mostrato @bortoz, possono esistere tecniche ad hoc per risolvere un dato problema (magari guardandolo da una diversa angolazione).
Tuttavia è innegabile come il C++, con la sua estesa STL, sia estremamente più funzionale in situazioni di questo tipo e possa costituire già da solo la differenza tra il riuscire o meno a risolvere un problema durante una gara.
Grazie mille @lucach, e grazie @bortoz per la soluzione in C, l’ho trovata illuminante! In particolare, non avevo pensato all’uso di qsort() e di bsearch() per semplificare la vita. Ne approfitto per chiederti se mi sapresti elencare brevemente una serie di funzioni e strutture dati del C in “stile STL”; esistono ad esempio le liste? Ho in mente la va_list, ma a quanto ho inteso è poco utile nel senso che mi interessa. Purtroppo, al di là delle due sopra nominate non sono al corrente di altre facilitazioni col C.
Mi abbandono a un’ultima curiosità; sono inesperto in fatto di programmazione competitiva, e mi accorgo che per imparare a dovere troverei un grande aiuto nelle soluzioni dei problemi presenti sulla piattaforma di allenamento. Queste esistono da qualche parte? Se no, cosa mi consigliate di guardare per conoscere le pratiche “corrette” per una gara? Ad esempio, tornando alla soluzione in C di @bortoz, l’uso di assert() è superfluo, oppure è saggio nel contesto di una competizione? Sembrerò pignolo, ma sto lottando per capire come scrive il codice un programmatore competitivo, e non solo come lo pensa
Non me ne intendo di C ma non posso che consigliarti di usare il C++ (e tutto ciò di utile che si trova nella STL), è sicuramente conveniente e a maggior ragione se conosci il C non potrai che trovarti meglio
Qui il codice delle submission è privato (ad eccezione di quello che trovi condiviso qui sul forum o su qualche github), tuttavia in altri siti come codeforces le soluzioni sono pubbliche e puoi quindi sbirciare un po’ il codice degli altri. In generale, può essere una buona lettura il libro “Competitive Programming”, di cui puoi certamente trovare un pdf da qualche parte
Grazie @filippos, sono conscio del miglior vantaggio del C++, la domanda era specifica sul C perché ho interesse a migliorarmi con esso prima di abbracciare uno studio approfondito del primo. Piuttosto, chiedo allora se per usare con successo la STL sia sufficiente avere una conoscenza non approfondita del C++, ovvero che abbia solo vaghe idee di cosa siano le classi e poco altro. Basta cioè saper maneggiare solo la superficie dei container, ossia la loro interfaccia ai fini delle gare? Il linguaggio sarà studiato a fondo successivamente, ma non subito.
Ho già in mano il libro che consigli, e so che su CodeForces le sottoposizioni altrui sono pubbliche, ma quello che chiedevo era una fonte più “ufficiale”. Ho bisogno di mettere ordine alle idee e alle conoscenze, e sento la mancanza di una buona sorgente da cui attingere. Davvero le selezioni territoriali, nazionali, e infine le OII non hanno delle soluzioni ufficiali?
Negli ultimi anni si è cercato di creare un booklet per ogni gara che contenesse le soluzioni “ufficiali” ai problemi. Cercando “booklet” su questo forum qua e là trovi alcuni post con i link per scaricarli.
Salve, non riesco a prendere il massimo dei punti (solo 60/100) perchè l’ultimo test della sezione 3) e 5) fallisce sistematicamente. Ho provato anche a sottomettere una delle soluzioni trovate in questo forum per ritrovarmi nella stessa situazione.
Presumo a questo punto che possa essere un problema della batteria di test, errata o mal configurata.
Ogni aiuto è apprezzato grazie.
Probabilmente è un problema di overflow. Quegli ultimi testcase hanno come risposta dei numeri che non stanno in un normale int, è necessario memorizzarli in un long long int.
