tiagonapoli's blog

By tiagonapoli, history, 4 years ago, In English

How to calculate the complexity of this simple loop?

// v is an array with n elements, n <= 10^5
for(int i=0;i<n;i++) {
  int sum = 0;
  for (int j = i + 1;j < n && sum < v[i]; j++) {
    sum += v[j];
    // O(1) block
  }
}

It seems the worst case scenario would be something like:

$$$ 2^k, 2^{k-1}, 2^{k-2}, ..., 2^0, 2^0 $$$

In which case the number of operations would be $$$O(nlog(maxElement))$$$, but I'm not being able to prove the complexity.

Background: a similar algorithm is used in the following problem and I wasn't able to understand the solution's complexity analysis

Full text and comments »

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

By tiagonapoli, history, 8 years ago, In English

Hi everyone, i'm a begginer on Games Theory and I was trying to solve Vasya and Chess — 281div2D but I couldn't understand the strategy behind the optimal way to play it, and , therefore, it's solution. Could anyone, please, help me with an explanation?

Full text and comments »

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