Treats for the Cows | Editorial by rsampaths16

Consider function **solve** witch returns the solution for range **i** to **j** starting at time **t**.
Also assume the function magically returns the optimal answer for now.
Then we know it can be written as
```
@magical
solve(i , j, t) {
    return (t)*(a[p[i]]) + (t+1)*(a[p[i+1]]) + (t+2)*(a[p[i+2]]) + ... +  (t + j)*(a[p[j]]);
}
```
* where **a[i..j]** are sub-array considered
* **i** start of sub-array, **j** end of sub-array
* **p[i..j]** some valid permutation of number from **i** to **j** which provides optimal result

Now consider the same function to return solution starting with time **t+1**
```
@magical
solve(i, j, t+1) {
    return (t+1)*(a[p[i]]) + (t+2)*(a[p[i+1]]) + (t+3)*(a[p[i+2]]) + ... + (t+j+1)*(a[p[j]);
}
```
Which can be rewritten as 
```
@magical
solve(i, j, t+1) {
    return a[p[i]] + a[p[i+1]] + a[p[i+2]] + ... a[p[j]] 
    + (t)*(a[p[i]]) + (t+1)*(a[p[i+1]]) + (t+2)*(a[p[i+2]]) + ... + (t+j)*(a[p[j]]);
}
```
* We know **p[i] .. p[j]** is a permutation of **i .. j**
  * *Therefore* **a[p[i]] + ... + a[p[j]] = a[i] + ... + a[j] = &#120680;a[i,j]**
  * **&#120680;a[i,j] is constant w.r.t time t**
* For **solve(i, j, t+1)** to be optimal, **(t)\*a[p[i]] + (t+1)\*a[p[i+1]] + (t+2)\*a[p[i+2]] + ... + (t+j)\*a[p[j]]** should be optimal.
  * This is because **&#120680;a[i,j] is constant w.r.t time t, thus the above sequence must be optimal w.r.t time t**
  * Therefore the above sequence is the solution for **solve(i, j, t)**

Taking above points into consideration the function can be rewritten as
```
@magical
solve(i, j, t+1) {
    return SIGMA(i, j) + solve(i, j, t):
}
```
No assume that the magic has been removed to get solutions automatically, but still present in sub-levels
Then we find the solution as
```
solve(i, j, t) {
    return max(a[i] + solve(i+1, j, t+1), a[j] + solve(i, j-1, t+1) + a[j]);
}

@magical
solve(i, j, t) {
    return SIGMA(i, j) + solve(i, j, t-1);
}
```
Removing SIGMA from magical solution to main solution we get
```
solve(i, j, t) {
    return max(a[i] + SIGMA(i+1, j) + solve(i, j-1, t+1) + SIGMA(i, j-1) + a[j]);
}

@magical
solve(i, j, t) {
    return solve(i, j, t-1);
}
```
Resolving this we get 
```
solve(i, j, t) {
    return SIGMA(i, j) + max(solve(i+1, j, t+1), solve(i, j-1, t+1));
}

@magical
solve(i, j, t) {
    return solve(i, j, 1);
}
```
* We can make an observation that **solve(i, j, t) = solve(i, j, t-1) = ... = solve(i, j, 1)**
  * **t** cannot be less than **1** as age cannot be less than **1**
  * Thus we can remove t from the equation altogether

```
solve(i, j) {
    return SIGMA(i, j) + max(solve(i+1, j), solve(i, j-1));
}

@magical
solve(i, j) {
    return solution(i, j, 1);
}
```

Now we remove magic completely and we get
```
solve(i, j) {
    if (i == j) {
        return a[i];
    }
    return SIGMA(i, j) + max(solve(i+1, j), solve(i, j-1));
}
```
We can see that time taken to solve the problem of size T is
```
solve(T) = 2 * solve(T-1)
hence
solve(T) = 2^T * solve(1)
```
To make this faster memorize solve(i, j) when solved
```
solve(i, j) {
    if (memorized(i, j)) {
        return memorized(i, j);
    }
    if (i == j) {
        memorize(i, j, a[i]);
        return a[i];
    }
    var ans = SIGMA(i, j) + max(solve(i+1, j), solve(i, j-1));
    memorize(i, j, ans);
    return ans;
}
```

Treats for the Cows | Editorial by rsampaths16

Download submission

All caught up!

View submission

Is your resume even shortlisted?