Ligh0x74's Blog

2023-10-02发表2023-10-02更新算法 / Codeforces5 分钟读完 (大约718个字)

Jellyfish and Undertale

每个工具对答案的贡献为 \(\min(a-1,x_{i})\)，并且答案可能会爆 \(long\)，状态好差，WA 两次。

public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), n = io.nextInt();
    long ans = b;
    for (int i = 0; i < n; i++) {
        ans += Math.min(a - 1, io.nextInt());
    }
    io.println(ans);
}

Jellyfish and Game

数学题。当 \(k\bmod 2=1\) 时，先手会得到 \(\min(0,maxb-mina)\)；反之，后手此时必然有最小价值的苹果 \(\min(mina,minb)\)，而先手此时会有最大价值的苹果 \(\max(maxa,maxb)\)，做一次交换即可。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();

    long suma = 0L;
    int mina = Integer.MAX_VALUE, maxa = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int x = io.nextInt();
        suma += x;
        mina = Math.min(mina, x);
        maxa = Math.max(maxa, x);
    }

    int minb = Integer.MAX_VALUE, maxb = Integer.MIN_VALUE;
    for (int i = 0; i < m; i++) {
        int x = io.nextInt();
        minb = Math.min(minb, x);
        maxb = Math.max(maxb, x);
    }

    if (k % 2 == 1) {
        io.println(suma + Math.max(0, maxb - mina));
    } else {
        io.println(suma + Math.max(0, maxb - mina) - Math.max(maxa, maxb) + Math.min(mina, minb));
    }
}

Jellyfish and Green Apple

完了，官方解法看不懂，下面是我的解法，就是一直乘二求余，贪心的拆分。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    int x = n % m, y = m / gcd(n, m);
    if ((y & (y - 1)) != 0) {
        io.println(-1);
        return;
    }

    long ans = 0L;
    while (x != 0) {
        ans += x;
        x *= 2;
        x %= m;
    }
    io.println(ans);
}

private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

下面是官解，大概懂了。\(\frac{a}{b}\) 表示最终每个人得到的苹果价值的小数部分（可以表示为 \(\sum_{i\in S}\frac{1}{2^{i}}\)），因为 \(b\) 必须是二的幂，所以 \(a\) 中 \(1\) 的个数就表示这个人所需的最小苹果片数（就是集合 \(S\) 中元素的个数），乘以 \(m\) 就表示最后总共的苹果片数，然后减去最开始的 \(n\) 片就是需要进行操作的次数（因为每次操作会增加 \(1\) 片）。（这个题解很详细，提供了另一种视角）

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();

    n %= m;
    int x = gcd(n, m), a = n / x, b = m / x;
    if ((b & (b - 1)) != 0) {
        io.println(-1);
    } else {
        io.println((long) Integer.bitCount(a) * m - n);
    }
}

private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Jellyfish and Mex

其实是很简单的动态规划，但就是动不起来啊。定义 \(dp[i]\) 为将 \(MEX\) 变为 \(i\) 需要的最小代价，然后从大到小转移即可。

private static final int N = 5001;

public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[N];
    for (int i = 0; i < n; i++) {
        int x = io.nextInt();
        if (x < n) cnt[x]++;
    }

    int mex = 0;
    while (cnt[mex] > 0) mex++;
    long[] dp = new long[mex + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[mex] = 0;
    for (int i = mex - 1; i >= 0; i--) {
        for (int j = i + 1; j <= mex; j++) {
            dp[i] = Math.min(dp[i], dp[j] + (long) (cnt[i] - 1) * j + i);
        }
    }
    io.println(dp[0]);
}

2023-10-02发表2023-10-02更新算法 / AtCoder4 分钟读完 (大约663个字)

AtCoder Beginner Contest 322

First ABC 2

public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    int ans = s.indexOf("ABC");
    io.println(ans < 0 ? -1 : ans + 1);
}

Prefix and Suffix

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    String s = io.next(), t = io.next();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            ans |= 2;
        }
        if (s.charAt(i) != t.charAt(m - n + i)) {
            ans |= 1;
        }
    }
    io.println(ans);
}

Festival

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < m; i++) {
        int x = io.nextInt() - 1;
        ans[x] = 0;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ans[i] == -1) {
            ans[i] = ans[i + 1] + 1;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}

Polyomino

模拟题，使用位运算似乎更简单，题解。

public static void solve() {
    char[][][] G = new char[3][4][4];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            G[i][j] = io.next().toCharArray();
        }
    }
    io.println(dfs(0, G, new char[4][4]) ? "Yes" : "No");
}

