Codeforces Round 1097 (Div. 2)

A. Zhily and Array Operating

Since each element can only be selected at most once, thus we can start by accumulating the suffix unless the suffix sum is negative, and add the suffix to current element.

Time complexity $O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>

using i64 = long long;

void run() {
  int n;
  std::cin >> n;
  std::vector<i64> a(n);
  for (auto &x : a)
    std::cin >> x;

  int ans = 0;
  i64 accum = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (a[i] + accum >= 0)
      a[i] += accum, accum = a[i];
    else
      accum = 0;
    if (a[i] > 0)
      ans++;
  }

  std::cout << ans << "\n";
}

int main() {
  int t;
  std::cin >> t;
  while (t--)
    run();
}

B

We first count the global max and mex. We can divide into several cases.

• If max == 0, then all elements are $0$, the answer is $n$.
• If max == 1, then if there exists $0$, the answer is $3n-2$, otherwise, it’s $n$.
• Then if mex > max, this means 1,2, ..., max are in the array, we first put max at first, then 1,2,..max-1 after it. This is the optimal
• If mex < max, this arrangement is also optimal.

C

We can adopt a greedy solution. If $a_i=b_i$, then swapping makes no sense; otherwise, let’s assume $a_i=\texttt{)}$, if $b_{1,\dots,i-1}$ has more $\texttt{(}$ than $a_{1,\dots,i-1}$, then we swap $a_i,b_i$.

After processing all positions, we check if $a,b$ are valid.

D

A common expansion of expectation is to exploit its linearity to convert counting problem into independent judgement problem. For this problem, expected number of inversion pairs is equivalent to

$$\sum_{i\lt j}\mathbb{E}[a_ib_i' \gt a_jb_j']$$

Since $a_i,a_j$ are fixed and $b_i',b_j'$ are arbitrary, we can use a $O(n^2\log n)$ approach to count how many pairs of $b_i',b_j'$ satisfies this. We collect all $\frac{b_i'}{b_j'}$, sort them, and for each pair of $(a_i,a_j)$, we binary search in the sorted array to count.