Skeef79's blog

By Skeef79, history, 3 months ago, translation, In English

Recently I've come up with this problem:

You are given an array $$$a_1, a_2, \dots, a_n$$$ of positive integers.

You need to find $$$l$$$, $$$r$$$ such that $$$\frac{\prod_{i=l}^{r} a_i}{r-l+1}$$$ is maximum over all possible $$$l,r$$$ $$$(l \leq r)$$$.

Is it possible to solve this faster than $$$O(n^2)$$$? This problem looks like something well-known, but I am not sure.

Read more »

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

By Skeef79, history, 3 months ago, translation, In English

Hello codeforces!

I am wondering is there a way to caculate prefix sums $$$k$$$ times modulo $$$p$$$ fast, especially when we can't use matrix multiplication?

By calculating prefix sums $$$k$$$ times I mean this piece of code:

for(int it = 0; it < k; it++) {
    for(int i = 1; i < n; i++)
        pref[i]+= pref[i-1];
}

So if we start with array: $$$1, 0, 0, 0$$$ we will get:

  1. $$$1, 1, 1, 1$$$;

  2. $$$1, 2, 3, 4$$$;

  3. $$$1, 3, 6, 10$$$;

  4. $$$1, 4, 10, 20$$$; ...

Read more »

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it