Lily White's blog

Analysis

The key observation is this sentence:

For every pair of two blue square $a$ and $b$, there is at most one path that starts from $a$, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches $b$, without traversing the same square more than once.

This could be rewritten as

For each two node, only one simple path connects them

which is a definition of a forest.

With forests, we have the simple conclusion that, $N_{\mathrm{Conn}}=|V|-|E|$. This is intuitive in that, if the forest is reduced to a tree, then rhs is $1$, which is yet another definition of a tree.

Based on this observation, we can use 2D prefix sum to maintain the rectangular sum of nodes, vertical edges and horizontal edges. Note that edges cannot lead to nodes out of the boundary.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

const int N = 2020;
int sumv[N][N], sumh[N][N], sumn[N][N];
char s[N][N];
int n, m, q;
void Main() {
    rd(n, m, q);
    repn(i, n) repn(j, m) {
        cin >> s[i][j];
        sumv[i][j] = sumv[i - 1][j] + sumv[i][j - 1] - sumv[i - 1][j - 1] + (s[i][j] == '1' && s[i][j - 1] == '1');
        sumh[i][j] = sumh[i - 1][j] + sumh[i][j - 1] - sumh[i - 1][j - 1] + (s[i][j] == '1' && s[i - 1][j] == '1');
        sumn[i][j] = sumn[i - 1][j] + sumn[i][j - 1] - sumn[i - 1][j - 1] + (s[i][j] == '1');
    }
    while (q--) {
        int x1, y1, x2, y2;
        rd(x1, y1, x2, y2);
        cout << (sumn[x2][y2] - sumn[x1 - 1][y2] - sumn[x2][y1 - 1] + sumn[x1 - 1][y1 - 1]) -
                (sumh[x2][y2] - sumh[x1][y2] - sumh[x2][y1 - 1] + sumh[x1][y1 - 1]) -
                (sumv[x2][y2] - sumv[x1 - 1][y2] - sumv[x2][y1] + sumv[x1 - 1][y1]) << endl;
    }
}

Comment

Take note of the unconventional statements in the problem. In this problem, the given connected components are special in that they form several trees, and this is the key observation that ultimately leads to the solution of this problem.

热身赛

热身赛的题目是 THUPC 的往年赛题，我们前一个小时认真做了 AB 两题，后一个小时进行了系统测试，包括

• CE 算不算罚时？（不算）
• WA1 算不算罚时？（算）
• 提交时需要选择语言，且不选择将默认为 C

正赛

9：00 进场后开题。按照往届 VP 的经验，一般在 3 分钟左右就会有人过题，但这次比赛直到 10 分钟左右才出现过题。由于平常我们队伍几乎永远处于有榜可跟的状态，我们并没有练出判断题目可做性的能力。这使得比赛开始浪费了不少时间。

9：20 左右基本可以看出 AL 两题是签到题。因此开始做 A，ttb 提出了一个分块做法，我粗略估算是 $O(n\sqrt{n})$ 量级，但他证明了上限只是略微超过 20000，并且“很松”，因此能过。于是喂给我做法。我上机写 A。A 的这个分块做法写起来很复杂，有不少边界条件需要判断，因此写的很急。9：40 发现 F 也是可做题，xzk 迅速推出了基环树上的计数方法，于是他上机开写，稍微调试一段时间后便通过。

之后我继续上机写 A，xzk 和 ttb 讨论 L 的做法，他们很快推出了正解 DP 式子。我的 A 通过了样例，但极限数据测试需要的操作数超过了题目要求。于是我让机给 L。L 很快通过了样例，但是提交后超时，后来发现极限数据在 O2 后要跑到 4s。

这时已经快到了 2h，我仍然没有想到如何压缩 A 的操作次数，这时 ttb 想到了 A 的正确构造——二分，这是 $O(n \log n)$ 级的，明显可以通过。但此时我奋战了两小时的做法被完全无效化，对我的心态产生了不小的影响。我也犯了向队友输出情绪的大错。

xzk（代码核心！）上机写出了 A，调试的时候崩掉了我的 checker，一开始以为 checker 写的有问题，于是又吃了一发罚时，后来发现 checker 在非法输出的时候会崩溃，改掉后过了 A

此时时间为 2 小时 40 分钟，我带着 A 的错误做法想 G 并几乎立刻想到了哈希+分块的正解，喂给 xzk 后吃了两发罚时，最后改了一个似乎不会影响正确性的小点后通过。

时间来到 3 小时。我们全队开始卡 L 的常无果，同时 ttb 去做 I 题，xzk 提了一嘴数据分治之后去写了 $k \ge 4$ 的情况，同时 ttb 开始数学推导，最终推出了 $k=3$ 的正解 Observation。需要一些 STL，因此我上机写了 $k=3$ 的情况，一段调试后过样例并吃 WA。此时到了 4h。

最后一个小时我们一起试图调出 L 和 I，由于 L 通过人数很多，我们对自己的做法产生了很大的怀疑，几度决定换做法但也想不出有效的做法。而 I 则不断发现小错误，在代码上打了很多补丁最后也没有通过。最终因为高罚时而遗憾铁牌离场。

总结和自我批判

SS

本场比赛我犯了很多错误，其中最重要的一点便是情绪管理。我在自己负责的分块程序不正确之后便有些情绪失控，这样的失控几乎贯穿了全场比赛。同时，我个人的代码能力偏向于模拟/STL等，思维能力较弱，这就导致在写很多题目的时候都难以独自输出，必须依赖队友。这是以后个人训练时必须加强的。

TTB

