Incontri inaspettati 2

Aiuto
1

buon giorno, qualcuno saprebbe dirmi come migliorare questo codice per superare la subtask N<=1000?

#include <iostream>
using namespace std;
int Max(int a, int b);bool visita(int N, int A[]) {
	int s1=0,s2=0,max;
	int i=0,j=N-1;
	while(i<j){
		s1+=A[i];
		s2+=A[j];
		max=Max(s1,s2);
		if(max==s1){
			while(s2<s1){
				j--;
				s2+=A[j];
			}
		}
		else if(max==s2){
			while(s1<s2){
				i++;
				s1+=A[i];
			}
		}
		else if(max==0&i+1!=j-1){
			i++;
			j--;
		}
		/*cout<<"sono i "<<i<<"\n";
		cout<<"sono j "<<j<<"\n";
		cout<<"sono s1 "<<s1<<"\n";
		cout<<"sono s2 "<<s2<<"\n";*/
		if(s1==s2&i+1==j-1)return true;
	}
  return false;
}
int Max(int a, int b){
	if(a>b)return a;
	else if(b>a)return b;
	else return 0;
}

Grazie in anticipo :smiley:_smile:

2

Salve, prova a spiegare la tua idea cosi è più facile capire cosa potrebbe essere sbagliato.
Intanto prova questi due casi di test per migliorare la tua soluzione:

1
17

5
20 14 1 4 20

Immagino che sia voluto restituire 0 se i due valori sono uguali.

3

salve in pratica la mia soluzione era quella di stabilire 2 somme, una per emil e l’altra per gemma e di controllare chi fosse in ritardo dei 2 in modo che ogni volta faccio andare avanti solo la persona che è in ritardo di quella differenza tra il suo tempo e quello dell’altra persona.
se i tempi coincidono faccio andare avanti entrambi ed ecco spiegato il return zero.
alla fine di ogni ciclo controllo se il loro tempi coincidono e se rimane solo una bellezza da visitare per cui se si beccano.
qrazie ai casi di test ho migliorato qualcosa ma non riesco a passare ancora la subtask 3

4

ecco cosa ho migliorato:

bool visita(int N, int A[]) {
	int s1=0,s2=0,max;
	int i=0,j=N-1;
	**if(i==j)return true;**
	while(i<j){
		s1+=A[i];
		s2+=A[j];
		max=Max(s1,s2);
		//cout<<max;
		if(max==s1){
			while(s2<s1){
				j--;
				s2+=A[j];
			}
		}
		else if(max==s2){
			while(s1<s2){
				i++;
				s1+=A[i];
			}
		}
		else if(max==0&i+1!=j-1){
			i++;
			**s1+=A[i];**
			j--;
			**s2+=A[j];**
			
		}
		/*cout<<"sono i "<<i<<"\n";
		cout<<"sono j "<<j<<"\n";
		cout<<"sono s1 "<<s1<<"\n";
		cout<<"sono s2 "<<s2<<"\n";*/
		if(s1==s2&i+1==j-1)return true;
	}
  return false;
}
5

Non mi sembra sia sbagliato ma puoi scriverlo meglio in termini di codice. Cerca di usare un solo ciclo per far muovere i ragazzi.

6

va bene ma in generale non mi è chiaro cosa intendono loro con N<=1000 ad esempio.
per superare la subtask il programma deve funzionare con N maggiore di 1000?

7

l’errore non è di timeout ma di output non corretto. tutti i miei test case vanno a buon fine per cui non ho ancora capito bene come provare

8

I subtask sono un insieme di casi di test dove vigono determinate caratteristiche che vengono indicate. Questo permette di ottenere punteggi parziali qual’ora non si riesca a risolvere l’istanza generale del problema. Di solito limitano la grandezza dei valori in input per far ottenere punti a soluzioni lente.
Nel caso di N \leq 1000 ti garantiscono che per quel gruppo di casi N non sarĂ  mai maggiore di 1000 permettendo cosi a chi trova una soluzione O(N^2) di ottenere il punteggio di quel subtask.
Un esempio di soluzione O(N^2) per questo problema è: fissata un attrazione quanto tempo impiegano i due ragazzi ad arrivarci?

1 Mi Piace
9

L’idea è giusta, devi solo scriverla meglio!

1 Mi Piace
10

Prova questi casi di input:

10
3 9 3 4 11 12 4 12 7 6 

5
5 9 2 6 8

Per quanto riguarda l’idea esistono sicuramente modi più semplici per scriverla per esempio: per ogni attrazione ti calcoli dopo quanto tempo la raggiunge Gemma in O(N), quanto tempo impiega Emil per raggiungerla in O(N) e poi verifichi se esiste almeno un’attrazione che Gemma ed Emil iniziano a visitare contemporaneamente sempre in O(N).

11

io ho usato un approccio diverso ma comunque se non erro in complessitĂ  di O(N)
Edit: sono riuscito ad ottimizarla ed è la 3a soluzione più veloce

12

Su un esercizio in cui il codice è così semplice non c’è molto che puoi fare per abbassare il tempo d’esecuzione. Un’idea potrebbe essere quella di allocare meno memoria( si può fare in O(N) tempo ed O(1) memoria).

13

io lo ho risolto con Prefix sum

14

Alla fine è questo:

Con prefix sum però ti serve O(N) memoria, io ho provato anche a simulare in O(1) memoria ma ottengo un tempo maggiore del tuo.

	int i=0, j=N-1, a=0, b=0;
	while(i<j){
		if(a==b && i==j)
			return true;
		if(a==0 || a<b)
			a+=A[i++];
		else b+=A[j--];
	}
15

io impiego O(N-1) per l’inizializzazione mentre per trovare la soluzione impiego O(N-2)
credo che a te che quelle 2 condizioni aumentino il tuo tempo, perché sono per ogni ciclo deve fare 4 comparazioni

16

Asintoticamente O(N) ed O(N+C) con C costante sono la stessa cosa.

17

si, però avendo meno condizioni risulta più veloc

18

@bortoz Ora vorrei sapere come hai fatto a fare 0.02 ahahah

19

Risparmiare 4 operazioni su 100000 non fa nessuna minima differenza, soprattutto se si tratta di comparazioni che richiedono un numero quasi nullo di cicli di cpu. Se ti è sembrato più veloce è solo una casualità, difatti il server non è sempre preciso e sottomettendo la stessa soluzione più volte si possono ottenere tempi lievemente diversi.

20

su questo concordo anche se sinceramente sono curioso della tua soluzione, nel caso ne potremmo parlare in privato?