# Think About it: perm

**URL:** <https://forum.olinfo.it/t/think-about-it-perm/5900>\
**Category:** Algoritmi\
**Created:** [16 Novembre 2019, 12:11pm UTC](https://forum.olinfo.it/t/think-about-it-perm/5900 "2019-11-16T12:11:00Z")\
**Posts on this page:** 1\
**Showing post:** 5

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [30 Novembre 2019, 6:02pm UTC](https://forum.olinfo.it/t/think-about-it-perm/5900/5 "2019-11-30T18:02:49Z")

</div>

# Editorial

Con la pubblicazione di [sfere](https://forum.olinfo.it/t/think-about-it-sfere/5945) 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)

```auto
#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](http://www.cplusplus.com/reference/algorithm/next_permutation/) che ci permette di analizzare tutte le righe della matrice in ordine lessicografico.  
Complessità temporale: O(N \* N!)  
Complessità spaziale: O(N!)

```auto
#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)

```auto
#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:

```auto
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 😄

---

_[View the full topic](https://forum.olinfo.it/t/think-about-it-perm/5900)._