misaka18931's blog

AtCoder Beginner Contest 215

F - Dist Max 2

Approach: binary search

Binary Search is always an option! Unless you have to do things the hardest way.

G - Colorful Candies 2

Split the expectation into contribution over each color, then we have:

\[ \begin{aligned} E(X_k) = \sum_{c}1 - \binom{n- cnt_c}{k} \left. \middle / \binom{n}{k} \right. \end{aligned} \]

Notice that there are at most \(O(\sqrt{n})\) different \(cnt_c\). So the problem is solved in \(O(n\sqrt n)\) time.

H - Cabbage Master

Hall's marriage theorem

let \(O\) be the set of all "1 cabbage order"\((ord, V)\) where \(V\) is the set of all acceptable brands.

By Hall’s marriage theorem, all the orders in set \(O\) can be satisfied if and only if

for all \(T \subseteq O\) , \(\sum_{s\in \cup V}a_s \ge |T|\) holds.

change the summation order and iterate over set of brands, we have

\[ f(S) \ge g(S) \]

for all \(S \subseteq V\) .

Where \(f(S)\) is number of cabbages, \(g(S)\) is number of orders.

\(\min {(f(S) - g(S))}\) is the number of cabbages eaten.

Find all valid \(S\), and calculate the number of ways when the snake only eats cabbages of brands in \(S\).

This can be done using an OR convolution and an inverse AND convolution.

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

void solve() {
  binom_init();
  int n = rd(), m = rd();
  FOR(i, 0, n) a[i] = rd();
  FOR(i, 0, m) b[i] = rd();
  FOR(i, 0, n) FOR(j, 0, m) c[i][j] = rd();
  FOR(i, 0, 1 << n) FOR(j, 0, n) f[i] += ((i & (1 << j)) != 0) * a[j];
  FOR(i, 0, m) {
    int t = 0;
    ROF(j, 0, n) t = (t << 1) | c[j][i];
    g[t] += b[i];
  }
  fwt(g, 1 << n);
  int X = 1e9;
  FOR(i, 0, 1 << n) {
    if (g[i]) chkmin(X, f[i] - g[i]);
  }
  if (X < 0) {
    puts("0 1");
    return;
  }
  FOR(i, 0, 1 << n) {
    if (g[i] && f[i] - g[i] == X) flag[i] = 1;
  }
  fmt(flag, 1 << n);
  FOR(i, 0, 1 << n) h[i] = binom(f[i], X + 1);
  ifwt(h, 1 << n);
  mint ans(0);
  FOR(i, 0, 1 << n) if (flag[i]) ans += h[i];
  cout << X + 1 << ' ' << ans << '\n';
}

DP practices

Probability/Expectations DP

「PKUWC2018」随机算法

Key Inspection: After deleting a arbitrary node and all its adjacent nodes from the greatest independent set, the rest is still the greatest independent set of the remaining parts.

Approach: bitmask-dp, graph-theory

misaka-cp/p2540.cpp

DP over digits

[AHOI2009]同类分布 - 洛谷 code

contribution split

Problem - 1238E - Codeforces code

data structure

W - Intervals code

counting

Y - Grid 2 code

Codeforces Round #738 (Div. 2)

statistics: problem solved: 4/6 realtime, 1 after contest.

C - Mocha and Hiking

This problem is a partial proof that

There always exists an Hamiltonian path in a tournament graph.

D2. Mocha and Diana (Hard Version)

Problem - D2 - Codeforces

Approach: greedy graph matching technique.

First, try add all possible edge \((1, u)\)

Then all nodes which are not in the same component as node 1 must be in the same component with node 1 in the second graph.

Now we will consider nodes of two types, the ones that are in the same component than 1 in the first tree, and the ones that are in the same component than 1 in the second tree. We will store all nodes of type 1 in a stack p1, and all nodes of type 2 in a stack p2, and we will try to match them with the following algorithm.

• If the top of p1 is in the same component than 1 in both trees, delete it

• If the top of p2 is in the same component than 1 in both trees, delete it

• Otherwise, add an edge between the top of p1 and the top of p2.

E. Mocha and Stars

Problem - E - Codeforces

Approach: Mobius Inversion (the good old gcd inversion)

\[ \begin{aligned} Ans=& \sum_{l_i \le a_i \le r_i}[\sum a_i \le m][gcd(a_i) = 1]\\ =& \sum_d \mu(d)\sum_{l_i \le a_i \le r_i}[\sum a_i \le m][a_i|d]\\ =& \sum_d \mu(d) \sum_{\lceil\frac{l_i}{d} \rceil \le a_i \le \lfloor \frac{r_i}{d}\rfloor}[\sum a_i \le \lfloor\frac{m}{d}\rfloor]\\ \end{aligned} \]

the rest part is just some \([z^k]\frac{1}{(1 - z)^{n + 1}}\prod(1-z^{k_i})\), which can be solved \(O(nk)\) through DP

Total time complexity:\(O(nm\ln m)\)

An archive of my problem-solving/contests logs and notes, hosted preliminary for future references.