asim2005's blog

What is the Time Complexity of this problem?
By asim2005, 4 years ago, In English

https://mirror.codeforces.com/problemset/problem/1180/A

Isn't the time complexity of the problem I mentioned above is o(1) ? In the tutorial they are saying o(n) ?

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

Comments Comments (2)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Well, you can also implement the solution in $$$O(1)$$$ like in this submission. The trick here that the rhombus is made out of $$$1+3+5+7+...+7+5+3+1$$$ so, you can sum all $$$N-1$$$ elements they will be $$$1+3+5+7+...+2(N-1)-1$$$. Which is basically the sum of all odd numbers starting from 1 till the $$$(N-1)th$$$ term. The summation is known to be $$$N^2$$$. Lets proof it with induction:

$$$f(1)=1$$$

$$$f(x)=f(x-1)+2x-1$$$

$$$f(x)=f(x-1)+2x-1=x^2$$$

$$$f(x-1)=f(x-2)+2(x-1)-1=(x-1)^2$$$

$$$f(x-1)=f(x-2)+2x-3=(x-1)^2$$$

$$$f(x)=f(x-2)+2x-3+2x-1=x^2$$$

$$$f(x)=f(x-2)+4x-4=N^2$$$

Subtracting $$$f(x)$$$ with $$$f(x-1)$$$:

$$$f(x-2)+4x-4-f(x-2)-2x+3=x^2-(x-1)^2$$$

$$$2x-1=x^2-(x-1)^2$$$

$$$2x-1=x^2-x^2+2x-1$$$

$$$2x-1=2x-1$$$

Therefore, it is correct for all integers $$$>=1$$$.

And because the last $$$N-1$$$ equal to first $$$N-1$$$ terms, we will multiply it by 2. What is left is to add the row which have the most cells. In 1, it was 1. In 2, it was 3. So, it keeps increasing by 2. So we will add $$$2N-1$$$ as it keeps increasing by 2 and -1 is the calibration constant. Therefore, $$$2((N-1)^2)+(N*2-1)$$$ is the final answer.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Other simpler way is we can notice that for each next-n, we can split the adding area it to 4 regions of the same area

    n = 1
    n = 2
    n = 3

    So by the fact above, the number of areas are $$$1 + 1 \times 4 + 2 \times 4 + 3 \times 4 + \cdots + n \times 4 = 1 + 4 * (1 + 2 + \cdot + n) = 1 + 4 \times \frac{n (n - 1)}{2}$$$

    → Reply