Solutia problemei Battle of the Blackwater

Pentru orice numar x exista valori distincte la impartirea x / i. Astfel vor exista intervale pentru i unde fiecare interval are asociat valoarea x / i. De exemplu pentru x = 16 exista intervalele (1-1), (2-2), (3-3), (4-4), (5-5), (6-8), (9-16) unde valorile asociate vor fi pe rand 16, 8, 5, 4, 3, 2, 1. Putem folosi aceasta observatie pentru a optimiza calculul aportului fiecarui numar pe fiecare pozitie in care ar rezulta in urma permutarii circulare. Deci daca vectorul nostru are forma [x,x,x,16,x,x,x,x,x,x,x] si stim ca are intervalele de mai sus pentru permutarea circulara la stanga de 3 ori are asociat intervalul 1-1 cu valoarea 16, pentru permutarea de 2 ori are valoarea 8, pentru permutarea circulara o data are valoarea 5, pentru nicio permuare are valoarea 4, pentru permutarea circulara la dreapta o data (echivalenta cu permutare la stanga de 10 ori) valoarea este 3, iar de acum inainte vor urma intervale mai lungi cu acelasi rezultat, pentru permutarile la dreapta de 2, 3 sau 4 ori 16 va contribui cu 2 iar pentru permutarile la dreapta de 5, 6 sau 7 va contribui cu 1. Asadar se poate aplica smenul lui mars pentru a adauga pe un interval o valoare si se poate rezolva problema in .