Ciao,
stavo provando a risolvere il problema Torre di Controllo (https://cms.di.unipi.it/#/task/aeroporto/statement), ma non riesco proprio a trovare una soluzione possibile… L’unica che mi viene in mente è una dinamica, ma con 100000 atterraggi e un tempo massimo di 1000000000 (minuti?) una quadratica non sembra assolutamente andare bene.
Qualcuno che mi da’ una mano?
Provo con questo suggerimento 
Supponi di conoscere già un tempo T: sei in grado di determinare, in complessità lineare nel numero di atterraggi, se è possibile effettuare tutti gli atterraggi aspettando almeno T minuti?
In questo caso, cosa potresti fare per determinare qual è il valore accettabile di T più grande?
Comincio a seguirti… Il tempo massimo lo trovo facendo il massimo di tutti gli istanti finali degli intervalli. Poi da li potrei provare una ricerca binaria di qualche tipo. Domani provo a implementare qualcosa, grazie!
p.s.: tranquillo, chiederò ancora 
2 Mi Piace
Riprendendo il discorso di prima, una volta ottenuto T massimo, ancora non riesco ad andare molto più avanti. Avevo pensato ad una ricerca binaria di qualche tipo, magari inizialmente da 0 a T, ogni volta che divido il problema dico che in ogni metà ci deve essere lo stesso numero di atterraggi (e se sono dispari?) e posso andare avanti così. Il problema è che non riesco a dimostrare che una cosa del genere funzioni.
Un’altra idea era quella di dividere non a metà ma con lo stesso numero di intervalli da una parte e dall’altra… bocciata, per ogni divisione avrei una complessità lineare. Come complessità della soluzione verrebbe O(nlogn)
Non ci sto capendo molto 
Dario
1 Mi Piace
Mmmmh no, forse non ci eravamo intesi bene
La domanda del mio primo messaggio era questa: riesci a sapere se puoi completare tutti gli atterraggi distanziandoli almeno di un valore K ? Se sì, con quale complessità?
Non mi ero accorto che la lettera T fosse già usata all’interno del problema, errore mio 
Comunque cerca di ragionare su questa parte, poi potrai pensare a come cercare il valore più alto che puoi assegnare a K
1 Mi Piace
Prima di tutto grazie per l’aiuto!
Nonostante non abbia implementato la ricerca del K massino in tempo lineare come dicevi, ma con una sorta di ricerca binaria (parto da 1, raddoppio ogni volta finchè non è troppo grande, altra ricerca tra Kmax e Kmax / 2 per trovare K finale) sono riuscito ad ottenere 100/100.
Grazie ancora, sei un grande
2 Mi Piace
No no la ricerca di K andava fatta proprio tramite una ricerca binaria, lineare è il tempo necessario per testare se un determinato intervallo K può essere rispettato, comunque sono contento che tu abbia risolto
Approfitto di questa discussione sul tema “Torre di controllo” per condividere il mio problema: il sorgente allegato viene compilato correttamente, nel momento in cui lo sottopongo alla piattaforma (commentando ovviamente il main e lasciando solo la funzione) mi da “Compilazione fallita”. Grazie a chi potrà rispondermi.aeroporto.zip (890 Byte)
Ho mandato il tuo codice rimuovendo il main con le annesse variabili e non ho nessun problema di compilazione. Dovresti trovare una soluzione più veloce, se hai bisogno di suggerimenti basta leggere i post precedenti.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void pianifica(int R, int A[], int B[], int T[]) {
int i,c,kmin,imin;
bool trovato,fine=false;
int *K = (int*)malloc(R * sizeof(int));
T[0]=A[0];
//inizializza array T e K
for(i=1; i<R; i++) {
T[i]=B[i];
K[i-1]=T[i]-T[i-1];
}
//c=2; //primo e ultimo vincolati
while(!fine) {
//cerca minimo ki tal che abbia alla sua sinistra un ki-1 maggiore
fine=true;
for(i=1,kmin=1000000000,trovato=false; i<R-1; i++) {
if(K[i]<kmin && K[i-1]>K[i] && T[i]>=A[i]) {
kmin=K[i];
imin=i;
trovato=true;
fine=false;
}
}
//se trovato...
if(trovato) {
if(T[i]>=A[i]) {
K[imin]++;
K[imin-1]--;
T[imin]--;
}
}
}
}