private static boolean dfs(int i, char[][][] G, char[][] C) {
    if (C == null) return false;
    if (i == 3) return check(C);
    for (int j = 0; j < 4; j++) {
        for (int dx = -3; dx <= 3; dx++) {
            for (int dy = -3; dy <= 3; dy++) {
                char[][] T = move(dx, dy, G[i]);
                if (T == null) continue;
                if (dfs(i + 1, G, add(T, C))) return true;
            }
        }
        G[i] = rotate(G[i]);
    }
    return false;
}

private static char[][] rotate(char[][] A) {
    char[][] B = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            B[i][j] = A[3 - j][i];
        }
    }
    return B;
}

private static char[][] move(int dx, int dy, char[][] G) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        Arrays.fill(res[i], '.');
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int nx = i + dx, ny = j + dy;
            if(G[i][j] == '#') {
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
                    return null;
                }
                res[nx][ny] = G[i][j];
            }
        }
    }
    return res;
}

private static char[][] add(char[][] T, char[][] C) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] == '#' && T[i][j] == '#') return null;
            if (C[i][j] == '#' || T[i][j] == '#') res[i][j] = '#';
            else res[i][j] = '.';
        }
    }
    return res;
}

private static boolean check(char[][] C) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] != '#') return false;
        }
    }
    return true;
}

Product Development

动态规划，\(dp[i][j]\) 表示从前 \(i\) 个计划中选择开发计划，使得参数到达 \(j\)，需要的最小成本，其中 \(j\) 表示 \(a_{1},a_{2},\dots,a_{k}\) 的某个取值，通过将序列看作 \(p+1\) 进制数，可以将一个序列转换为某个数值（在这里就是 \(j\)）。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), p = io.nextInt();

    int[] pw = new int[k + 1];
    pw[0] = 1;
    for (int i = 1; i <= k; i++) {
        pw[i] = pw[i - 1] * (p + 1);
    }

    long[] dp = new long[pw[k]];
    Arrays.fill(dp, -1L);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        int[] a = new int[k];
        for (int j = 0; j < k; j++) {
            a[j] = io.nextInt();
        }

        for (int s = pw[k] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < k; j++) {
                int cur = s / pw[j] % (p + 1);
                int nxt = Math.min(p, cur + a[j]);
                t += nxt * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + c)) {
                dp[t] = dp[s] + c;
            }
        }
    }
    io.println(dp[pw[k] - 1]);
}

2023-09-29发表2023-09-29更新课程 / CMU 15-44522 分钟读完 (大约3298个字)

Project #2 - B+Tree

项目准备

项目地址：Project #2 - B+Tree

准备工作：阅读 Chapter 14.5 24.5 14.1-14.4 18.10.2，学习 Lecture #07 #08 #09，以及阅读课堂笔记。

Task #1 - B+Tree Pages

实现

① 第一个比较迷惑的点就是 max_size_ 的含义，对官方提供的B+Tree进行插入操作，发现叶子节点的 size_ 不会到达 max_size_。难道叶子节点实际只能包含 max_size_ - 1 个 key 吗？通过查看项目地址中的 Requirements and Hints 可以发现，官方建议叶子节点在插入后大小达到 max_size_ 时，进行分裂，内部节点在插入前大小达到 max_size_ 时进行分裂。所以对于内部节点，max_size_ 表示它能包含的指针数量；对于叶子节点，max_size_ 表示它能包含的键值对数量。

② GetMinSize 的实现，同样参考官方示例，对于非叶子节点，返回 (max_size_ + 1) / 2；对于叶子节点，返回 max_size_ / 2。为什么要这样，参考第 ① 点也就明白了，这样可以保证分裂后的两个节点的大小都至少为最小大小，所以该方法的实现实际上取决于分裂的具体实现（即何时分裂）。

补充

① 如何理解 MappingType array_[0]，注释表示它是 Flexible array member for page data，参见维基百科Flexible array member。似乎是 C 语言的特性，C++ 标准不支持，但是 C++ 的编译器普遍会支持。

② 在内部节点和叶子节点中，array_ 的唯一区别就是在搜索内部节点时不能使用 array[0]_.first，因为它并不能准确表示 array_[0].second 中 key 的范围（向 array_[0].second 中插入一个更小的 key，它就失效了）。

Task #2a - B+Tree Insertion and Search for Single Values

实现

① 比较纠结的是既然要使用二分查找，如何保证节点内部 key 的有序性，因为是使用数组存储的，所以似乎只能花费 \(O(n)\) 时间来移动元素了？或者可以加一个数据结构存下标，来保证有序性，但是涉及分裂和删除操作还是比较难搞的，暂时不优化。

