Interrogazioni ordinate

Aiuto
1

Ciao a tutti,ho tentato di risolvere il problema delle interrogazioni ordinate utilizzando(almeno penso di utilizzare) la tecnica della programmazione dinamica detta “bottom up manner”.Purtroppo riesco ad ottenere solamente 50/100.Qualcuno può darmi un consiglio su come migliorare il mio algoritmo ?Perchè nella subtask 3 mi dà l’errore di “execution timed out”?
Questo è il codice

#include<stdio.h>
#include<assert.h>

int soluzioni[200000];
int i,j;
int last = 0;
int lastV = 0;
void swap(int *a,int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int posizione = 0;
int start = 0;
int interr(int N,int num[]) 
{

  for(i=1;i<N;i++) 
  {
    for(j=0;j<i;j++)
    {
      if(num[i] < num[j])
      {
      soluzioni[i+1] = soluzioni[lastV] + 1;
      lastV = i+1;
      swap(&num[i],&num[j]);
      start = 0;
      }
      else start = 1;
    }
    if (start == 1) posizione++;
    else {
        if (posizione == 0) posizione = 0;
        else posizione--;
    }
    
  }
  return soluzioni[N];
}

int main() 
{   
   int n;
   int numeri[200000];
   FILE *fr;
   FILE *fw;
   fr = fopen("input.txt","r");
   fw = fopen("output.txt","w");
   assert(1 == fscanf(fr,"%d\n",&n));
   for(i = 0;i<n;i++) {
        assert(1 == fscanf(fr, "%d ", &numeri[i]));
   }
   fprintf(fw,"%d\n",interr(n,numeri));
   fclose(fr);
   fclose(fw);
   return 0;
   
}
2

Prima di tutto vorrei farti notare che nel tuo programma usi un array (soluzioni) di 200 000 int ma ti limiti semplicemente ad aumentare di una unità l’ultimo elemento usato, quindi potresti semplicemente usare una variabile int e aumentare quella di una unità e alla fine stamparla.
La tecnica che tu usi non è programmazione dinamica, è semplicemente una ricerca esaustiva di tutte le coppie di alunni possibili e verificare se la loro posizione sul registro è la stessa che in quella SIDI (approccio a “forza bruta”).
Non mi è chiaro l’uso della funzione swap, che non è necessaria, così come l’uso delle variabili start e posizione che non vengono minimamente usate e senza le quali il tuo programma funzionerebbe lo stesso.
In alcuni task ottieni un “execution timed out” perchè l’aproccio a forza bruta che hai usato ha un costo quadratico, ovvero per N molti alti il tempo di esecuzione aumenta esponenzialmente, superando il secondo previsto
Avevo in mente una soluzione ma poi si è dimostrata sbagliata, oggi o domani ti farò sapere.

4 Mi Piace
3

Probabilmente non è l’unica soluzione possibile, però utilizzando un Fenwick Tree (o Binary Indexed Tree) possiamo contare il numero di scambi necessari per ciascun elemento (dopo aver fatto opportuni ordinamenti) senza superare il tempo limite di 1 secondo. Ti consiglio di guardare qualcosa sull’argomento e poi magari chiedere se rimane qualcosa che ti sfugge :slight_smile:

1 Mi Piace