← Complete problem index

PROJECT EULER · #0663

Sums of Subarrays

Statement only · SolvedOriginal problem ↗

Let tk be the tribonacci numbers defined as:
t0=t1=0;
t2=1;
tk=tk−1+tk−2+tk−3 for k≥3.

For a given integer n, let An be an array of length n (indexed from 0 to n−1), that is initially filled with zeros.
The array is changed iteratively by replacing An[(t2i−2modn)] with An[(t2i−2modn)]+2(t2i−1modn)−n+1 in each step i.
After each step i, define Mn(i) to be max{∑j=pqAn[j]:0≤p≤q<n}, the maximal sum of any contiguous subarray of An.

The first 6 steps for n=5 are illustrated below:
Initial state: A5={0,0,0,0,0}
Step 1: ⇒A5={−4,0,0,0,0}, M5(1)=0
Step 2: ⇒A5={−4,−2,0,0,0}, M5(2)=0
Step 3: ⇒A5={−4,−2,4,0,0}, M5(3)=4
Step 4: ⇒A5={−4,−2,6,0,0}, M5(4)=6
Step 5: ⇒A5={−4,−2,6,0,4}, M5(5)=10
Step 6: ⇒A5={−4,2,6,0,4}, M5(6)=12

Let S(n,l)=∑i=1lMn(i). Thus S(5,6)=32.
You are given S(5,100)=2416, S(14,100)=3881 and S(107,1000)=1618572.

Find S(10000003,10200000)−S(10000003,10000000).

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.