② 可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Search 函数，来实现二分查找指定 key。内部节点一定可以找到一个满足条件的位置（因为我们找的实际上是指针），而叶子节点如果找不到指定 key，那么就返回 -index - 1（方便之后插入，类似 Java 中的 BinarySearch）。具体的实现逻辑：

内部节点从位置 1 开始找第一个大于 key 的键，返回它左边位置，即 index - 1。
叶子节点从位置 0 开始找第一个大于等于 key 的键，如果越界或者键值不等于 key，则返回 -index - 1，否则返回 index。

③ 特别注意 PageGuard 的使用，只有当操作完页面之后，才对其进行 Drop 操作（移动赋值以及匿名对象的析构都会导致该操作）。并且用完页面后及时 Drop，这样可以尽早释放页面的锁以及 Unpin 页面。插入时，利用 latch crabbing 技巧，先拿到下个页面的锁，然后根据页面大小判断是否 Drop 上个页面（使用 Context）。注意拿锁和 Drop 的顺序，以及该大小判断依赖于分裂的实现，详细见 Task #1 - B+Tree Pages ①。

④ 获取页面需要进行类型转换，如果只读不写就使用 page_guard.h 中提供的 As 函数，只有需要写页面时才使用 AsMut 函数，因为该函数会将页面置为脏页。先将其转换为 BPlusTreePage，然后再根据页面类型，将其转换为内部节点或叶子节点，注意 BPlusTree 类中已经为我们提供了别名：

1 2	using InternalPage = BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator>; using LeafPage = BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>;

一开始我没有注意，在对内部节点转换时，误将其 page_id_t 转为 ValueType，导致完全误解了整个项目的结构。

⑤ 分裂叶子节点和内部节点时，注意判断当前节点是否是根节点。我们可以在 BPlusTreeInternalPage 和 BPlusTreeLeafPage 中添加 Split 函数，来实现分裂。

叶子节点的分裂操作比较简单，就是移动然后设置大小，为了不让页面类和其他类耦合（BufferPoolManager，Context），我将分裂函数的参数设计为 BPlusTreeInternalPage &new_page，它会返回将插入到上层的 key，即新节点的第一个 key。

内部节点的分裂操作比较复杂，并发测试时遇到边界样例才发现，因为内部节点的分裂是插入前分裂，所以还需要考虑插入的那个键的大小。如果 key 比 array_[GetMinSize() - 1] 小，则插入到当前节点，否则插入到新分裂的节点。并且，在插入新分裂的节点时，可能会插入到索引为 0 的位置，这一点要特别注意。最后，也是返回新节点的第一个 key（指的是 array_[0].first，因为分裂的时候复制了）。

⑥ 同理，在内部页面和叶子页面类中可以添加 Insert 函数。需要注意的是，这两个函数的实现有些点不同。对于内部节点，当 B+Tree 的根节点分裂时，该情况会将 page_id 插入到内部节点的第一个没有键的位置，所以我们可以将参数设计为 const std::optional<KeyType> &opt 来区分这种情况。对于叶子节点，由于不能有相同的键，所以根据 Search 的实现，当 index ≥ 0 时返回 false，否则继续插入。

调试

调试时可以先使用可视化网站查看 B+ 树，方便定位问题，我们可以使用 shell 脚本一键生成文件（解决方案）：

1
2
3

#!/bin/bash
make b_plus_tree_printer -j$(nproc)
{ echo 2 3; echo i 1; echo i 2; echo g my-tree.txt; echo q; } | ./bin/b_plus_tree_printer

在生成文件时可能会报 [b_plus_tree.cpp:356:Draw] WARN - Drawing an empty tree 错误，原因是我们没有实现 b_plus_tree.cpp 中的 IsEmpty 函数。

补充

① 如何使用 upper_bound 和 lower_bound（Java 选手表示踩了很多坑），可以看看 cppreference 的示例代码，尤其注意 lambda 表达式的使用（参数顺序，以及大小的比较）。

② 测试时忽略 iterators 的测试。

③ GetValue 注意特判根节点是否存在，否则可能引发空指针异常（依赖于 BufferPoolManager 的实现）。

Task #2b - B+Tree Deletions

实现

① 删除操作可以分为两种情况，相邻节点重新分配和相邻节点合并。进一步可以划分为操作当前节点的左节点，还是右节点。需要注意的是，我们只有对相同父节点的两个子节点执行上述操作，一个非根节点必定有一个同父的左节点或右节点。（如果不这样限制，实现起来会很麻烦，需要找到最近公共祖先，做键值的替换。）为了能够获取左右节点的页面，我们在从上到下找 key 对应的页面时，可以同时保存左右页面的 page_id。

