Salve,
oggi nel secondo round delle OIS è uscito il problema findperm. Il problema era interattivo, e dato un intero N (1 \leq N \leq 1000), che rappresentava la lunghezza di un vettore P contenente tutti i numeri da 1 a N, il nostro obbiettivo era indovinare una permutazione di P nascosta, potendo fare Q richieste al problema del tipo “? i j” (1\leq i,j, \leq N) e per ognuna di queste Q domande il problema doveva rispondere con la posizione del bit più significativo risultante dall’operazione P_i \& P_j ovvero il bitwise and tra i due valori, dove ricordo P essere la permutazione da indovinare, se i due valori non avessero bit in comune, quindi P_i\&P_j = 0 allora avrebbe restituito -1.
quindi facendo un esempio, con N = 5 e P = \{4, 3, 2, 5, 1\} se faccio la richiesta “? 2 4” allora il problema mi restituirà P_2 \& P_4 = 3\&5 = 011\&101 = 001 \to 0 essendo il bit più significativo in posizione 0.
Il problema valutava il mio algoritmo in base alle domande inviate, nel caso in cui Q \geq 30000 avrei ricevuto 0 punti e così via con la suddivisione in varie subtask che non mi serve nominare.
Dato tutto questo, io ho avuto vari problemi con il mio algoritmo ottenendo in ogni testcase l’errore “Execution Killed” però stando nei limiti di memoria imposti dal problema. Ho pensato quindi che l’unica cosa possibile è o sbagliare o far sbagliare qualche accesso a qualche vettore o cose del genere. Dopo vari tentativi di fixare, creo un altro file da capo dove mando una richiesta a caso e stampo una permutazione a caso, per riuscire ad ottenere almeno “Output isn’t correct”.
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
cout << "? " << 1 << " " << 1 << endl;
cout.flush();
int x; cin >> x;
cout << "! ";
for(int i = 1; i <= N; ++i){
cout << i << " ";
}
cout << endl;
cout.flush();
return 0;
}
Questa tattica funziona, e infatti ottengo ad ogni testcase “Output isn’t correct” e non più “Execution killed”. Allora ho provato a confrontare i due codici ma qualcosa non andava, non sembrava fare niente di tanto diverso il codice “serio” rispetto a quello di “debug”, tranne che quello “serio” mandava più domande di quello “debug”.
Quindi modifico quello “debug” facendo la stessa domanda 25000 volte, in modo di rientrare di molto nel limite imposto dal problema ma comunque sparare più domande. (anche se superato mi avrebbe dovuto dare TLE, o almeno così diceva il testo)
#include <bits/stdc++.h>
using namespace std;
int main(){
int N; cin >> N;
for(int i = 0; i < 25000; ++i){
cout << "? " << 1 << " " << 1 << endl;
cout.flush();
int x; cin >> x;
}
cout << "! ";
for(int i = 1; i <= N; ++i){
cout << i << " ";
}
cout << endl;
cout.flush();
return 0;
}
Disastro, tutti i testcase “Execution killed” tranne l’esempio, ho perso tipo 40 min di gara solamente per sto problema, pensando di poterlo risolvere ma niente da fare, ed è un gran peccato.
Sapete dirmi dov è l’errore? Sto rosicando tantissimo anche perchè non è nemmeno una tecnica di programmazione su cui allenarsi o cose del genere, quindi se avrei dovuto fare cose tipo dare una specie di pausa per non sovraccaricare l’input, mi darebbe fastidio perchè è una cosa che andrebbe messa nel testo e che non sono tenuto a sapere.
Queste sono le mie considerazioni a caldo, quindi non voglio nemmeno sembrare arrogante, è probabilissimo che abbia letto male il testo o magari mi è scappato qualche errore che non ho visto. Se non fosse così vi prego di farmi capire cosa sbaglio almeno evito di perseverare la prossima volta. Grazie in anticipo per le eventuali risposte.
?