An array of size s + 1
is initialized such that a[i] = i
for 0 <= i < s
, a[s] = 0
. Then I iteratively use dynamic programming to sum the values of the array, going from largest to smallest, doing it t
times. Results get large very quickly so I reduce them mod some modulus
.
If s = 10
, the arrays look like this:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
[0, 45, 44, 42, 39, 35, 30, 24, 17, 9, 0]
[0, 45, 89, 131, 170, 205, 235, 259, 276, 285, 0]
And so on.
After t
iterations I am interested in the extreme non-zero values of the array. My algorithm does this explicitly, resulting in time complexity of O(s*t)
. Is there any algorithm that can produce either (or both) of these values in a better time complexity? Specifically I was thinking about whether matrix exponentiation is possible, reducing time complexity to O(s*log(t))
, but really any approach is welcome as well as optimizations.
My code:
public class ArraySummation{
public static void main(String []args)
{
int s = 10;
long t = 10;
long modulus = 1000000;
long [] a = new long [s + 1];
for (int i = 1 ; i < s ; i++)
a[i] = i;
for (int i = 2 ; i <= t ; i++)
{
if ((i & 1) == 1)
for (int j = 1 ; j < a.length - 1 ; j++)
{
a[j] += a[j - 1];
if (a[j] >= modulus)
a[j] -= modulus;
}
else
for (int j = a.length - 2 ; j >= 1 ; j--)
{
a[j] += a[j + 1];
if (a[j] >= modulus)
a[j] -= modulus;
}
}
System.out.println(a[1]);
System.out.println(a[s - 1]);
}
}
For s=10 it can be found in OEIS https://oeis.org/A030113 as a linear recurrence.
There is also a formula in matrix form for all s
(PARI) k=9; M(k)=matrix(k, k, i, j, if(1-sign(i+j-k), 0, 1)); v(k)=vector(k, i, 1); a(n)=vecmax(v(k)*M(k)^n)
Sample for the matrix construction
Explanation The Matrix M operates by multiplication to Matrix T as follows to the result matrix R (short: M . T = R)
Thus the adding procedure of the question is done by matrix multiplication, but with initialization a[i] = 1
. After first round with M^2 the last column contains the initialization of the question a[i] = i
Depending on the parameters s, t it could be better to use the matrix exponentiation like M^8 = M^4 . M^4 = M_4 . M_4 , M^4 = M^2 . M^2 = M_2 . M_2, where M_2 and M_4 can be reused. So instead of 8 matrix mulitiplications with only 3 multiplication we can get the result.
The complexity is O(s^2 * log(t))