Problema Torre di controllo


#1

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?


#2

Provo con questo suggerimento :slight_smile:
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?


#3

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 :grin:


#4

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 :confounded:

Dario


#5

Mmmmh no, forse non ci eravamo intesi bene :slight_smile:
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 :innocent:

Comunque cerca di ragionare su questa parte, poi potrai pensare a come cercare il valore più alto che puoi assegnare a K


#6

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


#7

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 :slight_smile:


#8

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)


#9

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]--;					
			} 				
		}	
	}
}