Lavishe's blog

Could you please suggest some ideas to help me approach this problem?
By Lavishe, history, 12 months ago, In English

Hello everyone, Could you please suggest some ideas to help me approach this problem? Thank you!

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

Comments Comments (8)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

did u try segment tree?

→ Reply
»
12 months ago, hide # |
← Rev. 3  
Vote: I like it +24 Vote: I do not like it

You could implement with a segment tree. You start by negating all the elements in odd positions in the original array, and then constructing a segment tree.

For every node, you need to store the total sum, the maximum prefix sum, the maximum suffix sum, and the maximum contiguous subarray sum. When you combine two nodes, (total, prefix, suffix, mcss) becomes (total_l + total_r, max(prefix_l, sum_l + prefix_r), max(suffix_r, sum_r + suffix_l), max(mcss_l, mcss_r, suffix_l + prefix_r)).

When you swap, if the target indices are in opposite parities you need to negate them and then swap, or else you can just swap them.

The top node will contain the answer after every query.

→ Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I think it's a bit trickier than that because the alternating negation happens from the start of the left of the subarray so the positions getting negated aren't always the odd ones

    For instance, if A=[1,2,3,4,5] and you choose S=[1,2,3,4] then you get 1-2+3-4 but if you choose S=[2,3,4] then you get 2-3+4

    The easiest implementation I can think of right now is to have a segment tree where the keys are pairs of adjacent items so you can follow a strategy like the one described above while enforcing that the contiguous subarray starts from either an even or an odd position (edit: not necessary since all Ai are positive, see below)

    Also the problem description uses the wrong definition of subarray because it doesn't require the remaining elements to be contiguous (edit: removed incorrect solution for this case, it would be a dp problem)

    → Reply
    • »
      »
      »
      12 months ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +8 Vote: I do not like it

      Oh, I didn't notice that it meant the subarray is alternating. I think it's a very easy fix though, correct me if I'm wrong.

      You can simply store two MCSS segtrees, one where alternating elements are negated with the first element being positive, and one where the first element is negative.

      So like a' = [a1, -a2, a3, ..., an] a'' = [-a1, a2, -a3, ..., -an]

      Now you can just run the same algorithm I stated above, but update both segtrees and return the maximum of either one.

      → Reply
      • »
        »
        »
        »
        12 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        The query doesn't tell you which tree to use

        However I just realized since all Ai are positive in the problem, you can just query both trees and take the max result, because the MCSS will always start on a positive element in each tree

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, hide # ^ |
          ← Rev. 3  
          Vote: I like it 0 Vote: I do not like it

          Yeah you will have to query both trees, the structure ensures that it's impossible for the mcss to have a negative element on either end.

          If ai could be negative, this would not work. You could also get around that though, by storing a MIN_MCSS segtree with our MAX_MCSS segtree.

          edit: On second thought, neither methods will work with negative elements. It can be shown that they are essentially the same thing.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Not necessarily, if A=[-5, 5, -5, 5] then the a'' tree will claim the answer is 20 when that would require starting the alternating sum on a negated element which isn't allowed

            → Reply
»
12 months ago, hide # |
← Rev. 4  
Vote: I like it +1 Vote: I do not like it

literally 1420C2 - Pokémon Army (hard version).

One can use $$$(max,+)$$$ matrix multiplication and segment trees to solve this problem.

→ Reply