Think About it: perm

#1

Per il quarto appuntamento con la rubrica tai vi proponiamo: perm.
Vi ricordo, come ogni volta, che tra circa due settimane uscirà un nuovo problema insieme a un editorial su questo.
Riuscirete a risolvere i miei problemi con la matematica? :laughing:

1 Mi Piace
Think About It: Scavi Fortunati
#2

Guarda sinceramente l’ho letto e poi volevo spararmi😂 2 secondi di constraint e non ho la minima idea di che cosa usare per stare nei tempi

1 Mi Piace
#3

Tra circa 7 giorni verrà pubblicato un nuovo esercizio e l’editoral di questo. Nel frattempo ti rilascio qualche hint. Gli ho ordinati dal meno spoileroso al più:

  1. Prova a scrivere una soluzione a forza bruta e confronta i risultati. La funzione next_permutation potrebbe darti una grossa mano.

  2. Quante sono le sequenze massime e quali sono?

  3. C’è qualche pattern che si ripete?

  4. Riesci a prevedere dove si troverà un numero?

1 Mi Piace
#4

Grazie♥️ forse mi basta il primo hint, non sapevo proprio dell esistenza di una funzione del genere.

#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 quale valore 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
#6 
using namespace std;
int fattoriale(int n)
{
    if(n > 1)
        return (n * fattoriale(n - 1));
    else
        return 1;
}
int trova(int N)
	{
  int out=1;
  if(N==1)
  {
  	return 1;
  }
  if(N==2)
  {
  	return 2;
  }
  for(int i=1;i<N;i++)
  {
    out+=fattoriale(i)%10000000007;
  }
  return out+2;
}

immagino di non aver capito la formula nella funzione, la ho interpretata come la somma dei fattoriali da 1 a N-1 per poi aggiungere 2, ma ho nel subtask 5 i testcase da 27 a 29 con Output isn’t correct. da 30 in poi Execution timed out. Penso che l’errore sia in come calcolo il fattoriale, ma non conosco metodi migliori, grazie in anticipo per qualsiasi correzione e spiegazione

#7

Per il tempo: il fattoriale può essere calcolato direttamente dentro al ciclo for( basta scrivere out+=fact; fact*=i; ). Inoltre, per evitare errori, definisci sia out sia fact come long long int( 10^9+7 sta un int, ma può essere che superi il limite di int prima di applicare il modulo) e metti il modulo anche quando sommi 2

2 Mi Piace
#8

Grazie,effettivamente il problema è anche come interpreto la formula.

#9

Salve, la formula della sommatoria va interpretata includendo gli estremi. Se richiamassimo F(4) otterremo:

F(4) = (\sum_{i = 0}^{4 - 1} i!) + 2 = 0! + 1! + 2! + 3! + 2 = 1 + 1 + 2 + 6 + 2 = 12

Come detto da @battini durante i calcoli sono necessari i long long e il modulo ad ogni operazione, anche nella funzione fattoriale. Inoltre il suggerimento di calcolare il fattoriale durante la somma serve per rendere la complessità lineare e non quadratica.
Se vuoi calcolarti il fattoriale usando la tua funzione potresti salvarti risultati intermedi per non doverli ricalcolare di nuovo con la tecnica della Memoizzazione.

1 Mi Piace
#10 
  long long int fact=0;

  for(long long int i=0;i<N;i++)
  {
    fact=(fact%10000000007)*(i%10000000007);
    if(i==0)
    {
      fact=1%10000000007;
    }
    out=(out%10000000007)+(fact%10000000007);
  }
  return (out+2)%10000000007;

Continuo a non capire :sweat_smile:… Output isn’t correct sempre da 027 a 036,penso di non aver capito come evitare l’overflow.

#11

Aggiungi nel ciclo anche out%=1000000007; oppure scrivi out=((out%10000000007)+(fact%10000000007))%1000000007;
Poi se non l’hai già fatto dichiara anche out come long long int

1 Mi Piace
#12 
  {
   long long int out=0;
  long long int fact=0;
  for(long long int i=0;i<N;i++)
  {
    fact=(fact%10000000007)*(i%10000000007);
    if(i==0)
    {
      fact=1%10000000007;
    }
    out=((out%10000000007)+(fact%10000000007))%1000000007;
     out%=1000000007;
  } 
  return (out+2)%10000000007;
}

stessi errori @battini

#13

Devi fare la stessa cosa che hai fatto per out anche pet fact, cioè fact=((fact%10000000007)*(i%10000000007))%1000000007;

1 Mi Piace
#14

Per evitare di scrivere nel codice più e più volte il valore del modulo puoi dichiarare una costante e utilizzare sempre quella, cosi eviti errori durante i vari copia e incolla. Inoltre potresti scriverti due funzioni apposite che ti eseguano la somma tra due numeri e la moltiplicazione come queste:

const int MOD = 1e9 + 7;

int add(long long A, long long B){
  A %= MOD;
  B %= MOD;
  return (A + B) % MOD;
}

int mul(long long A, long long B){
  A %= MOD;
  B %= MOD;
  return (A * B) % MOD;
}