Think About it: perm

Algoritmi
5

Editorial

Con la pubblicazione di sfere colgo l’occasione per scrivere l’editorial di questo problema. Come a mio solito, lo analizzerò nei suoi vari piccoli subtasks.

Subtask 1 ( 0pt)

Il primo subtask riguarda i casi d’esempio. Niente da notare in particolare oltre già quello indicato nelle spiegazioni del testo. Per risolvere questo subtask è possibile scrivere 3 condizioni che testano il valore di N.
Complessità temporale: O(1)
Complessità spaziale: O(1)

#include <bits/stdc++.h>

using namespace std;

int trova(int N){
  if(N == 1)return 1;
  if(N == 2)return 2;
  if(N == 3)return 6;
  return 0;
}

Subtask 2 (10pt)

Il secondo subtask ha un valore di N molto basso, quindi possiamo scrivere una soluzione a forza bruta che provi a trovare la lunghezza della sequenza maggiore. Una grande mano ci è data dalla funzione next_permutation che ci permette di analizzare tutte le righe della matrice in ordine lessicografico.
Complessità temporale: O(N * N!)
Complessità spaziale: O(N!)

#include <bits/stdc++.h>

using namespace std;

int trova(int N){
  vector < vector <int> > matrix, dp;
  vector <int> v(N, 0);
  for(int i = 0; i < N; i++){
    v[i] = i + 1;
  }
  do{
    matrix.push_back(v);
    dp.push_back(vector <int> (N, 1));
  }while(next_permutation(v.begin(), v.end()));
  int ret = 0;
  for(int i = 0; i < (int) matrix.size(); i++){
    for(int j = 0; j < N; j++){
      int best = 1;
      for(int z = -1; z <= 1; z++){
        if(i - 1 >= 0 && j + z >= 0 && j + z < N && matrix[i][j] == matrix[i - 1][j + z]){
          best = max(best, dp[i - 1][j + z] + 1);
        }
      }
      dp[i][j] = best;
      ret = max(ret, best);
    }
  }
  return ret;
}

Subtask 3 (10pt)

Le assunzioni su N rimangono piccole, ma non abbastanza da permetterci di tenere in memoria la matrice in se. Dal codice precedente possiamo notare che la dimensione massima per l’i-esima riga è calcolabile conoscendo solo i risultati della (i-1)-esima riga.
Complessità temporale: O(N * N!)
Complessità spaziale: O(N)

#include <bits/stdc++.h>

using namespace std;

int trova(int N){
  vector <int> dp0(N, 0), dp1(N, 0);
  vector <int> v0(N, 0), v1(N, 0);
  for(int i = 0; i < N; i++){
    v1[i] = i;
  }
  int ret = 0;
  do{
    for(int i = 0; i < N; i++){
      int ans = 1;
      for(int j = -1; j <= 1; j++){
        int z = i + j;
        if(z >= 0 && z < N && v1[i] == v0[z]){
          ans = max(ans, dp0[z] + 1);
        }
      }
      dp1[i] = ans;
      ret = max(ret, ans);
    }
    v0 = v1;
    dp0 = dp1;
  }while(next_permutation(v1.begin(), v1.end()));
  return ret;
}

Subtask 4 (10pt)

Il valore massimo di N non ci è dato saperlo, ma sappiamo che la lunghezza massima della sequenza è inferiore a 10^9 + 7. Da questa informazione possiamo utilizzare questo subtask per verificare che un eventuale soluzione potrebbe essere corretta ma sbagli per i vari moduli.

Subtask 5 (70pt)

Il subtask finale, colui che vale la maggior parte del punteggio del problema. Arrivato a questo subtask tutte le nostre soluzioni finora non hanno margine di miglioramento. Come faremo a risolvere questo problema? Si inizia cercando di verificare l’esistenza di qualche pattern nella matrice. A questo proposito abbiamo le nostre care e belle soluzioni precedentemente verificate (grazie ai subtask) pronte a essere modificate restituendo su video qualche informazione utile per un determinato N. Una prima idea è di stampare quali sono le sequenze più grandi e su quale riga si fermino. Da tali informazioni possiamo estrapolare la seguente tabella:

N Lunghezza Valore A Riga A Valore B Riga B
3 6 0 5 2 5
4 12 0 11 3 23
5 36 0 35 4 119
6 156 0 155 5 719
7 876 0 875 6 5039

Dove Valore A e Riga A indicano l’elemento con il quale abbiamo realizzato la sequenza massima e in quale riga finisce. Lo stesso vale per Valore B e Riga B. Estrapolate le informazioni e schematizzate si può benissimo notare che le sequenze massime sono due e sono sempre costituite dal valore più piccolo e il più grande. Quindi possiamo incominciare a trovare una pattern per l’elemento più piccolo. Prendiamo in considerazione le matrice per N = 4:

0 1 2 3 
0 1 3 2 
0 2 1 3 
0 2 3 1 
0 3 1 2 
0 3 2 1 
1 0 2 3 
1 0 3 2
1 2 0 3 
1 2 3 0 
1 3 0 2 
1 3 2 0 
2 0 1 3 
2 0 3 1 
2 1 0 3 
2 1 3 0 
2 3 0 1 
2 3 1 0 
3 0 1 2 
3 0 2 1 
3 1 0 2 
3 1 2 0 
3 2 0 1 
3 2 1 0

È chiaramente visibile che il valore più piccolo presente nella matrice cambi colonna solo dopo un determinato numero di volte. Ma a quanto equivarrà questo numero? Questo numero equivarrà al numero di permutazioni possibili con il numero di elementi presenti alla sua destra. Inizialmente solo il valore più piccolo rimane “fermo” permettendo di far muovere gli N - 1 valori in tutte le loro (N - 1)! permutazioni possibili. Successivamente si sposta di colonna e rimangono “fermi” due valori permettendo a N - 2 elementi di comporre tutte le loro (N - 2)! permutazioni possibili, dopo rimangono fermi N - 3 elementi… e cosi proseguendo. Fino ad arrivare al punto in cui il valore più piccolo arrivi all’ultima colonna, per poi finire con gli ultimi due spostamenti. Da questa pattern possiamo individuare la seguente funzione per trovare la lunghezza massima:

f(N)= \begin{cases} 1,& \mbox{se }N = 1 \\ 2,& \mbox{se }N = 2 \\ (\sum_{i = 0}^{N - 1} i!) + 2,& \mbox{se } N \ge3 \end{cases}

Vi ricordo che nel calcolo della soluzione di utilizzare il modulo.
Complessità temporale: O(N)
Complessità spaziale: costante.

Conclusioni

Spero che l’esercizio vi sia piaciuto, e che l’editorial non risulti troppo pesante. Per ogni dubbio, o considerazione sul editorial basta lasciare un piccolo commento. Ci fa piacere rispondervi :smile:

2 Mi Piace