Balkan OI 2018 - Election

Authors: Andi Qu, Benjamin Qi

Method 1 (Offline)

Consider the greedy strategy: iterate from left to right and change Ts to satisfy the increasing condition, then do the same from right to left.

We can solve this problem offline by simulating this process.

https://oj.uz/submission/61836

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Method 2 (Online)

A simpler case

Consider the case where we only care about counting votes from left to right.

Let a C vote count as 1-1 and a T vote count as +1+1 in an array VV.

The answer to a query on the range [l,r][l, r] is simply the maximum prefix sum in that range. (i.e. The largest Vl+Vl+1++VkV_l + V_{l + 1} + \dots + V_k)

If we count votes from right to left though, the answer is the maximum suffix sum instead.

We can use a segment tree to answer both of these types of queries efficiently.

Combining values

It would be really convenient if we could just calculate the maximum prefix and suffix sums and add them. However, we would count some nullified votes twice if we do this.

In each node of the segment tree that stores information about the range [l,r][l, r] we store the following information:

  • The maximum prefix sum in the range [l,r][l, r]. (Let this be LL)
  • The maximum suffix sum in the range [l,r][l, r]. (Let this be RR)
  • The total sum of the range. (Let this be SS)
  • The answer to a query on the range [l,r][l, r]. (Let this be AA)

When we combine two nodes uu (left child) and vv (right child) to make node ww,

  • w.L=max(u.L,u.S+v.L)w.L = \max(u.L, u.S + v.L)
  • w.R=max(u.R+v.S,v.R)w.R = \max(u.R + v.S, v.R)
  • w.S=u.S+v.Sw.S = u.S + v.S

Finding w.Aw.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)w.A=\max(\max(u.A + v.S, u.S + v.A), u.L + v.R)

For a range of length LL, this calculates maxi(max(first i prefix sums)+max(last Li suffix sums))\max_i\left(\max(\text{first }i\text{ prefix sums})+\max(\text{last }L-i\text{ suffix sums})\right)

Claim 1: This is a lower bound on the answer.

We can say that the increasing condition must hold for the first ii votes and the decreasing condition must hold for the rest of the votes in the range.

Claim 2: This lower bound can be attained.

Consider the greedy strategy mentioned in method 1. Then equality holds when we set ii equal to one less than the position of the leftmost T removed when doing the right to left iteration.

Therefore, this is a lower bound and it can be attained.

The final complexity of this algorithm is O((N+Q)logN)\mathcal{O}((N + Q) \log N).

Implementation

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
struct Node {
int l_max, r_max, tot, ans;
Node operator+(Node b) {
Node ret;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!