② 重新分配操作，需要区分左右。如果从右节点取，则需要更新右节点对应父节点中的 key；如果从左节点取，则需要更新当前节点对应父节点中的 key。操作完可以直接返回。

③ 合并操作同理，只不过不是更新，而是删除对应父节点中的 key（递归删除）。注意，如果合并叶子节点，需要同时更新 next_page_id_。（合并之后右侧的页面永远都不会被使用，或许需要对其执行 DeletePage 操作，在 DeletePage 之前需要 Drop/Unpin 页面。有个疑问，DeletePage 之前 Drop 之后，如果有线程 Fetch，那么删除页面的操作就会失败。）

调试

实现的思路弄明白后，大方向上就不会出错，但是很多细节容易写错：变量名字，重复执行 pop_back() 操作，删除页面后对页面进行操作等等。不过，说实话官方提供的可视化类真好用，Debug 全靠可视化来定位问题。磨磨蹭蹭，花费一天时间，做得有点慢。

Task #3 - An Iterator for Leaf Scans

基本上没有难度，遇到唯一的错误就是把 GetSize 打成了 GetMaxSize（因为用的自动补全）。

Task #4 - Concurrent Index

① 遇到问题，先定位它是什么问题。首先，应该解决非并发问题，我们可以在插入和删除的开头加一把大锁，然后利用并发测试 MixTest2，来混合查找、插入和删除操作，看看是否存在问题。为了尽可能引发问题，可以将叶子节点和内部节点的最大大小修改为 2 3，将 total_keys 修改为 1000，尽可能的触发分裂和合并操作（这个测试，比线上测试还强，多跑几次线上能过的给报错了）。在混合时，可以分别混合查找和插入，查找和删除，插入和删除，这样方便定位问题出在哪里。然后，再去进行并发优化，一点一点优化，边优化边测试，这样就不会因为找不到 Bug 的位置而发愁啦。

② 遇到错误，[disk_manager_memory.h:104:ReadPage] WARN - page not exist，发现是 BufferPoolManager 的 Bug，需要跑回去修复。一天后，终于真正的把 Bug 修好了，代码也稍微重构了一下，哈哈，真的 99% 不会报错（有个 FetchPageBasic/Read/Write 返回 nullptr 的错误没修复，报错概率很低，以后有问题再修），不得不说本地测试用例修改后是真的强劲，线上强度不够啊。（~~但是重构了个寂寞，效率没变，难受啊~~）

③ B+Tree 的并发问题其实基本没有，都是单线程问题或者 BPM 的并发问题，B+Tree 的并发只要注意 Fetch 和 Drop 的顺序就 OK。

(Optional) Leaderboard Task

① 初次提交通过，排名还挺高。额，多次提交能差七八万。感觉测试有问题，平均 QPS 也就十万多。

② 优化暂时搁置。

Rank	Submission Name	read_qps	write_qps	total_qps
36	ALEX	200376	603	200980

测试结果

Checkpoint #1 说简单也不简单，感觉有些细节总是写错，包括下标的处理，C++ 二分查找函数的使用，变量名称，以及一些边界条件。说难也不难，线上测试首次提交就通过了。总共花了一天半吧。

Checkpoint #2 总共花了两天，任务三四没什么难度，主要时间还是在删除操作，以及修复插入操作中的 Bug。

#!/bin/bash
make b_plus_tree_insert_test b_plus_tree_sequential_scale_test b_plus_tree_delete_test b_plus_tree_concurrent_test -j$(nproc)
./test/b_plus_tree_insert_test
./test/b_plus_tree_sequential_scale_test
./test/b_plus_tree_delete_test
./test/b_plus_tree_concurrent_test
make format
make check-lint
make check-clang-tidy-p2
make submit-p2

项目小结

开始做项目之前，对插入和删除具体怎么操作还是比较迷糊的，实际实现起来发现原来是这样的。特别需要注意别打错变量名，我用自动补全总是搞混 MaxSize 和 MinSize，还有各种变量都敲错，运行起来找 Bug 就头疼了。还要注意，内部节点和叶子节点分裂的时机不同，实现也不同，以及在分裂时如何对待内部节点的第一个 key。然后删除操作就是个分类讨论，弄明白就不难了。并发错误我也真是见识到了，BPM 优化需谨慎啊。（~~做得还是很慢，对大佬来说，其实就是个复杂点的模拟题吧~~）