Sono riuscito a fare 90/100 su solitario, ho semplicemente generato tutte le possibili giocate e contato il numero maggiore di x in quelle valide, tuttavia l’ultimo subtask dà timeout/errori.
Ho visto dalla soluzione che per quel subtask in particolare c’è una formula matematica, che è questa:
if (N*M > 25) return N*M*11/20+1;
L’ultimo subtask è l’unico il cui valore N*M supera 25, tuttavia non riesco a capire come funzioni.
Qualche delucidazione?
Purtroppo non so aiutarti sul perché della formula matematica, comunque provando tutte le combinazioni puoi comunque stare entro ai limiti di tempo con qualche ottimizzazione, in particolare se stai usando la ricorsione prova a pensare se puoi trascurare qualche caso/ramo 
Sto provando a risolvere il tris in solitaria. Qualche subtest riesco a risolvere, ma purtroppo faccio 0/100.
Sto ancora cercando di capire come usare al meglio il backtracking.
Basandomi sull’esempio delle soluzioni in un sudoku ho scritto questo codice:
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
using namespace std;
static int totale;
bool isSafe(std::vector<std::vector<int>> tris, int row, int col){
int numberOfRows = tris.size();
int numberOfCols = tris[0].size();
tris[row][col] = 1;
//check three on a row
int count = 0;
for (int c=0;c<numberOfCols; c++){
if (tris[row][c] == 1){
count++;
if (count >=3){
return false;
}
}
else
count = 0;
}
//check three on a col
count = 0;
for (int r=0;r<numberOfRows; r++){
if (tris[r][col] == 1){
count++;
if (count >=3){
return false;
}
}
else
count = 0;
}
//check three on a diag
count = 0;
for (int r=0; r<numberOfRows; r++){
for (int c=0; c < numberOfCols; c++){
if (r==c){
if (tris[r][c]==1){
count++;
if (count >= 3)
return false;
}
else
count = 0;
}
}
}
return true;
}
bool gioca(std::vector<std::vector<int>> tris, int row, int col) {
int numberOfRows = tris.size();
int numberOfCols = tris[0].size();
if (row == numberOfRows-1 && col == numberOfCols)
return true;
if (col == numberOfCols){
row++;
col = 0;
}
if (tris[row][col] > 0)
return gioca(tris, row, col+1);
for (int num=1; num<=numberOfRows; num++){
if (isSafe(tris, row, col)){
tris[row][col] = 1;
totale++;
if (gioca(tris,row, col+1))
return true;
}
tris[row][col] = 0;
}
return false;
}
int main() {
FILE *fr, *fw;
int N, M;
totale = 0;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(2 == fscanf(fr, "%d %d", &N, &M));
std::vector<std::vector<int>> tris;
for (int i=0; i<N;i++){
std::vector<int>row;
for (int j=0; j<M; j++){
row.push_back(0);
}
tris.push_back(row);
}
gioca(tris, 0, 0);
fprintf(fw, "%d\n", totale);
cout << totale << endl;
fclose(fr);
fclose(fw);
return 0;
}
Qualcuno mi darebbe una mano a capire come sistemare il mio codice?
Quello che non capisco è quando aggiornare il totale delle X che si possono mettere sulla griglia senza fare tris.
potresti commentare il tuo codice?
La funzione isSafe( ) mi dice se la configurazione attuale è accettabile. Controlla quindi se ci sono tre elementi consecutivi sulla riga, sulla colonna o sulla diagonale principale. Manca da implementare la diagionale secondaria.
La funzione gioca( ) è la funzione ricorsiva che permette di scorrere tutto il tris.
Non mi è ancora molto chiaro come scorrere il tris e tenere traccia dei valori inseriti.
Ho quindi preso spunto dal backtracking applicato per risolvere il sudoku, dato che mi sembrava un problema simile.
Nella funzione gioca( ) controllo inizialmente se son arrivato a fine schema (ultima cella in basso a destra allora termino il tris). Se la colonna attuale è uguale al numero di colonne, rimetto la colonna a 0 e aggiorno la riga.
Se nel tris c’è già una X (rappresentata con un 1 nel vector di vector) allora vado alla cella row, col+1.
Infine nel ciclo for itero il procedimento più volte per scorrere tutto il tris.
Allora, io ancora non sono riuscito a risolvere il codice, ma penso che la soluzione sia una formula matematica o comunque più formule matematiche messe assieme con uno o più if
Consigli:
Penso si debbano tenere due variabili, una che memorizzi il risultato “parziale” per ciascuna delle iterazioni fino ad arrivare alla fine della griglia, ed una che tenga il massimo risultato ottenuto dopo aver generato tutti i casi possibili.
Quindi, ogni volta che arrivi all’ultima casella della griglia in ciascuna iterazione della funzione ricorsiva devi controllare se il risultato parziale è maggiore di quello massimo memorizzato ed eventualmente aggiornarlo.
Per quanto riguarda la variabile con il risultato parziale invece, io la ho aggiornata ogni volta che ho aggiunto una x sulla griglia, passandola come argomento della funzione ricorsiva.
Inoltre, per generare tutti i casi possibili penso tu debba contare anche quelli in cui non aggiungi la x nella casella in cui ti trovi e vai avanti a quella dopo. Non sono sicuro se questo passo ci sia già nel tuo codice.
Infine dovrai trovare un modo di ottimizzare il codice per non andare fuori tempo. Hai una variabile che rappresenta il risultato parziale di quella iterazione ed una che rappresenta il massimo risultato ottenuto fino ad ora. Usando queste due e tenendo in mente la casella in cui ti trovi, c’è un modo di sapere che di sicuro il risultato di questo ramo non sarà superiore al massimo che hai già?
Facendo tutto questo si può fare 100/100 usando backtracking.
Da quello che ho capito, questa più che una formula è un’approssimazione: si è notato che in griglie più grandi il numero di caselle riempibili senza formare tris si aggira al 55% delle caselle totali.
Confermo. Aggiungo che questo rapporto oltre a essere ottimale per questo problema, risulta essere ottimale in qualunque problema contenente euristiche. Ad esempio nel problema oii_foglietto é sempre ottimale fare pieghe lunghe 77/128 bit. Vi chiedo solo il favore, in caso la utilizzaste, di mettere un commento a fianco // this ratio is contributed by Matteo Arcari