Balkan OI 2018 - Election Editorial help

[Evang]

Problem link
I have read the editorial here, but I am confused about the section Combining Values in Method 2 (link).

The editorial states that w.A = max(max(u.A + v.S, u.S + v.A), u.L + v.R).
Then, the editorial says:

Claim 1: This is a lower bound on the answer.
We can say that the increasing condition must hold for the first i votes and the decreasing condition must hold for the rest of the votes in the range.

1. What increasing conditon?

2. Why does this mean that w.A = max(max(u.A + v.S, u.S + v.A), u.L + v.R) is a lower bound on the answer?

[Benq]

1. increasing condition = “Cap is happy if at every point in time during the vote counting he is NOT losing to Tony” when going in increasing order of the fan’s indices

2. If you split the sequence into two parts, then the answer for the sequence is at least the number of modifications necessary to make the first part satisfy the increasing condition and the second part satisfy the decreasing condition

[Evang]

I have a follow-up question:

Here is another quote from the editorial:

Claim 2: This lower bound can be attained.
Consider the greedy strategy mentioned in method 1. Then equality holds when we set i equal to one less than the position of the leftmost T removed when doing the right to left iteration.

I don’t see how. Can someone justify the justification for Claim 2? (Illustrations might be a good idea if you wanna do that)

[Benq]

• The number of votes that the greedy strategy nullifies to the left of or equal to i is equal to \max(\text{first }i\text{ prefix sums}).
  • Explanation: These votes must have been nullified while the greedy strategy was iterating from left to right.
• The number of votes that the greedy strategy nullifies to the right of i is equal to the (L-i)-th suffix sum.
  • Explanation: After nullification, the number of non-nullified Ts to the right of i must be equal to the number of Cs to the right of i.

[Evang]

@Benq

Explanation: After nullification, the number of non-nullified Ts to the right of i must be equal to the number of Cs to the right of i.

1. Why?
2. Can the number of Cs to the right of i be greater than the number of non-nullified Ts to the right of i? If not, why?
3. How to be red coder?
4. is it rated?

[Benq]

When moving from left to right, the greedy strategy only nullifies the j-th T in order to make the number of Cs in the prefix of length j equal to the number of Ts in the prefix of length j. Similar reasoning holds from right to left.

[Evang]

@Benq

The number of votes that the greedy strategy nullifies to the right of i is equal to the (L−i)-th suffix sum.

Wait, but the editorial says:

Finding w.A is a bit more tricky though. We will show that it is equal to
w.A=max⁡(max⁡(u.A+v.S,u.S+v.A),u.L+v.R)
For a range of length L, this calculates \max_i\left(\max(\text{first }i\text{ prefix sums})+\max(\text{last }L-i\text{ suffix sums})\right)

The editorial says \max(\text{last }L-i\text{ suffix sums}) instead of \text{the }(L-i)^{\text{th}}\text{ suffix sum}. What am I missing here?

[Benq]

It turns out that \max(\text{last }L-i\text{ suffix sums}) = (L-i)-th suffix sum for the i in question.

(Also, if the code instead computed \max_i\left(\max(\text{first }i\text{ prefix sums})+(L-i\text{-th suffix sum})\right) it would end up with the same answer.)

[Evang]

does that also imply that \max_i(\max(\text{first }i\text{ prefix sums}) + \max(\text{last } L-i\text{ suffix sums}))=\max_i([i^{\text{th}}\text{ prefix sum}]+[(L-i)^{\text{th}}\text{suffix sum}])?

(I’m assuming that the suffix array is indexed backwards. For example, the 1st suffix sum is the sum of 1 element, and the Lth suffix sum is the sum of all the L elements)

[Benq]

No it doesn’t.

[Evang]

@Benq

• The number of votes that the greedy strategy nullifies to the left of or equal to iii is equal to max⁡(first i prefix sums)\max(\text{first }i\text{ prefix sums})max(first i prefix sums).
  • Explanation: These votes must have been nullified while the greedy strategy was iterating from left to right.
• The number of votes that the greedy strategy nullifies to the right of iii is equal to the (L−i)(L-i)(L−i)-th suffix sum.
  • Explanation: After nullification, the number of non-nullified Ts to the right of iii must be equal to the number of Cs to the right of iii.

Let p be the position of the leftmost T removed when doing the right to left iteration (instead of using i).
I now understand that
\max_{1\leq j <p}(\text{pre}[j])+\text{suf}[p]=\max_{1\leq j <p}(\text{pre}[j])+\max_{p\leq j\leq n}(\text{suf}[j])
where \text{pre}[i]=V_1+V_2+...+V_i and \text{suf}[i]=V_i+V_{i+1}+V_{i+2}+...+V_n.

But, I still cannot prove why \max_{1\leq j <p}(\text{pre}[j])+\max_{p\leq j\leq n}(\text{suf}[j])=\max_{1<i\leq n}(\max_{1\leq j<i}(\text{pre}[j])+\max_{i\leq j\leq n}(\text{suf}[j])).

How to prove that?

[Benq]

Claim 1:

\max_{1<i\le n}(\max_{1\le j<i}(pre[j])+\max_{i\le j\le n}(suf[j]))\le \text{answer}

By greedy strategy:

\text{answer}\le \max_{1\le j<p}(pre[j])+\max_{p\le j\le n}(suf[j])

Obvious:

\max_{1\le j<p}(pre[j])+\max_{p\le j\le n}(suf[j])\le \max_{1<i\le n}(\max_{1\le j<i}(pre[j])+\max_{i\le j\le n}(suf[j]))

and a\le b\le c\le a\implies a=b=c

[Evang]

The only part that I’m confused about is answer≤max_{1≤j<p}(pre[j])+max _{p≤j≤n}(suf[j])

Could you explain why this is true in further detail?

[Benq]

The answer is at most the number of votes that the greedy strategy nullifies, right? And the number of votes that the greedy strategy nullifies is precisely the RHS of that inequality.

[Evang]

Ohhh right the answer is exactly the number of votes that the greedy strategy nullifies. Thanks, I’ve spent too much time on this one problem.