Buongiorno, ho problemi di Execution Timed Out nel problema binary chess.
Ho applicato una recursion calcolando tutte le possibili combinazioni. Se un rook uccide un bishop o contrario allora ritorno 0. Se arrivo alla fine ritorno 1.
La memoizzazione memorizza le coppie di rook o bishop che non possono stare nella stessa combinazione.
E’ possibile ottimizzare questa risoluzione o devo cambiare metodo?
Grazie in anticipo.
#include <bits/stdc++.h>
using namespace std;
int n;
vector <pair <int, bool>> p[200000][2];
long long int risolvi(bool rb, int i, int x[], int y[], bool v[])
{
for(pair<int, bool> e : p[i][rb]) //memoizzazione
{
if(v[e.first] == e.second)
return 0;
}
v[i] = rb;
if(rb == 0) //rook
{
for(int k = i - 1; k >= 0; k--)
{
if(v[k] == 1)
{
if((x[k] == x[i] || y[k] == y[i]))
{
p[i][rb].push_back(make_pair(k, v[k]));
return 0;
}
if((abs(x[k] - x[i]) == abs(y[k] - y[i])))
{
p[i][rb].push_back(make_pair(k, v[k]));
return 0;
}
}
}
}
else
{
for(int k = i - 1; k >= 0; k--) //alfiere
{
if(v[k] == 0)
{
if((x[k] == x[i] || y[k] == y[i]))
{
p[i][rb].push_back(make_pair(k, v[k]));
return 0;
}
if((abs(x[k] - x[i]) == abs(y[k] - y[i])))
{
p[i][rb].push_back(make_pair(k, v[k]));
return 0;
}
}
}
}
if(i >= n-1)
{
return 1;
}
return (risolvi(0, i+1, x, y, v) + risolvi(1, i+1, x, y, v));
}
int main()
{
ifstream in("input.txt");
int r, c;
in >> r >> c >> n;
int x[n], y[n];
for(int i = 0; i < n; i++)
{
in >> x[i] >> y[i];
}
bool v[n] = {false};
long long int a = risolvi(0, 0, x, y, v);
long long int b = risolvi(1, 0, x, y, v);
long long int ris;
ris = a+b;
cout << ris % (long long int)(pow(10, 9) + 7);
return 0;
}
Credo che il ragionamento di fondo del tuo approccio sia troppo lento purtroppo. Prova a rispondere a questa domanda: se 2 pezzi si vedono (sono sulla stessa riga/colonna/diagonale) allora cosa puoi dire riguardo il loro “tipo”?
Esatto, immagino tu abbia notato come il ragionamento possa essere esteso transitivamente. Ossia, dati 3 pezzi a, b, c tali che a e b si vedono e b e c si vedono, anche a e c devono essere dello stesso tipo, a prescindere dal fatto che si vedano o meno. Dopo questa considerazione riesci a trovare un modo per riformulare il problema originale in modo che sia più semplice da risolvere?
Io avevo già implementato questo ragionamento creando delle zone in cui i pezzi si vedono tra di loro ma non vedono quelli delle altre zone. Il massimo che sono riuscito ad ottenere è stato 30/100 per via del tempo, è un problema di python o c’è una qualche ottimizzazione che non ho trovato?
R, C, N = map(int, input().strip().split())
rr = [0 for i in range(N)]
cc = [0 for i in range(N)]
alr = [] # zone
MOD = 10 ** 9 + 7
lu = 0 # numero di zone
for i in range(N):
rr[i], cc[i] = map(int, input().strip().split())
coll = [] # collisioni, ovvero le zone a cui il nuovo pezzo appartiene
new = [i] # nuova zona
for j in range(lu): # scorro nelle zone
for h in alr[j]: # scorro tra i pezzi della zona
if cc[i] == cc[h] or rr[i] == rr[h] or (abs(rr[h] - rr[i]) == abs(
cc[h] - cc[i])): # se il nuovo pezzo è sulla stessa fila, riga o diagonale
new += alr[j]
coll.append(j)
lu -= 1
break
for k in coll[::-1]:
alr.pop(k)
alr.append(new)
lu += 1
lu %= MOD
print((2**lu%MOD))
Il ragionamento è giusto, ma il modo in cui crei gli insiemi che chiami zone è troppo lento. In particolare, tu confronti ogni pezzo con ogni altro pezzo sulla scacchiera, ottenendo una complessità di O(N^2), devi trovare un modo per farlo in O(NlogN). Conosci algoritmi che ti permettono partendo di N insiemi di unire tali insiemi in maniera veloce (e allo stesso tempo ti permettono di capire a quale insieme appartiene ogni elemento)
