Ho provato a risolvere questo problema usando una binary search per trovare la lunghezza del sottoarray, per poi verificare la soluzione nella funzione f(), tuttavia ottengo solo 60 punti per via di un output non corretto (testcase 13).
Questo è il codice: http://pastebin.com/dYrZyTgj
Ho provato con vari testcase inventati ma proprio non riesco a trovare il bug…
Non sono sicuro che si possa sempre applicare la ricerca binaria per trovare la lunghezza ottima.
Per avere la sicurezza di ottenere risultati sempre corretti è necessario che la funzione F sia monotòna, in particolare vuoi che:
F(l)=False \implies F(m>l)=False
Cioè se la soluzione non esiste per una lunghezza l allora non deve esistere per tutte le lunghezze maggiori.
Tuttavia si può trovare un facile contro-esempio:
- C=<1, 0, 0, 0, 2>
- M=<0, 1, 1, 1, 0>
- F(4)=False
- F(5)=True
Che rende falsa la monotònia.
Spero di non aver detto fesserie 
3 Mi Piace
Cavolo hai ragione, non ci avevo pensato 
dovrò pensare a un altro algoritmo.