Lotteria Di Quadri 20/100 [Execution Timed Out]

Aiuto
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.

1 Mi Piace
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?

1 Mi Piace