DEAMN's blog

Help!
By DEAMN, history, 4 years ago, In English

Hello Codeforces! I need help. I can't solve this problem for 24 points (this problem), if anyone has an idea, you can write a comment. Thank you in advance

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

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

here is the editorial by Benq

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

    thx, but I need 24 point

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

      Solution for 4th subtask:

      Let us fix j and now need to find i and k. Now we have to consider 2 cases.

      first case: If element at position j is 2 we need to find rightmost index of 1 in range [1, j], and let it be i, then leftmost index of 1 in range [j+1, n], let it be k (you can find them with segment tree). We will need to add to answer $$$(k-j-1)*(j-i)$$$. Why do we add it? [i+1, j] and [j+1, k-1] are maximum ranges we with the same elements, we do simple combinatorics by multyplying them

      second case: If element at position j is 1 we do the same as in the first case but instead of finding indexes of 1 we look for indexes of 2.

      And also, we add to answer $$$i*(n-k+1)$$$, it is a case when we need both 1 and 2 in these ranges.

      So, we just iterate over j and find rightmost and leftmost indexes in $$$O(logN)$$$, the overal complexity will be $$$O(NlogN)$$$

      PS when you don't find rightmost or leftmost indexes you will assume that indexes are 0 and n+1.

      Hope you understand and sorry for my poor English.

      → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

For every position $$$u$$$ we can calculate $$$\mathrm{nxt}[u]$$$ — the next position after $$$u$$$ where the array equals $$$a_u$$$. If it doesn't exist, set $$$\mathrm{nxt}[u] = \infty$$$.

Fix $$$i$$$ and start sliding $$$j$$$. For each $$$j$$$ you can calculate the range of $$$k$$$ such that $$$(i, j, k)$$$ is beautiful. The left endpoint of the range is the maximum of $$$\mathrm{nxt}[u]$$$, where the maximum is taken over the rightmost appearances of every element in the range $$$i \ldots j$$$. And the right endpoint is the leftmost $$$r$$$ such that $$$a_r$$$ doesn't appear among $$$a_i \ldots a_j$$$. If you have this data for $$$i, j$$$ then you can calculate it for $$$i, j + 1$$$ in amortized $$$\mathcal{O}(1)$$$ time. Thus you end up with an $$$\mathcal{O}(n^2)$$$ algorithm.

→ Reply