Lotteria Di Quadri 20/100 [Execution Timed Out]


#1

Ciao,
Ho provato a risolvere l’esercizio “Lotteria Di Quadri” ma mi da l’errore Execution Timed Out nei Testcase 7, 9, dal 20 al 26 e dal 28 al 33.
Ecco il mio codice: https://pastebin.com/2aG6AA0P
L’algoritmo che ho scritto fondamentalmente calcola le somme delle subsequenze partendo da B=1 fino a B=N se tutte le somme calcolate sono minori di M ritorna N, sennò il ciclo si interrompe quando S>M e ritorna il valore sella i che sarebbe la B precedente.
Per esempio se N=4, M=8 V={1,2,3,4} procede in questo modo:

[B=1]
1>8 ?
2>8 ?
3>8 ?
4>8 ?

[B=2]
(1+2)=3>8 ?
(2+3)=5>8 ?
(3+4)=7>8 ?

[B=3]
(1+2+3)=6>8 ?
(2+3+4)=9>8 ? Vero quindi B=2

Vorrei sapere se il mio approccio va bene ma con qualche errore di strazione oppure la mia soluzone è sbagliata, come potrei ottimizzare il programma?


#2

Devi trovare un algoritmi migliore, prima l’osservazione, se sai già quanto vale la somma dei K valori che partono da i, come puoi calcolare la somma dei K valori che partono da i+1?


#3

che intendi con K valori che partono da i?


#4

Partendo da qui, con B=3 la somma dei primi 3 valori fa 6, quando calcoli la somma dei valori dal secondo al quarto tu la calcoli da 0, quando potresti sfruttare la somma dei primi 3.


#5

Grazie, ma ho fatto come dici tu e il punteggio ora è 45/100.
Il codice: https://pastebin.com/5VNqTFHH
Ora invece di calcolare tutto da 0 uso la somma precedente sottraendo il Vi minore e aggiungendo il prossimo Vi, ma non capisco che altro c’è che non va.
Va bene il nuovo algoritmo oppure è sbagliato?


#6

Prossima osservazione, tu sai che se per un certo B, tutti i subarray di lunghezza B hanno somma minore di X allora sai che se prendi A<B nessun subarray di lunghezza A avrà somma maggiore o uguale a X.

Quindi puoi fare un altro tipo di ricerca che non sia quella lineare?


#7

Con la ricerca binaria dopo aver ordinato i numeri, giusto?


#8

Perché devi ordinare i numeri?


#9

non serviva un array ordinato per poter effettuare la ricerca binaria?


#10

Per cercare un elemento in un array ordinato sì, in generale basta la seconda osservazione che ho fatto, quindi se vale: Se p(x)=T allora p(y)=T, y<x in questo caso se puoi prendere x quadri alla volta senza sforare la somma potrai prenderne sicuramente y,y<x senza sforare la somma.


#11

Scusa, non riesco a capire in che modo posso implementare questo nel codice.
che intendi con A<B e y<x?


#12

Immagina che f(x) ti restituisca la somma del subarray di lunghezza x con somma massima.
Allora tu puoi iniziare controllando f(\frac{N}{2}) e se ti restituisce un valore minore di M allora sai che per ogni i< \frac{N}{2} , f(i)<M e quindi puoi non controllarli e con la stessa logica controllare f(\frac{3N}{4}). Se invece il risultato fosse stato maggiore di M allo puoi evitare di controllare gli i> \frac{N}{2} e passare a \frac{N}{4}. Procedi cosi salvandoti l’i massimo che ti restituisce un valore minore o uguale a M.


#13

Quindi nella funzione f(x) per ritornare la somma massima del subarray x, devo calcolare tutte le somme di dimensione x per avere il numero maggiore come ho già fatto nella soluzione precedente?