虽然正赛连键盘都没碰，但是我还是觉得这场发挥没太大问题，在误差允许范围内。A的分块假做法确实大锅，不过好在最后还是喂了真做法，xzk五分钟直接拿下。I题其实也应该有能力把$k=3$的二分做法推广到$k\ge 4$从而改善最后的程序的，可惜当时一直执着于WA了什么数据，没想过这种优化方法。
之后感觉保持这样状态也行，不过既然不怎么写代码就更要多做题，熟悉一下建模套路，免得I这种其实很简单的题却开太晚而且最后都没过。

XZK

自我批判：平时我写代码都不太注重罚时，这次到后面也有些心急甚至直接开莽，这导致了代码中出现了很多小漏洞，吃了很多罚时，在以后的模拟和比赛中要多加注意。一些代码常见错误要在写时就避免（多测清空，注意空间大小，注意数组下标）。平时看见一些常用技巧要多注意。板子的多样性。

Problem of the day: CF1856E1

Analysis

It is easy to observe that we need to split the sizes of the subtrees evenly. The problem is transformed to the following basic pattern:

Given an array $a$, find a way to partition $a$ into two parts, such that the difference between the sum of these two parts is minimized.

This can be solved via knapsack DP. Note that we don’t need to calculate the sizes of subtrees before running the DP, we can do this while traversing the tree. The resulting time complexity is $O(n^2)$.

Solution

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
32
33
34
35
36
37

void dfs(int u, int f) {
    sz[u] = 1;
    bool hasChild = false;
    for (auto v : g[u]) {
        if (v == f) continue;
        hasChild = true;
        dfs(v, u);
        sz[u] += sz[v];
        ans[u] += ans[v];
    }
    if (hasChild) {
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        for (auto v : g[u]) {
            if (v == f) continue;
            for (int i = sz[u]; i >= sz[v]; i--) chmax(dp[i], dp[i - sz[v]]);
        }
        int dans = 0;
        for (int i = sz[u] / 2; i >= 1; i--) {
            if (dp[i]) {
                chmax(dans, i * (sz[u] - i - 1));
            }
        }
        ans[u] += dans;
    }
}
void Main() {
    rd(n);
    repn(i, n - 1) {
        int f;
        rd(f);
        g[f].push_back(i + 1);
        g[i + 1].push_back(f);
    }
    dfs(1, 0);
    cout << ans[1] << endl;
}

Problem of the day: CF1862F, *1800

Analysis

As casting spells take no time, we can first fill up with mana and then deal with the monsters.

A naive thought would be to simply binary search for the answer, and then check whether the total mana acquired is enough to defeat all monsters. However, note that a monster could be killed with only one kind of magic (you can’t use 5 points of water followed by 2 points of fire), this won’t work.

However, we can be greedy. Let’s say we try to use water magic as much as possible, then we resort to using fire magic. In this way, we can ensure that no monster shall lie on the borders. However, we can’t just naively use the given ordering, as this might not be optimal (i.e. we might leave a huge pile of water mana). Instead, we use knapsacks. Compute the maximum number of monsters defeatable using water magic, and leave the rest to fire magic.

Solution

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

int a[N], dp[1001000];
void Main() {
    ll W, F;
    int n;
    rd(W, F);
    rd(n);
    ll S = 0;
    repn(i, n) {
        rd(a[i]);
        S += a[i];
    }
    rep(i, S + 1) dp[i] = 0;
    repn(i, n) {
        repd(j, S, 1) {
            if (j >= a[i]) {
                dp[j] = max(dp[j], dp[j - a[i]] + a[i]);
            }
        }
    }
    ll L = 0, R = 1e6, ans = -1;
    while (L <= R) {
        ll t = midpoint(L, R);
        if (F * t >= S - dp[min(S, W * t)]) {
            ans = t;
            R = t - 1;
        } else {
            L = t + 1;
        }
    }
    cout << ans << endl;
}

Problem of the day: CF1864D, *1700

Analysis

The idea is pretty simple and cliche. Similar to the classical problem of flipping light bulbs on and off, with a light triggering every light bulbs surrounding it, all the operations we perform here can only affect numbers “below” the current number. Thus, we can fully determine what to do for the first row, and then the second row, until we get all the way to the bottom.

However, the real essence of this problem lies in: How do you actually keep account on this? You can’t just do updates by brute-force, that’ll be $O(n^4)$, we have to think of a better way.

Note that we don’t actually need to traverse every cell. We only need the cell to know how should it be updated, and we can know about this by just asking the cells above it.

Thus, we keep track of three tags, l, m, and r. Note that it’ll be ugly if we don’t keep tabs on m. When we try to do an update, we push the tags down, just like in a segment tree. l gets pushed to the bottom-left, m the bottom, and r the bottom-right.

We can solve this problem in $O(n^2)$.

Solution

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
32

void Main() {
    rd(n);
    repn(i, n) scanf("%s", a[i] + 1);
    repn(i, n) repn(j, n) a[i][j] -= '0';
    repn(i, n) repn(j, n) l[i][j] = m[i][j] = r[i][j] = 0;
    int ans = 0;
    repn(i, n) {
        repn(j, n) {
            if (m[i][j]) {
                a[i][j] ^= 1;
                l[i + 1][j - 1] ^= 1;
                m[i + 1][j] ^= 1;
                r[i + 1][j + 1] ^= 1;
            }
            if (l[i][j]) {
                a[i][j] ^= 1;
                l[i + 1][j - 1] ^= 1;
            }
            if (r[i][j]) {
                a[i][j] ^= 1;
                r[i + 1][j + 1] ^= 1;
            }
            if (a[i][j]) {
                ans++;
                l[i + 1][j - 1] ^= 1;
                m[i + 1][j] ^= 1;
                r[i + 1][j + 1] ^= 1;
            }
        }
    }
    cout << ans << endl;
}