Counting grid squares surrounded by rectangles

Exported on 6/15/2025 at 07:26:10 GMT+8 from Cursor (1.0.0)

User

Purdue University logo Kattis Cat Search Kattis Courses / CS211-CP1 / 2025-Spring / LATE SUBMISSIONS ONLY / Problems / The Rectangles Are Surrounding Us! tannal Hide Problem D The Rectangles Are Surrounding Us! You are given a list of rectangle boundaries. Each rectangle boundary is on integer coordinates. The rectangles surround squares on the coordinate grid. Your job is to determine the total number of such grid squares that are surrounded by at least one of the given rectangles.

Input Input consists of a set of to cases. Each case starts with the number of rectangles . Following this are rectangles, each given as four integers,

, where and . The point defines the bottom left corner of the rectangle and the point defines the top right. All coordinates are between and (inclusive). Input ends when is .

Output For each set of rectangles, print the total number of grid points they surround.

Sample Input 1 Sample Output 1 1 1 1 2 2 1 10 10 19 19 2 10 10 19 19 15 15 24 24 0 1 81 146 Edit & Submit Metadata My Submissions Hide You haven’t made any submissions on this problem yet.

Contact System Status是 Terms of Service Privacy Policy

首先告诉我这道题的出处，作者，历史故事，接着用有趣和便于理解的方式叙述题目

Cursor

题目出处与作者

这道题目出自 Kattis 在线判题系统，题目名称为 “The Rectangles Are Surrounding Us!”，编号为 Problem D。
作者署名为 tannal，该题目常见于编程竞赛和算法课程练习，尤其在 Purdue University 的 CS211-CP1 课程中出现过。

历史故事（趣味化版本）

在遥远的“坐标王国”里，国王喜欢用长方形的围栏来圈地。他的园丁们每天都在不同的地方用这些长方形围栏围出一块块地。久而久之，国王突然好奇：到底有多少个小方格（1x1的地块）被这些围栏圈住了呢？有的地块可能被多个围栏圈住，但国王只关心总共有多少块地被至少一个围栏圈住。于是，他向聪明的你发出了挑战！

题目趣味叙述

想象你有一张巨大的方格纸，每个格子都是1x1的小方块。现在你拿起几根长方形的“围栏”，每根围栏都能刚好围住一片矩形区域。你可以把这些围栏放在纸上的任意整数坐标处，有的围栏可能会重叠。

你的任务是：数一数，所有被至少一个围栏圈住的小方块总共有多少个？

输入方式

每组数据先给你一个数字 ( n )，表示有多少个围栏（矩形）。
接下来 ( n ) 行，每行四个整数 ( x_1, y_1, x_2, y_2 )，表示一个矩形的左下角 ((x_1, y_1)) 和右上角 ((x_2, y_2))。
输入以 ( n = 0 ) 结束。

输出方式

对于每组数据，输出被至少一个围栏圈住的小方块总数。

样例

输入：

1
1 1 2 2
1
10 10 19 19
2
10 10 19 19
15 15 24 24
0

输出：

1
81
146

总结

这道题考察你如何高效地统计多个矩形覆盖的格子数，避免重复计数。你可以用集合、扫描线、差分数组等多种方法来解决。
准备好接受国王的挑战了吗？快来数一数这些被围栏圈住的小方块吧！

1
1 1 2 2
1
10 10 19 19
2
10 10 19 19
15 15 24 24
0

1
81
146

User

区间合并问题是不是这个问题的一维模式

Cursor

是的，你的理解非常正确！

区间合并与本题的关系

区间合并问题，通常指的是在一维上有若干个区间（如 ([a_1, b_1], [a_2, b_2], \ldots)），你需要统计这些区间合并后总共覆盖了多少长度。
做法一般是：

先把所有区间按起点排序。
依次合并有重叠的区间。
统计合并后所有区间的总长度。

本题的二维扩展

本题其实就是区间合并问题的二维版本。

一维：统计被区间覆盖的点数/长度。
二维：统计被矩形覆盖的格子数/面积。

具体联系

如果你把所有矩形的 (y) 坐标都设为同一个值（比如都在 (y=0) 到 (y=1) 之间），那么本题就退化成了一维的区间合并问题。
在二维中，常用的做法是扫描线：
- 沿着 (x) 轴扫描，每次处理一条竖线上的所有矩形的“进入”和“离开”事件。
- 对于每个 (x) 区间，统计当前被覆盖的 (y) 区间总长度（这一步其实就是一维区间合并）。
- 然后用这些长度乘以 (x) 区间的宽度，累加起来就是总面积。

总结

一维区间合并：合并线段，统计总长度。
本题（二维）：合并矩形，统计总面积/格子数。
核心思想：避免重复计数，合并重叠部分。

如果你能熟练解决一维区间合并问题，那么理解和实现本题的二维版本会容易很多！

User

扫描线是什么？

Cursor

当然可以！
让我们用通俗易懂的方式来解释**扫描线（Sweep Line）**算法。

扫描线是什么？

扫描线是一种常用于解决几何问题的算法思想，尤其适合处理“覆盖”、“交集”、“并集”等问题。
它的核心思想是：想象有一根线（通常是竖直或水平的），从一侧“扫”过整个平面，每次只处理当前线经过的事件。

形象比喻

想象你在用扫描仪扫描一张纸。扫描仪的光线从左到右（或从上到下）移动，每次只“看到”当前这一条线上的内容。你只需要关心当前线上的变化，而不用一次性处理整个平面。

扫描线的基本步骤

以矩形面积并为例（和本题类似）：

事件排序
把所有矩形的“左边界”和“右边界”都当作事件，按 (x) 坐标从小到大排序。
线性扫描
用一根“扫描线”从左到右移动，每遇到一个事件就处理一次：
- 如果是矩形的左边界，说明有新矩形“进入”扫描线，加入当前覆盖的区间。
- 如果是右边界，说明有矩形“离开”扫描线，从当前覆盖区间中移除。
统计覆盖长度
在每两个事件之间，扫描线覆盖的 (y) 区间长度是固定的。
用这个长度乘以 (x) 的变化量，就是这段区域的面积。
累加结果
把所有区间的面积加起来，就是总面积。

动画演示（想象）

扫描线从左到右移动。
每遇到一个矩形的左边界，扫描线“记住”这个矩形的 (y) 区间。
每遇到一个右边界，扫描线“忘记”这个矩形的 (y) 区间。
扫描线每次移动时，统计当前所有被覆盖的 (y) 区间总长度。

适用场景

计算多个矩形的面积并
统计区间覆盖长度
计算线段交点
解决区间合并、区间染色等问题

总结

扫描线就是用一根“线”从一侧扫到另一侧，动态维护当前的覆盖情况，遇到事件就更新，适合处理“区间合并”类的二维问题。

如果你会一维区间合并，扫描线就是把这个思想“搬到二维”，每次只处理一条线上的变化！

如果你想看具体的代码实现或动画演示，可以随时告诉我！

User

    let lastX = events[0].x;
    let total = 0;
    // 维护当前被覆盖的y区间
    const yIntervals = [];
    for (const event of events) {
        const dx = event.x - lastX;
        if (dx > 0) {
            // 统计当前y区间总长度
            let covered = 0;
            if (yIntervals.length > 0) {
                // 合并区间
                yIntervals.sort((a, b) => a[0] - b[0]);
                let [curStart, curEnd] = yIntervals[0];
                for (let i = 1; i < yIntervals.length; i++) {
                    const [s, e] = yIntervals[i];
                    if (s > curEnd) {
                        covered += curEnd - curStart;
                        curStart = s;
                        curEnd = e;
                    } else {
                        curEnd = Math.max(curEnd, e);
                    }
                }
                covered += curEnd - curStart;
            }
            total += covered * dx;
        }
        // 更新y区间
        if (event.type === 1) {
            yIntervals.push([event.y1, event.y2]);
        } else {
            // 移除区间
            for (let i = 0; i < yIntervals.length; i++) {
                if (yIntervals[i][0] === event.y1 && yIntervals[i][1] === event.y2) {
                    yIntervals.splice(i, 1);
                    break;
                }
            }
        }
        lastX = event.x;
    }
    results.push(total);
}
return results;

}

处理一下输入输出，完整js代码

Cursor

当然可以！下面是一个完整的 JavaScript 程序，支持 Kattis 题目的输入输出格式（标准输入/输出），并用你给的扫描线算法实现。

完整 JS 代码（Node.js 环境）

// 处理标准输入
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

const rectGroups = [];
let currentGroup = null;
let rectsToRead = 0;

rl.on('line', (line) => {
    line = line.trim();
    if (line === '') return;
    if (rectsToRead === 0) {
        const n = parseInt(line);
        if (n === 0) {
            // 输入结束，处理所有组
            const results = countCoveredSquares(rectGroups);
            for (const res of results) {
                console.log(res);
            }
            process.exit(0);
        }
        currentGroup = { rects: [] };
        rectGroups.push(currentGroup);
        rectsToRead = n;
    } else {
        const [x1, y1, x2, y2] = line.split(' ').map(Number);
        currentGroup.rects.push([x1, y1, x2, y2]);
        rectsToRead--;
    }
});

// 扫描线算法
function countCoveredSquares(rectGroups) {
    const results = [];
    for (const group of rectGroups) {
        if (!group.rects || group.rects.length === 0) continue;
        const events = [];
        for (const [x1, y1, x2, y2] of group.rects) {
            // 只覆盖[x1, y1]到[x2-1, y2-1]的格子
            events.push({ x: x1, y1, y2, type: 1 });  // 左边界，加入
            events.push({ x: x2, y1, y2, type: -1 }); // 右边界，移除
        }
        // 按x排序，x相同先加后减
        events.sort((a, b) => a.x - b.x || b.type - a.type);

        let lastX = events[0].x;
        let total = 0;
        // 维护当前被覆盖的y区间
        const yIntervals = [];
        for (const event of events) {
            const dx = event.x - lastX;
            if (dx > 0) {
                // 统计当前y区间总长度
                let covered = 0;
                if (yIntervals.length > 0) {
                    // 合并区间
                    yIntervals.sort((a, b) => a[0] - b[0]);
                    let [curStart, curEnd] = yIntervals[0];
                    for (let i = 1; i < yIntervals.length; i++) {
                        const [s, e] = yIntervals[i];
                        if (s > curEnd) {
                            covered += curEnd - curStart;
                            curStart = s;
                            curEnd = e;
                        } else {
                            curEnd = Math.max(curEnd, e);
                        }
                    }
                    covered += curEnd - curStart;
                }
                total += covered * dx;
            }
            // 更新y区间
            if (event.type === 1) {
                yIntervals.push([event.y1, event.y2]);
            } else {
                // 移除区间
                for (let i = 0; i < yIntervals.length; i++) {
                    if (yIntervals[i][0] === event.y1 && yIntervals[i][1] === event.y2) {
                        yIntervals.splice(i, 1);
                        break;
                    }
                }
            }
            lastX = event.x;
        }
        results.push(total);
    }
    return results;
}

使用说明

直接用 Node.js 运行此脚本。
输入格式与 Kattis 保持一致，输入以 0 结尾。
输出每组的答案，每行一个。

如需浏览器版本或有其他输入输出需求，请随时告知！

// 处理标准输入
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});

const rectGroups = [];
let currentGroup = null;
let rectsToRead = 0;

rl.on('line', (line) => {
    line = line.trim();
    if (line === '') return;
    if (rectsToRead === 0) {
        const n = parseInt(line);
        if (n === 0) {
            // 输入结束，处理所有组
            const results = countCoveredSquares(rectGroups);
            for (const res of results) {
                console.log(res);
            }
            process.exit(0);
        }
        currentGroup = { rects: [] };
        rectGroups.push(currentGroup);
        rectsToRead = n;
    } else {
        const [x1, y1, x2, y2] = line.split(' ').map(Number);
        currentGroup.rects.push([x1, y1, x2, y2]);
        rectsToRead--;
    }
});

// 扫描线算法
function countCoveredSquares(rectGroups) {
    const results = [];
    for (const group of rectGroups) {
        if (!group.rects || group.rects.length === 0) continue;
        const events = [];
        for (const [x1, y1, x2, y2] of group.rects) {
            // 只覆盖[x1, y1]到[x2-1, y2-1]的格子
            events.push({ x: x1, y1, y2, type: 1 });  // 左边界，加入
            events.push({ x: x2, y1, y2, type: -1 }); // 右边界，移除
        }
        // 按x排序，x相同先加后减
        events.sort((a, b) => a.x - b.x || b.type - a.type);

        let lastX = events[0].x;
        let total = 0;
        // 维护当前被覆盖的y区间
        const yIntervals = [];
        for (const event of events) {
            const dx = event.x - lastX;
            if (dx > 0) {
                // 统计当前y区间总长度
                let covered = 0;
                if (yIntervals.length > 0) {
                    // 合并区间
                    yIntervals.sort((a, b) => a[0] - b[0]);
                    let [curStart, curEnd] = yIntervals[0];
                    for (let i = 1; i < yIntervals.length; i++) {
                        const [s, e] = yIntervals[i];
                        if (s > curEnd) {
                            covered += curEnd - curStart;
                            curStart = s;
                            curEnd = e;
                        } else {
                            curEnd = Math.max(curEnd, e);
                        }
                    }
                    covered += curEnd - curStart;
                }
                total += covered * dx;
            }
            // 更新y区间
            if (event.type === 1) {
                yIntervals.push([event.y1, event.y2]);
            } else {
                // 移除区间
                for (let i = 0; i < yIntervals.length; i++) {
                    if (yIntervals[i][0] === event.y1 && yIntervals[i][1] === event.y2) {
                        yIntervals.splice(i, 1);
                        break;
                    }
                }
            }
            lastX = event.x;
        }
        results.push(total);
    }
    return results;
}

User

Purdue University logo Kattis Cat Search Kattis Courses / CS211-CP1 / 2025-Spring / LATE SUBMISSIONS ONLY / Problems / Baloni tannal Hide Problem E Baloni There are balloons floating in the air in a large room, lined up from left to right. Young Perica likes to play with arrows and practice his hunting abilities. He shoots an arrow from the left to the right side of the room from an arbitrary height he chooses. The arrow moves from left to right, at a chosen height until it finds a balloon. The moment when an arrow touches a balloon, the balloon pops and disappears and the arrow continues its way from left to right at a height decreased by . Therefore, if the arrow was moving at height , after popping the balloon it travels on height .

Our hero’s goal is to pop all the balloons using as few arrows as possible.

Input The first line of input contains the integer ( ). The second line of input contains an array of integers . Each integer ( ) is the height at which the -th balloon floats, respectively from left to right.

Output The first and only line of output must contain the minimal number of times Pero needs to shoot an arrow so that all balloons are popped.

Sample Input 1 Sample Output 1 5 2 1 5 4 3 2 Sample Input 2 Sample Output 2 5 1 2 3 4 5 5 Sample Input 3 Sample Output 3 5 4 5 2 1 4 3 Edit & Submit Metadata My Submissions Hide You need to join the assignment in order to be allowed to submit.

Contact System Status Terms of Service Privacy Policy

首先告诉我这道题的出处，作者，历史故事，接着用有趣和便于理解的方式叙述题目

Cursor

题目出处与作者

这道题目出自 Kattis 在线判题系统，题目名称为 “Baloni”，编号为 Problem E。
作者署名为 tannal，该题目常见于编程竞赛和算法课程练习，尤其在 Purdue University 的 CS211-CP1 课程中出现过。

历史故事（趣味化版本）

在遥远的克罗地亚小镇上，有个叫 Perica 的小朋友，他最喜欢的游戏就是用弓箭射气球。一天，他看到房间里从左到右排着一排五颜六色的气球，气球们漂浮在不同的高度。Perica 想用最少的箭把所有气球都射下来。
不过，他的箭有个特别的魔法：每当射中一个气球后，箭会继续往右飞，但高度会自动降低 1。Perica 可以随意选择每支箭的初始高度，但每支箭只能从左往右飞。

Perica 想知道，他最少需要射几支箭，才能把所有气球都射下来？聪明的你能帮他算一算吗？

题目趣味叙述

想象你在玩一个气球射击游戏。

有一排气球，从左到右排成一行，每个气球漂浮在不同的高度。
你可以从任意高度发射一支箭，箭会从左往右飞。
每当箭碰到一个气球，气球就会爆炸，箭的高度会自动下降 1，然后继续往右飞。
如果箭的高度低于下一个气球，就射不到了，需要重新发射一支新箭。

你的目标是：用最少的箭把所有气球都射下来！

输入方式

第一行：气球的数量 ( n )。
第二行：( n ) 个整数，分别表示每个气球的高度。

输出方式

输出最少需要多少支箭。

样例

输入1：

5
2 1 5 4 3

输出1：

输入2：

5
1 2 3 4 5

输出2：

输入3：

5
4 5 2 1 4

输出3：

总结

这道题考察你如何贪心地安排每支箭的使用，避免浪费，尽量让每支箭射中更多的气球。
你能帮 Perica 用最少的箭把所有气球都射下来吗？快来挑战一下吧！

5
2 1 5 4 3

5
1 2 3 4 5

5
4 5 2 1 4

User

hinton说anology

Cursor

你提到的 “Hinton 说 analogy”，这里的 Hinton 很可能指的是深度学习领域的奠基人之一 Geoffrey Hinton。他在神经网络、人工智能等领域有很多开创性的工作，也经常在演讲和论文中谈到“类比（analogy）”在智能中的作用。

Hinton 关于 analogy（类比）的观点

1. 类比是智能的核心

Hinton 认为，类比（analogy） 是人类智能和学习的核心能力之一。

人类能够通过类比，把已知的知识迁移到新情境中。
比如：你学会了骑自行车，再学骑摩托车时会用到很多相似的动作和思维方式。

2. 神经网络与类比

Hinton 认为，神经网络 的强大之处在于它们能够自动发现和利用数据中的模式和结构，这其实就是一种“类比”能力的体现。

神经网络可以在不同任务、不同数据之间迁移知识。
例如，卷积神经网络在识别猫和狗时，能自动学会“耳朵”、“眼睛”等局部特征的类比。

3. 经典引用

Hinton 在多次演讲和论文中提到：

“类比是人类思维的核心。我们能够通过把一个领域的结构映射到另一个领域，来理解和解决新问题。”

他还曾说过：

“真正的智能体应该能够做类比推理（analogical reasoning）。”

4. 例子

物理类比：你学会了水流的规律，再去理解电流时，可以用“水流-电流”类比。
语言类比：你学会了英语的语法，再学法语时会发现很多相似的结构。

总结

Hinton 认为，类比（analogy） 是智能的本质之一。

人类善于通过类比迁移知识，解决新问题。
神经网络和 AI 也应该具备这种能力，这样才能更像人类一样灵活、强大。

如果你想看 Hinton 具体哪篇论文或演讲里提到 analogy，可以告诉我，我可以帮你查找原文出处！

User

Registration for Summer Live Classes is Open!

Sections Problems

Resources Contact Us

Search Login USACO Guide A free collection of curated, high-quality resources to take you from Bronze to Platinum and beyond.

Get Started Created by the CP Initiative Learn USACO. Efficiently. Stop wasting time searching for problems and tutorials. The USACO Guide provides a comprehensive, organized roadmap carefully designed and crafted for USACO contestants – available to everyone, for free.

Resources CF EDU: DSU video explanation + problems for DSU CSA Disjoint Data Sets both optimizations, diagrams PAPS 11.1 - Disjoint Sets both optimizations, no diagrams CPH 15.2 - Union-Find small to large, diagrams Curated Resources Learn new topics from a vetted list of high-quality resources. If one resource doesn’t click, look at another!

Source Problem Name Difficulty CSES Road Construction Easy USACO Gold Closing the Farm Easy USACO Gold Mootube Normal Baltic OI 2016 - Park Hard Extensive Problemsets Practice each topic with extensive problemsets and solutions covering a wide range of difficulties.

Modules Progress 6 Completed 3 In Progress 2 Skipped 1 Not Started 12 total Progress Tracking Use our progress-tracking tools to track your progress in the Guide and stay motivated.

USACO Forum Screenshot Help when you need it Get help from other community members in the USACO Forum. View Forum →

Trusted by thousands This guide is written by top USACO contestants, including two-time IOI winner and USACO Problemsetter Benjamin Qi.

Registered Users 105k Pageviews 25.2M GitHub Stars 1695 View Guide Created by the CP Initiative. Here are some of our other projects you might find useful!

USACO Classes Learn USACO through affordable, high-quality classes with a curriculum designed and developed by past USACO Finalists.

Learn More → USACO IDE A realtime collaborative online IDE designed for competitive programming and USACO.

Learn More → USACO Groups A Learning Management System fully integrated with the USACO Guide. Perfect for clubs or group study sessions.

Learn More → Club Curriculum Join our competitive programming club network to get access to exclusive club curriculum and resources!

Learn More → Competitive Programming Contests Participate in high-quality programming contests targeted towards pre-college students!

Learn More → Competitive Programming Workshops Access workshops providing everything you need to know about USACO.

Learn More → Join our Team. The Competitive Programming Initiative is a student-run organization dedicated to promoting competitive programming. Join us in our mission, and earn PVSA volunteer hours and leadership positions along the way!

Apply Now Or, help us financially! We’re a 501(c)3 nonprofit organization — all donations are tax deductible. Since our inception in September 2020, we’ve impacted tens of thousands of students across our various initiatives.

Sponsor Us or Donate via PayPal

Read our sponsorship prospectus Our Sponsors

Platinum Sponsors

Non-Trivial logo Bronze Sponsors

EasyFunCoding logo Frequently asked questions What is the USACO? USACO stands for the USA Computing Olympiad. Check out the USACO FAQ Page for more information.

Is this an official syllabus? No, USACO does not have an official syllabus. This guide merely lists topics that have historically appeared in USACO contests; it makes no guarantees about the topics in future USACO contests.

How do I report a problem or ask a question? If you encounter an issue while using the guide (website bug, typo, broken link, unclear explanation, etc), use the “Contact Us” button. Alternatively, email us at usacoguide@gmail.com.

I’m looking for classes, club curriculum… Check out the Competitive Programming Initiative!

Is this guide for non-USACO competitive programmers? Of course! While we structure our content around USACO, feel free to use this guide even if you don’t do USACO. You will still learn a lot from it!

How can I get help? If you get stuck, head over to the USACO Forum for help.

How can I contribute? To learn more about contributing, please visit this page. We appreciate any and all contributions!

Is this open source? Yes! Check out our GitHub Repository.

Contributors

By the Community, for the Community. Comprised of USACO Finalists and top USACO competitors, our team is committed to increasing participation in competitive programming.

Benjamin Qi Benjamin Qi

Kevin Sheng Kevin Sheng

Ryan Chou Ryan Chou

Nathan Wang Nathan Wang

Melody Yu Melody Yu

Bing-Dong Liu Bing-Dong Liu

Evan Zhao Evan Zhao

Ryan Fu Ryan Fu

Justin Ji Justin Ji

Tatha Pandey Tatha Pandey

Daniel Zhu Daniel Zhu

Justin Huang Justin Huang

Trisha Sabadra Trisha Sabadra

Aakash Gokhale Aakash Gokhale

Alex Wang Alex Wang

Andrew Xu Andrew Xu

Chongtian Ma Chongtian Ma

Peng Bai Peng Bai

Rameez Parwez Rameez Parwez

Former Team Members Jesse Choe Jesse Choe

Amy Chang Amy Chang

Arpan Banerjee Arpan Banerjee

Daniel Guan Daniel Guan

Jay Fu Jay Fu

Maggie Liu Maggie Liu

Nathan Chen Nathan Chen

Neo Wang Neo Wang

Nikhil Chatterjee Nikhil Chatterjee

Varun Ragunath Varun Ragunath

Albert Zhu Albert Zhu

Amogha Pokkulandra Amogha Pokkulandra

Andrew Wang Andrew Wang

Atharv Jain Atharv Jain

Darren Yao Darren Yao

David Li David Li

David Zhang David Zhang

Dustin Miao Dustin Miao

Faris Raza Faris Raza

Harry Wang Harry Wang

Jeffrey Meng Jeffrey Meng

Juheon Rhee Juheon Rhee

Michael Cao Michael Cao

Nathan Gong Nathan Gong

Pranav Jadhav Pranav Jadhav

Vikas Thoutam Vikas Thoutam

Aadit Ambadkar Aadit Ambadkar

Adham Ibrahim Adham Ibrahim

Aditya Gupta Aditya Gupta

Advay Bajpai Advay Bajpai

Akshar Yeccherla Akshar Yeccherla

Albert Jiang Albert Jiang

Alex Chen Alex Chen

Alex Du Alex Du

Andi Qu Andi Qu

Arnan Bawa Arnan Bawa

Arnav Adhikari Arnav Adhikari

Ben Dodge Ben Dodge

Chuyang Wang Chuyang Wang

Daniel Ge Daniel Ge

Eric Xu Eric Xu

Frank Xiao Frank Xiao

Harsh Akunuri Harsh Akunuri

Ian Zhang Ian Zhang

Jaiman Pandya Jaiman Pandya

Jason Antwi-Appah Jason Antwi-Appah

Jeffrey Zhang Jeffrey Zhang

John Tian John Tian

Jonathan Paulson Jonathan Paulson

Lokesh Pampatti Lokesh Pampatti

Mihnea Brebenel Mihnea Brebenel

Mithil Srungarapu Mithil Srungarapu

Mrinall Umasudhan Mrinall Umasudhan

Nathan Zhang Nathan Zhang

Nikita Gorshkov Nikita Gorshkov

Oscar Rendón Oscar Rendón

Paul Chen Paul Chen

Riley Bonner Riley Bonner

Shikhar Ahuja Shikhar Ahuja

Siyong Huang Siyong Huang

Sofia Yang Sofia Yang

Stanley Zhao Stanley Zhao

Vidith Madhu Vidith Madhu

Vivian Han Vivian Han

Yifan Ma Yifan Ma

这是什么玩意？

Cursor

你看到的这个页面内容，实际上是USACO Guide（美国信息学奥林匹克指南，https://usaco.guide/）的介绍和部分内容。

这是什么？

USACO Guide 是一个由美国信息学奥林匹克（USACO）高水平选手和志愿者团队维护的、完全免费的在线学习平台。
它的目标是帮助学生系统地学习算法竞赛（尤其是 USACO）所需的知识，从入门到高级（Bronze → Silver → Gold → Platinum），并提供大量精选题目、教程、视频、进度追踪等功能。

主要内容和功能

系统化学习路线
- 按照 USACO 的分级（Bronze, Silver, Gold, Platinum）组织知识点和题目。
- 每个知识点配有详细讲解、代码模板、例题和习题。
高质量资源
- 精选了 CSES、Codeforces、USACO、Baltic OI 等各大平台的优质题目。
- 每个知识点下有多种不同风格的教程和视频，适合不同学习习惯的同学。
进度追踪
- 可以注册账号，记录自己完成了哪些模块、做了哪些题，方便长期学习和复习。
社区支持
- 有 USACO 论坛，遇到问题可以向其他同学和高手请教。
- 由众多 USACO Finalist 和 IOI 获奖者维护和解答。
开源与公益
- 完全免费，开源，接受捐赠和志愿者加入。
- 由 Competitive Programming Initiative 组织运营。

适合谁用？

想系统学习算法竞赛（尤其是 USACO）的同学。
需要刷题、查找优质题解和教程的同学。
需要进度管理和社区支持的同学。
也适合非 USACO 选手，内容覆盖了大部分常见算法竞赛知识点。

总结一句话

USACO Guide 就是一个“算法竞赛自学宝典”，内容权威、体系完整、题目丰富、完全免费，非常适合准备 USACO 或其他信息学竞赛的同学使用！

如果你想了解某个具体功能、模块或如何使用，可以告诉我！

User

Z Algorithm Time Limit: 5 sec

Problem Statement Given a length N N string S S. Calculate array a 0 , a 1 , . . . , a N − 1 a 0 ,a 1 ,…,a N−1 as follows:

a i a i is the LCP(longest common prefix) of S S and S . s u b s t r ( i ) S.substr(i). Constraints 1 ≤ N ≤ 5 × 1 0 5 1≤N≤5×10 5

Each character of S S is lowercase English letters. Input S S Output a 0 a 0

a 1 a 1

a 2 a 2 … a N − 1 a N−1

Sample #1 abcbcba 7 0 0 0 0 0 1 #2 mississippi 11 0 0 0 0 0 0 0 0 0 0 #3 ababacaca 9 0 3 0 1 0 1 0 1 #4 aaaaa 5 4 3 2 1 C++(Function) header

Unsupported

Submit

首先告诉我这道题的出处，作者，历史故事，接着用有趣和便于理解的方式叙述题目

Cursor

题目出处与作者

这道题目是算法竞赛和字符串算法领域的经典题，常见于各大OJ（如 AtCoder、Codeforces、洛谷等）和算法书籍中，通常被称为 Z-Algorithm 或 Z-Function 题。
具体作者不详，但 Z-Algorithm 由 Gusfield 等人在 1970-1980 年代提出，是字符串处理领域的基础算法之一。

历史故事（趣味化版本）

在遥远的“字符串王国”里，国王喜欢考验大臣们的观察力。他会给大臣们一串神秘的字符，然后问：“对于这串字符的每一个位置，从这里开始的子串和整串字符串的最长公共前缀有多长？”
聪明的大臣们发现，如果每次都暴力比对，效率太低。于是有位天才大臣发明了“Z算法”，能在一眨眼的功夫里算出所有答案，国王大喜，封他为“字符串大师”！

题目趣味叙述

想象你有一串字符，比如 "abcbcba"。
你要做的事情是：

对于每一个位置 ( i )（从 0 到 ( N-1 )），
你要比较：
- 整个字符串 ( S )
- 和从第 ( i ) 个字符开始的子串 ( S[i:] )
问：这两串从头开始有多长的“公共前缀”？

比如：

( i = 0 ) 时，就是 ( S ) 和 ( S ) 本身，当然全都一样，答案是 ( N )。
( i = 1 ) 时，就是 ( S ) 和 ( S[1:] )，看它们从头有多少个字符一样。

你要把每个位置的答案都输出出来！

输入输出格式

输入：
一行字符串 ( S )。

输出：
一行 ( N ) 个整数，第 ( i ) 个数表示 ( S ) 和 ( S[i:] ) 的最长公共前缀长度。

样例

输入1：

abcbcba

输出1：

7 0 0 0 0 0 1

输入2：

aaaaa

输出2：

5 4 3 2 1

总结

这道题考察你对字符串前缀匹配的理解，以及高效算法（Z-Algorithm）的实现能力。
你能像“字符串大师”一样，一眨眼就算出所有答案吗？快来挑战一下吧！

abcbcba

7 0 0 0 0 0 1

aaaaa

5 4 3 2 1

User

提示一下

Cursor

当然可以！这里给你一些Z-Algorithm（Z函数）的解题提示：

1. 什么是 Z-Algorithm？

Z-Algorithm 用于高效计算一个字符串的所有后缀与原串的最长公共前缀（LCP）长度。
对于字符串 ( S ) 的每个位置 ( i )，Z[i] 表示 ( S ) 和 ( S[i:] ) 的最长公共前缀长度。

2. 暴力做法（不推荐）

对于每个 ( i )，直接比较 ( S ) 和 ( S[i:] ) 的每个字符，直到遇到不同为止。

时间复杂度 ( O(N^2) )，会超时。

3. 高效做法（Z-Algorithm）

Z-Algorithm 可以在 ( O(N) ) 时间内计算所有 Z 值。
核心思想是：

维护一个区间 ([l, r])，表示当前已知的最长匹配区间。
如果 ( i > r )，就暴力匹配。
如果 ( i \leq r )，利用之前的结果快速跳过一部分匹配。

4. 伪代码提示

Z[0] = N
l = r = 0
for i = 1 to N-1:
    if i > r:
        // 暴力匹配
        while S[j] == S[i+j]: j++
        Z[i] = j
        if j > 0: l = i, r = i + j - 1
    else:
        k = i - l
        if Z[k] < r - i + 1:
            Z[i] = Z[k]
        else:
            j = r - i + 1
            while S[j] == S[i+j]: j++
            Z[i] = j
            l = i
            r = i + j - 1

5. 特别注意

Z[0] 一定等于字符串长度 N。
输出时，Z 数组的每一项用空格隔开。

6. 例子

对于 aaaaa，

Z[0] = 5
Z[1] = 4
Z[2] = 3
Z[3] = 2
Z[4] = 1

如果你需要代码模板或更详细的讲解，可以随时告诉我！

Z[0] = N
l = r = 0
for i = 1 to N-1:
    if i > r:
        // 暴力匹配
        while S[j] == S[i+j]: j++
        Z[i] = j
        if j > 0: l = i, r = i + j - 1
    else:
        k = i - l
        if Z[k] < r - i + 1:
            Z[i] = Z[k]
        else:
            j = r - i + 1
            while S[j] == S[i+j]: j++
            Z[i] = j
            l = i
            r = i + j - 1

User

Competition Programming and Problem Solving Seminar CS 5199 Fall 2019 Mon/Fri 10:10AM, Hollister Hall 110 Robbert van Renesse and Haobin Ni

The Competition Programming and Problem Solving Seminar (CP seminar in short) is an experimental seminar for discussing and practicing applied algorithms and techniques presented in programming contests, technical interviews, and problem solving through algorithms and programming in general. The goal is to provide a broader view of algorithms in practice and strengthen students’ skills in problem solving.

We meet twice every week. For about half of the lectures, a student or an invited speaker will present on a selected topic. The other half is more like a lab where students will solve problems in-class with help from mentors. We meet on Monday and Friday at 10:10AM in Hollister Hall 110.

The CP seminar is open to all Cornell students interested in this topic. Student participants are expected to sign up for CS 5199 for one credit.

Please join our Piazza for notifications and after-class discussions.

The CP seminar is co-organized with Cornell ICPC Project Team.

We greatly encourage students to sign up for a talk. For signing up, please contact Robbert van Renesse (rv22) or Haobin Ni (hn332). Signup Form

Other semesters: spring 19 Date Topic Presenter August 30 Introduction Slides

September 2 Labor Day, no meeting. September 6 Lab 1 Instructions Class Group Problems

September 9 Bruteforce Handout Example Problem Homework Problem Yunhao Zhang September 13 Lab 2 - Bruteforce Problems Slides

September 16 How to Solve Problems Slides Feedback Haobin Ni September 20 Lab 3 - Trivial? Problems Slides

September 23 Binary Search Slides Feedback Shuang Chen September 27 Lab 4 - Binary Search Problems Slides

September 30 Lab 5 - Basic DP Problems Slides

October 4 Basic DP SlidesFeedback Horace He October 7 Segment Tree Slides Raunak Kumar October 11 Lab 6 - Data Structures I Problems Instructions

October 14 Fall Break, no meeting. October 18 Lab 6’ - Data Structures II

October 21 Range Minimum Query Slides Siqiu Yao October 25 Lab 7 - Minimum Range Query Problems

October 28 Number Theory Slides Feedback Aaron Lou November 1 Lab 8 - Math Problems Instructions

November 4 String Slides Jyun-Jie Liao November 8 Lab 9 - Strings Problems

November 11 Meet in the Middle Slides Haobin Ni November 15 Lab 10 Problems

November 18 Advanced DP Slides Horace He November 22 Lab 11 - Advanced DP Problems

November 25 Fast Modulo Multiplication Slides Di Chen November 29 Thanksgiving Break, no meeting. December 2 Canceled due to weather, no meeting.

这些都是什么？

Cursor

你看到的这些内容，是**康奈尔大学（Cornell University）CS 5199 课程——“竞赛编程与问题求解研讨会”（Competition Programming and Problem Solving Seminar）**的课程介绍和部分课程安排。

这是什么？

CS 5199: Competition Programming and Problem Solving Seminar

是康奈尔大学开设的一门面向所有对算法竞赛、技术面试、算法问题求解感兴趣学生的研讨课。
由 Robbert van Renesse 和 Haobin Ni 主持，和 Cornell ICPC Project Team（国际大学生程序设计竞赛团队）联合组织。
课程编号为 CS 5199，属于选修课，1 学分。

课程内容和形式

目标：提升学生在实际算法问题中的分析、建模和编程能力，拓宽算法视野，为竞赛和技术面试做准备。
形式：每周两次课，一半是专题讲座（由老师、学生或嘉宾主讲），一半是上机练习（Lab），有导师现场辅导。
内容涵盖：
- 暴力搜索（Bruteforce）
- 二分查找（Binary Search）
- 动态规划（DP）
- 线段树、区间最小值查询（Segment Tree, Range Minimum Query）
- 数论（Number Theory）
- 字符串算法（String）
- Meet in the Middle
- 快速取模乘法（Fast Modulo Multiplication）
- 还有各种竞赛常见技巧和专题

课程特色

开放性：对所有康奈尔学生开放，欢迎有兴趣的同学旁听或选课。
实践性强：大量现场刷题和小组讨论，强调动手能力。
社区氛围：有 Piazza 讨论区，便于课后交流和答疑。
与 ICPC 团队合作：有助于准备 ACM-ICPC 等算法竞赛。

课程安排举例

8月30日：课程介绍
9月6日：Lab 1
9月9日：暴力搜索专题
9月16日：如何解决问题
9月23日：二分查找
10月4日：基础动态规划
10月7日：线段树
10月28日：数论
11月4日：字符串算法
11月11日：Meet in the Middle
11月18日：高级动态规划
11月25日：快速取模乘法

（中间穿插假期、Lab、天气原因取消等）

总结一句话

这是康奈尔大学面向算法竞赛和技术面试的算法专题研讨课，内容丰富，实践性强，非常适合想提升算法能力的同学。

如果你想了解某个专题的讲义、题目或具体内容，可以告诉我！

User

搜索类似的东西，关键词是什么

Cursor

你可以用以下关键词来搜索类似的课程、资源或活动：

英文关键词

competitive programming seminar
algorithmic problem solving course
university programming contest course
ICPC training seminar
programming contest workshop
algorithm seminar university
coding interview preparation course
algorithmic techniques seminar
data structures and algorithms seminar
programming competition class

中文关键词

竞赛编程研讨课
算法竞赛课程
ACM/ICPC 培训班
算法专题讲座
编程竞赛训练营
算法与数据结构课程

你可以在 Google、学校官网、Coursera、edX、Bilibili、知乎等平台用这些关键词搜索，会找到很多大学、社团、在线平台的相关课程和资源。如果需要具体的课程推荐或公开课链接，也可以告诉我！

User

CS3233 logo World of 7

Introduction Registration

News Ranklist Lesson Plan Hall of Fame Scoring Scheme

VisuAlgo Discord Server

CS2040S CS3230 CS3233 IT5003 My Teaching CSBooks@VA

PhD Tips CS3233 - Competitive Programming Introduction This course aims to prepare students in competitive problem solving.

It will benefit NUS students who want to compete in ICPC, invited high school students (via CeNCE CS3) who want to compete in IOI (not just for NOI), and NUS students in general who aspire to excel in technical interviews of top IT companies, especially NUS current (2025++) ICPC donors: Jane Street, HRT, Jump Trading, Optiver, Citadel | Citadel Securities, and Huawei.

It covers techniques for attacking and solving challenging* computational problems. Fundamental algorithmic solving techniques covered include complete search, divide/reduce/transform and conquer, greedy, dynamic programming, etc. Domain specific techniques like graph, mathematics-related, string processing, and computational geometry will also be covered. Some additional topics may be included depending on how the semester progresses. Programming language libraries that are commonly used in problem solving will also be taught.

*We only study well-known/solved problems, not research problems.

Note: This introductory message will not be prominent the next time you visit this URL again. This behavior is normal. You can view it again by scrolling to the top of this page.

Course Registration The quota of this class (S2 AY 2022/23 onwards) is 39, as that is the largest class size that is still considered a ‘small course’ where Bell Curve system does not have to be used. In 16+ academic years of CS3233 classes, on average only ~20 NUS students were enrolled per year. Although it was 30+ in the last three AYs (possibly including this S2 AY24/25).

Useful information to help you decide on whether you should offline register for CS3233:

Do you have national (but preferably international) programming competition background before? Examples: SGP NOI (or IDN OSN, VNM VNOI, CHN NOIP, MYS MCO, PHL NOI, IND ICO, etc), IOI (especially the recent IOI 2024 or IOI 2023), ICPC (especially the recent ICPC Asia Jakarta, Hanoi, and/or Yokohama 2024), Facebook Hacker Cup, CodeForces rated rounds, etc?

The difficulty of this course is very extreme for those without such background… but typically those that satisfy the next requirement (see question 2) can survive just as well… We will study problems that require (advanced) data structure and/or algorithms that are typically asked in programming competitions, and we have to implement those solutions fast and without bug…

Did you score well (at least A-) in CS1010/variant and CS2040/variant (and preferably score A+ in all; CS3230 (and CS4234) are good to have but optional)?

This course has a very high performance bar and the average GPA of the students enrolled in the recent AYs are/were 4.67 (this S2 AY24/25), did not track/ask between 2023 back to 2020, 4.57 (2019), 4.78 (2018, early year of grade-free first year policy), 4.3+, 4.33, 4.44, 4.43, 4.45, and 4.30 (out of 5.00), respectively. You will need special permission from the instructor (A/Prof Steven Halim) if you do not satisfy the pre-requisites listed above (the filter is there for your own good). PS: Getting at least A- in CS2030/variant is included as official pre-requisite of CS3233, but an exception can be made if all other indicators are good.

Are you OK to be tortured for one semester for a mere 4 units (your other courses may also suffer)?

You may have to take lighter set of other courses or be ready to S/U other courses or to rush course project submissions (for project-based courses that have STePS on Wednesday night of Week 13 — no longer clash with CS3233 Monday night classes) or to rush final assessment preparations for other courses only during study week (no final assessment for CS3233). Please do NOT take CS3233 course with another course that is known to be challenging/demanding (e.g., the 5 units CS3217 in Sem2, among others) unless you are very confident of yourself and have historical academic performance to back that up. Moreover, your ego may be hurt if some of the young NOI trainees (Sec2-JC2 students) beat you in (many) CS3233 contests (a few guest students may now return to F2F mode onsite at PL2-TBC). Try to ask CS3233 seniors who have taken (and survived) this course before applying, or read their public stories, e.g., Lim Jay Ching (exchange from University of Waterloo).

Are you thinking on applying to top (or emerging) IT companies like NUS current (2024/25; list to be refreshed by January 2025) ICPC donors: Jane Street, HRT, Jump Trading, Optiver, Citadel | Citadel Securities, Huawei, or other large IT companies like Google, Meta (Facebook), Microsoft, Sea Group, etc in the future?

Some of our ex-CS3233 graduates are now in those companies :). See the CS3233 Hall of Fame to see the current known status of CS3233 past top students. Since a few AYs ago, many of these company (HR) reps will (e-)visit some of our (mini) contests and give prizes and/or recruitment talks which may be (much) faster than normal application route… Some seniors have cited that these direct connections with top IT companies is actually one of the nicest features of CS3233…

Can you code in C++ (primary language), Python (second choice), and/or Java (third choice)?

We will use C++ (17), Python (3), and Java (17) in CS3233 (in that order :O). In this course, we are expecting students to be multi-lingual :O. Although a few ex-students had survived CS3233 with only (or mostly) Java and/or the slower Python, they struggled more compared to those who are well versed in C++ (fastest programming language for programming competitions). Since AY 2018/19, Python (3) has been used and has given some advantage at certain problems for students who master this language. However, Python code is usually slow (albeit usually also shorter). An algorithm written in Python may get TLE while the same algorithm written in C++/Java pass the time limit.

Do you want to learn interesting data structures, algorithms, (other programming language especially if C++ is not your primary language) and more importantly: On how to apply them properly — from teaching staffs who are deeply involved in such programming competitions?

Instructor: Associate Professor Steven Halim, current CeNCE Director, Singapore IOI team leader, ICPC Asia Pacific Championship 2025 Contest Director (also Asia Singapore Regionals 2015 and 2018), the author of Competitive Programming text book (the official text book of this course, we will use CP4 Book 1 and Book 2), former Deputy Director for IOI 2020 and IOI 2021 in Singapore (online competitions), former NUS ICPC coach (5x ICPC World Finals Coach Award).

Rating (out of 5.0) Jan-Apr 2025 (n=34) Jan-Apr 2024 (n=34) Jan-Apr 2023 (n=31) Jan-Apr 2022 (n=28) Jan-Apr 2021 (n=18) Jan-Apr 2020 (n=12) Course feedback (SoC avg lvl 3000 ~3.9) ≥ 4.4 (tgt) 4.4 ▼ 4.9 (PB) ▲ 4.7 ▼ 4.8 ▼ 4.9 (PB) Course difficulty (SoC avg lvl 3000 ~3.8) ≤ 4.3 (tgt) 4.3 ▼ 4.6 (PW) ▲ 4.3 == 4.3 ▲ 4.2 Prof Halim’s teaching (SoC avg lvl 2000 ~4.2) ≥ 4.5 (tgt) 4.6 ▼ 4.9 (PB) ▲ 4.8 ▼ 4.9 (PB) == 4.9 (PB) Qualified Teaching Assistant(s):

Teow Hua Jun, IOI Bronze Medallist Yeung Man Tsung, CS3233 winner S2 AY 2022/23, IOI Silver Medallist [and a few other behind-the-scenes problem setters for midterm and final contests]

Usually, CS3233 TAs have teaching feedback rating of around ~4.5 too (i.e., very good). TA will be mostly available in NUS ICPC Lab (COM1-02-15), especially every Monday, 4.00-5.15pm to answer any CS3233/Competitive Programming queries, if any.

Are you OK to have your coding style ‘somewhat damaged’ because of this course?

Known damages are (illustrations are in C++), but not limited to:

One character variable names (why type more than necessary), e.g., int i,j,k,l,m,n,u,v,w,x,y; (PS: i,j,k,l for up to 4-nested loop counter variables, m,n for number of edges/vertices of a graph, u,v,w for reading directed edge (u → v) with weight w, and x,y for 2D Cartesian coordinate system) Putting most of those variables as global variables (so that you never have to pass them as function parameter(s) — even by reference, especially the heavy ones like multi-dimensional arrays — to reduce ‘out of stack space’/‘stack overflow’ issue) Intentional memory wastage by declaring big arrays as global variable (usually DP table) as big (or slightly bigger) as the problem statement says, e.g., int memo[1000][1000][2]; although we may only use parts of it on many smaller test cases If local (loop) variables are needed, use for-loop’s initialization part (why waste additional lineS), e.g., for (int i=0,ans=0,flag=1;i<N;++i){…} Using autos everywhere and let the compiler do the variable type deduction work, e.g., for (auto& [v,w]:AL[u]){…} No comment (compiler doesn’t need that to compile your code and you won’t read your own code after end of contest/max 5 hours, so why write comments?) No function other than int main() unless you need to write a recursive function (your compiler just need this to run your code!) No space unless absolutely necessary (your compiler understands that :O), e.g., for(sum=i=0;i<N;++i)sum+=(A[i]>0?A[i]:0); One-liner-ing selection/repetition command/body if they are short, e.g., if (x>0) ++y,++z;, for (int i=0,j=1;i<N;++i,j*=2) or while (scanf("%d",&N),N){…} (yes, you can use commaS) Use (uhuk… nested…) ternary operation (condition1)?(condition2?if_1true2true:if_1true2false):(if_1false); as far as possible if that helps you to one-liner several standard if-elseif-else lines… Inlining (and one-liner-ing) short functions like inline inside(int r,int c){return r>=0&&r<R&&c>=0&&c<C;} for slightly faster speed As we want to shorten SLOC as far as possible, obviously we do not need to use blank line to separate logical blocks of code Excessive usage of constants/macros and typedefs, e.g., const int INF=1e9; const int MOD=1e9+7; typedef long long ll; typedef tuple<int,int,int> iii; Use bitmask operations whenever possible, e.g., printf("%d\n", __builtin_popcount(m)); Including all libraries upfront, much more than possibly necessary, to avoid silly compilation errors albeit (slightly) increase compilation time, e.g., #include <bits/stdc++.h> ‘Hack’ C++ STL defaults to suit our needs, e.g., inserting negated input integers into priority_queue pq; to make it into a Min-PQ instead of default Max-PQ (instead of definining our own comparison function) Intentional memory leaks, e.g., instead of wasting runtime ‘free’ing deleted vertices in a pointer based segment tree, we just re-initialize a new segment tree for another test case (especially after seeing memory limit = 2GB, for example) On some rare occassions, we use the ‘forbidden’ goto statement… Using C++ operator shortcuts as far as possible, e.g., ++i; i*=2; i%=7; using namespace std (as there is no other namespace to consider in a short C++ program) And many scary stuffs that are hated by SE purists

Fortunately, it is known that past CP-ers can somehow undo these damages to return back to normal SE practices, e.g., this one (so don’t worry my fellow SoC SE colleagues :).

If you have read all (scary) questions above and are still interested, simply complete this application form to join CS3233 S2 AY2024/25 for offline registration before round 3 (the last day of application). The offline registration will be closed as soon as the number of students hits 39 accepted NUS students.

To minimize the annual attrition rate on Week 02 (Drop without penalty) and also :O on Recess Week (Drop with a ‘W’ grade, it happens!), the pre-acceptance selection will be made reasonably rigorous, i.e., by showing Prof Halim that the applicant has at least CodeForces (max) rating of ≥ 14001299 (naturally talented, PS: this is a more accurate predictor of potential CS3233 grade) by Tuesday, 31 December 2024, 23.59.

Note: This course registration section will not be prominent from Monday, 09 January 2025 onwards (Week -01). This behavior is normal. You can view it again by scrolling to the top of this page.

News Date News Mon, 14 Apr 25 new Tonight is the last night of CS3233 of this S2 AY24/25. Enjoy the final team contest. Mon, 07 Apr 25 As the course is ending soon, the entire lesson plan is reopened to prepare students for the Final Team Contest next week. Ranklist

Senior students (for CS3233R only): Ong Weng Qi. Senior students (lurking as guest students): Ho Hong Wei, Tan Kwang Thiag. Another lurkers: errorgorn, pavement.

Lesson Plan Week Self Reading from CP4 before class (Flipped Classroom) Homework (Mon, 9.00am) Contest + Debrief/Donor Talk (Mon, 5.30-6.45-7.15pm, PL2) Class Topics (Mon, 7.30-9.00pm, PL2) -06/-05/ -04/-03/ -02/-01 As many pages from CP4 Book 1+2; at least from preface up to the end of Chapter 4 (the entire Book 1 basically); Note: For the actual semester, you must have a(n electronic) copy of CP4 (both book 1+2) to go through this course successfully; if you don’t already have both books, go to lulu.com to get a (legit) copy. Lots of preparatory work especially for those who do not have competitive programming background yet

Optional Kattis set #00 starts on Monday, 06 Jan 2025, 21:00 SGT No contest yet; But if you are not a multi-lingual programmer yet, pick up both C++17 (main), Python3 (secondary), and Java17 (tertiary) by yourself during holiday time At home: Set up a (free) Codeforces account, then use Dec24+early Jan25 holiday (~3-4 weeks) to get ≥ 1299 rating in CodeForces and/or set up a (free) Kattis (open) account, then get ≥ 500.0 points (~250 AC of ~2 pointer problems, see first ~3+ pages sorted based on Kattis difficulty ratings :O), use Prof Halim’s classification here) in Kattis by Tue, 31 Dec 24, 23:59 (or MUCH earlier) to ensure course acceptance, familiarize yourself with Ubuntu 22 LTS with GNOME desktop, or self-read the older teaching materials in this public website 01 13 Jan Preface to Chapter 1 (all pages) plus simple Ad Hoc problems in Chapter 2+3+9

Optional Kattis set #00 due

The official Kattis set #01 starts Mock Ad Hoc (after first lecture) Let’s Talk CP

Introduction; Brief Course Admins; Focus on delivering some “Wow Moments”; A Bit of C++17, Python3, Java17, Mock/Preview Contest (not graded, but has high standard) 02 20 Jan Chapter 2; Focus on Section 2.2 and 2.4.3 Read the rest of Chapter 2 by yourself Solve Mock 01 B/C HW01 due Kattis set #01 due

and Kattis set #02 starts (we repeat this pattern until Set #12) Mini 01 O(n1.5) Algorithms Money Contest funded by NUS ICPC endowment Be A Librarian

Mastery of Libraries (C++ STL, Python Standard Library, & Java API); Focus on Bit Manipulation and Binary Indexed (Fenwick) vs Segment Tree VisuAlgo: bitmask, ufds, fenwicktree (optional), and segmenttree

Decision to Drop CS3233/R without penalty by Fri, 24 Jan 25 (this time you can self-drop, but do inform Prof Halim first; hopefully we have ’no-one-drop-by-week-02’ whenever possible) 03 27 Jan Chapter 3, 4, 8, and 9; Focus on Section 3.1-2, 4.2.3, 4.4.2-3, 8.1-8.2, 8.6 (some NP-hard/complete problems with complete search solution), 9.20, and 9.21; Read Section 3.3 (DnC) too, especially about BSTA Solve Mini 01 B/C HW02 due Kattis set #02 due Mini 02 Libraries Money Contest funded by NUS ICPC endowment (Binary) Searching for Answers

Iterative Techniques (the fancier ones); Recursive Backtracking (bitmask-based, reverse thinking, data compression, etc); State-Space Search (harder form of SSSP, Graph modeling + BFS/Dijkstra’s) with Meet in the Middle (Bidirectional Search); and finally, what if we can ‘guess’ the answer in Binary Search fashion? VisuAlgo: bitmask, recursion

This AY 2024/25, CNY does not affect CS3233 CNY Eve (Reunion Dinner): 28 Jan 2025 PM (Tue) Day 1: 29 Jan 2025 (Wed) Day 2: 30 Jan 2025 (Thu) 04 03 Feb Chapter 3, 4, 5, 6, 8, and 9; Focus on Section 3.5, 4.6.1, 5.4, 5.5, 5.8, 6.3, 8.3, 8.5, 8.6 (some NP-hard/complete problems with DP solution), 9.3, 9.7, and 9.29 Read Section 3.4 (Greedy) too HW03 due Solve Mini 02 B/C Kattis set #03 due Mini 03 Complete/Binary Search Money Contest donated by HRT The Art of Stenography (or Being Greedy)

Dynamic Programming; “Instant” review of CS3230/CS4234 DP Materials; Focus on relationship between DP and DAG; Discussion of a few non-classic DP examples; Formulating non trivial DP states + transitions; DP vs greedy algorithm comparisons on some problems VisuAlgo: bitmask, recursion

HRT class visit Mon, 03 Feb 2025, dinner provided from 4.30-5.25pm Assemble at COM1-Basement by 4.30pm (FCFS) 05 10 Feb Chapter 8 and 9; Focus on Section 8.4, 9.24, and 9.25; Optional: Read the Max-Flow material of CS4234

short HW04 due Solve Mini 03 B/C Kattis set #04 due Mini 04 DP or Greedy Money Contest Optiver How to Prevent Flood?

Quick overview of Network Flow; Quick review of Ford-Fulkerson Max Flow algorithm variants: Edmonds-Karp and especially Dinic’s (short comparison with Push-Relabel); Focus on Flow Graph Modeling skill and applications VisuAlgo: maxflow

Optiver class visit Mon, 10 Feb 2025, dinner provided from 4.30-5.25pm Assemble at COM1-Basement by 4.30pm (FCFS) 06 17 Feb Chapter 4 and 8; Focus on Section 4.6 (Bipartite Graph) and 8.5; Then read Section 9.26, 9.27, 9.28, 9.29; We postpone Graph Matching in special cases of NP-hard problems (8.6) to Week 09 HW05 due Solve Mini 04 B/C Kattis set #05 due Mini 05 Graph1: Network Flow Money Contest donated by Jane Street (PS: We do midterm team contest formation outside class time via class Discord after Mini 05 so that you can practice as a team over Wk6 and/or recess week)

Career Development Network, see Hall of Fame

Quick overview of Graph Matching; Unweighted MCBM; Greedy Bipartite Matching, Focus on (Bipartite) Graph Modeling skill and applications; Quick Discussion on Weighted MCBM (Kuhn-Munkres/Hungarian algorithm); Review of DP bitmask for Graph Matching (any variant, but on small graph) – (Edmonds’ Matching algorithm shelved) VisuAlgo: maxflow, matching

Jane Street class visit Mon, 17 Feb 2025, dinner provided from 4.30-5.25pm Assemble at COM1-Basement by 4.30pm (FCFS) Additionally, we will extend the class to 9.15pm tonight

Discover Citadel & Citadel Securities (Singapore) Fri, 21 Feb 2025 (by invitation only)

NOI 2025 Competition is this Sat, 22 Feb 2025 (online qualification contest, onsite for potential EGOI25 participants) Recess 24 Feb No class Kattis set #06, continued No class Although we are not supposed to have any face to face activity this week, nobody prevents you to keep solving Kattis problems (KS06 or more) ‘by yourself’ (or as a team of three) :). Again, peruse Prof Halim’s classification here, this time probably aiming for the 3-4+ pointer problems…

Prof Halim and his (international) organizing (host/judge/technical) team organized the second ICPC Asia Pacific Championship, 27 Feb-02 Mar 2025 It went well and NUS team Jägermeister clinched 2nd place (gold medal)

Decision to Drop CS3233/R with ‘W’ grade by Sun, 02 Mar 25 07 03 Mar Re-read Week 01-06 reading materials and CS1020/2040/C/S stuffs; Re-read “standard” CS2040/C/S graph topics by yourself (Section 4.1-4.6) Kattis set #06 due Week01-06 + CS2040/C/S 5.15-9.45pm (4.5h) Money Contest funded by NUS ICPC endowment No lecture, we do Midterm Team Contest VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp

Midterm Team Contest (recent 3 AYs only): Midterm Team Contest (28 Feb 22) Midterm Team Contest (27 Feb 23) Midterm Team Contest (04 Mar 24)

Our Midterm Team Contest (03 Mar 25) is on Kattis Starts at 5.15pm SGT, ends at 9.45pm SGT (4.5 hours) 08 10 Mar Chapter 8; Focus on the Section 8.6; Optional: Read the first 1/3 of CS4234 material HW06 (special) due HW07 due Solve Mini 05 B/C (upsolve some non AC Midterm Contest problems by yourself, optional) Kattis set #07 due Mini 06 Graph2: Matching Money Contest donated by Citadel | Citadel Securities Coping with (NP-)hard Problems

Summary of 2/3 of CS4234 - Optimisation Algorithms (except local search) in CS3233 style. VisuAlgo: mvc, steinertree, tsp 09 17 Mar Chapter 5 and 9; Focus on Section 5.3-5.6 + 9.36; Read the rest of Chapter 5 by yourself; Plus Section 9.9, 9.11, 9.15, 9.16, and 9.30

HW08 due Solve Mini 06 B/C Kattis set #08 due Mini 07 (NP-)hard Problems Money Contest donated by NUS ICPC endowment NUMB3RS

Mathematics overview with a movie; Focus on Python/Java Big Integer, Combinatorics, Number Theory (Extended Euclid, Modular Inverse, Fermat’s little theorem, Chinese Remainder Theorem), and a bit of Probability VisuAlgo: cyclefinding

NOI 2025 Competition is this Sat, 22 Mar 2025 (onsite final contest) 10 24 Mar Chapter 6; Focus on Section 6.6 + 9.45; Read the rest of Chapter 6 by yourself HW09 due Solve Mini 07 B/C Kattis set #09 due Mini 08 Mathematics Money Contest donated by Jump Trading (we will take a class photo #1)

A Glance at Bioinformatics

String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array; a bit of String Hashing VisuAlgo: suffixtree, suffixarray

Jump Trading class visit Mon, 24 Mar 2025 7.00-7.30pm + QnA during break time

Fri, 28 Mar 2025 is chosen as NUS well-being day S2 AY 2024/25 This is to link with Hari Raya Puasa PH next Monday

Also, NUS Online Teaching Feedback opens this Fri You can already start declaring your vote about this course 11 31 Mar No class Kattis set #10 due (automatic) No class No class Hari Raya Puasa Public Holiday 12 07 Apr Chapter 7; Focus on Section 7.2, 7.3, 9.5; Also Section 8.7 (problem decomposition) Read the rest of Chapter 7 by yourself HW10 due Solve Mini 08 B/C Kattis set #11 due Mini 09 String Money Contest donated by NUS ICPC endowment (final team contest formation are finalised via class Discord discussion) (we will then do a no-longer-optional CS3233 Final Online Quiz (7.20-7.30pm))

Inside Video Games

(Computational) Geometry; Focus on Algorithms on Points, Lines, a bit of 3D Geometry, and Polygon, Art Gallery Problem VisuAlgo: polygon, convexhull

(we will run a short last lecture to close the course and may extend beyond 9pm) The Last Lecture (8.50-9.15pm) 13 14 Apr The entire CP4 book 1+2 and beyond

Do not forget to give your official NUS Online Teaching Feedback after final team contest is over Solve Mini 09 B/C Kattis set #12 due Week01-12 stuffs 5.15-9.45pm (4.5h) Money Contest funded by NUS ICPC endowment

Join NUS ICPC team selection (~Late August 2025?) No lecture, we do Final Team Contest VisuAlgo (for self-review): maxflow, matching, mvc, steinertree, tsp, cyclefinding, suffixtree, suffixarray, polygon, convexhull

Final Team Contest (recent 3 AYs only): Final Team Contest (11 Apr 22) Final Team Contest (10 Apr 23) Final Team Contest (15 Apr 24)

Our Final Team Contest (14 Apr 25) is on Kattis Starts at 5.00pm SGT, ends at 10.00pm SGT (5 hours)

No final assessment, go and save your other courses after tonight

Good Friday and Easter Sunday this Week Hall of Fame This table records the previous top students of CS3233 under Prof Halim (rank 1 up to at most rank 3) of that Academic Year and their current known job* as per last contact with Prof Halim (or as indicated by their latest LinkedIn update).

AY (Iteration) Rank Flag and Name Best ICPC Record Job* 08/09 (1) 1 VNM Ngo Minh Duc WF 09 (HM) & 10 (HM) Addepar (US) 08/09 (1) 2 VNM Nguyen Hoanh Tien WF 09 (HM) & 10 (HM) Microsoft (US) 09/10 (2) 1 VNM Trinh Tuan Phuong WF 12 (HM) & 13 (joint-48) Quantcast (SG) 10/11 (3) 1 SGP Koh Zi Chun WF 12 (HM) Microsoft (US) 10/11 (3) 2 IDN Harta Wijaya WF 12 (HM) & 13 (joint-48) Meta (US) 11/12 (4) 1 CHN Yang Mansheng N/A DTL (SG) 12/13 (5) 1 VNM Nguyen Tan Sy Nguyen WF 13 (joint-48) & 16 (joint-14) Anduin (VN) 13/14 (6) 1 IDN Nathan Azaria WF 14 (joint-19) & 15 (joint-28) Roblox (US) 13/14 (6) 2 IDN Jonathan Irvin Gunawan WF 14 (joint-19) & 15 (joint-28) Meta (SG) 14/15 (7) 1 IDN Stefano Chiesa Suryanto Asia Singapore 15 (4th) Hearth (US) 14/15 (7) 2 VNM Vu Dinh Quang Dat WF 15 (joint-28) & 18 (joint-56) DTL (SG) 15/16 (8) 1 VNM Nguyen Quang Dung Asia Phuket+Singapore 15 (10th) [a private hedge fund] 15/16 (8) 2 VNM Truong Ngoc Khanh Asia Singapore 15 (20th) ByteDance (SG) 16/17 (9) TA/Exempted SGP Gan Wei Liang Asia Manila 17+Nakhon Pathom 18 (1st) Jump Trading (SG) 16/17 (9) 1 SGP Tan Jun An Asia Singapore 18 (16th) Google (SG) 16/17 (9) 2 IDN Agus Sentosa Hermawan WF 17 (joint-20) Glints 17/18 (10) TA/Exempted SGP Ranald Lam Yun Shao Asia Manila 17+Nakhon Pathom 18 (1st) Jump Trading (SG) 17/18 (10) 1 PHL Robin Christopher Cham Yu Asia Jakarta 18+20 (3rd) Sea Group (SG) 17/18 (10) 2 IDN Sergio Vieri Asia Jakarta 18+20 (3rd) Jane Street (HK) 17/18 (10) 3 SGP Bay Wei Heng WF 2019 (joint-62) & 20 (honor) Jane Street (HK) 18/19 (11) Exempted SGP Bernard Teo Zhi Yi WF 19 (joint-62) & 20 (honor) HRT (SG) 18/19 (11) Exempted SGP Lim Li WF 22 (joint-61) Stripe (SG) 18/19 (11) 1 VNM Nguyen Dinh Quang Minh WF 2018 (joint-14) & 2021 (HM) [a private hedge fund] 18/19 (11) 2 VNM Tran Tan Phat Asia Jakarta 19 (1st) [Graduated] 18/19 (11) 3 IDN Herbert Ilhan Tanujaya N/A Allium 19/20 (12) Exempted SGP Gabriel Goh Kheng Lin Asia Jakarta 20 (3rd) [Graduated] 19/20 (12) 1 VNM Vuong Hoang Long WF 21 (HM) Pendle Finance (SG) 20/21 (13) Exempted SGP Zhang Guangxuan WF 21 (HM) Jane Street (HK) 20/21 (13) Exempted SGP Clarence Chew Xuan Da Asia Jakarta 20 (3rd) NUS PhD student 20/21 (13) 1 PHL Dan Alden Varsobia Baterisna Asia Jakarta 23 (4th) NUS SoC Research Assistant 21/22 (14) Exempted SGP Huang Xing Chen Asia Ho Chi Minh City 22 (3rd) 4th year UG 21/22 (14) Joint-1 IDN Rama Aryasuta Pangestu AP 24 (2nd); WF 24 (Silver) 4th year UG, joining Jump Trading (SG) soon 21/22 (14) Joint-1 VNM Bui Hong Duc AP 24 (2nd); WF 21 (Bronze) & 24 (Silver) DRW (SG) 21/22 (14) 3 MNG Nyamdavaa Amar AP 24 (2nd); WF 24 (Silver) Tower Research Capital (UK) 22/23 (15) Exempted SGP Jeffrey Lee Chun Hean WF 23 (HM) 3rd year UG, Jane Street Intern (HK) 22/23 (15) Exempted SGP Teow Hua Jun Asia Hanoi 2024 (2nd) 3rd year UG, Jump Trading Intern (SG) 22/23 (15) 1 HKG Yeung Man Tsung Asia Jakarta 23 (12th) 3rd year UG, Jump Trading Intern (SG) 22/23 (15) 2 SGP Tan Chee Heng Asia Jakarta 23 (12th) 4th year UG 23/24 (16) 1 VNM Nguyen Cao Duy N/A 2nd year UG 23/24 (16) 2 JPN Watanabe Yuto ICPC Jak23+24 (2nd); AP 25 (2nd) 2nd year UG 23/24 (16) 3 VNM Nguyen Nhat Minh WF 23 (HM) 2nd year UG 24/25 (17) Exempted SGP Tan Yi Kai Asia Jakarta 24 (4th) 1st year UG 24/25 (17) Exempted SGP Shen Zihan Asia Jakarta 24 (4th) 1st year UG 24/25 (17) Exempted SGP Lim Rui Yuan N/A 1st year UG 24/25 (17) 1 ??? One of you?? ??? ??? year UG 24/25 (17) 2 ??? Another one of you?? ??? ??? year UG 24/25 (17) 3 ??? Yet another one of you?? ??? ??? year UG Scoring Scheme for CS3233 S2 AY 2024/25 There are two big scoring components: SP(eed) (from live contests, up to 50%) and DI(ligence) (from non-speed-related stuffs, up to 50%). IMPORTANT change for S2 AY 2024/25 onwards: each component is now capped at 50%, i.e., one cannot just be very speedy (gets 57% from SP component but then gets a bit lazy) or just be very diligent (gets 57% from DI component but actually not that good during contests). The theoretical max is 100%, with just 60% needed to secure at least a B+ grade in this extremely competitive course. The SP(eed) component is further divided into two sub-components: M(ini)C(ontest) (up to 36%) and T(eam)C(ontest) (up to 22%). The DI(ligence) component is further divided into four sub-components: H(ome)W(ork) (up to 15%), (Problem)Bs (up to 10%), K(attis)S(ets) (up to 12%), and Ac(hievements) (up to 20%).

MC = Weekly Mini Contest (36%) 9 Weekly Mini Contests, three problems in 75 minutes, using https://cs3233.com. (9 weeks x (3%+0.5%+0.5%)/week = 36%).

very easy/easy/warm-up/1-2 simple CP technique(s): 1%. medium/last week material, 2%; may have weakened subtask for 1%. usually very hard and from topics not specifically taught in class (or taught in latter part of the class – suitable for senior students only), for CS3233R students, bonus 0.5% for CS3233/R students who can get this AC in contest time. Occasionally (if Prof Halim is not that lazy), we may open problem D (or even E) which is (are) the easier form of problem B/C. We give bonus 0.5% for top 3 in each mini contest. We use strict binary grading (Accepted or not Accepted: Wrong Answer, Time Limit, Memory Limit, Runtime Error, etc) for our contests.

Two Team Contests (21%) 1 Midterm Team Contest (10%+0.5%=10.5%, 10 “original” problems, worth 1.0% each). 1 Final Team Contest (10%+0.5%=10.5%, 10 “original” problems, worth 1.0% each). Bonus 0.5% for top 3 teams in both team contests. Team size is three students. If the class size is not divisible by 3, the last team can have 4 or 5 members.

Weekly Homework (15%) 10 Weekly Homework (10 weeks * 1.5%/week = 15%). CP4 book 1+2 review + solve certain written exercises, 1.5%. Scoring scheme: 0% = no submission, 0.5% = poor, 1% = default score, 1.5% superb.

Problem Bs (10%) Solve problem B of last week’s mini contest at home, on your own pace, by next Mon 05.30pm, if you fail to solve it during the live Mini Contest. Simply submit your code to cs3233.com, TA will check your last submission.

Scoring scheme: 0% = not AC in the actual mini contest and not attempted after one more week. 1% = managed to solve problem B during mini contest itself or within one more week afterwards. There is no additional marks for solving problem C at home (for non-CS3233R students).

Kattis Set (12%) Prof Halim selects seven targeted Kattis problems related to CS3233 topic of that week (Prof Halim had solved six of them before with one problem that he has not solved before). To get 1% per week, student has to solve at least three (of any preferred difficulty level as indicated in Kattis) of the selected problems within the stipulated deadline (Monday night 09:00pm SGT of that week until Monday 05:30pm SGT of the following week). Note that Prof Halim can see all CS3233 class submissions at nus.kattis!

Please check the details of the 12 Kattis Sets at NUS@Kattis for this semester.

Achievement System of CS3233 (20%) One star = 1%, most achievements are manual entry:

**** Active in class: Subjective title for students who participated well during various class activities (answering in-lecture questions, asking/answering questions in real life or in our Discord server, consultations (with Prof Halim/TAs on Mon 4.00-5.15pm), active in Kattis, etc), awarded by Prof Halim/TAs throughout the semester (max claim: 4 times/student). *** Surprise us: Managed to surprise the teaching staffs by giving a better/more elegant solution/pinpoint bug in lecture, etc anytime during the semester (max claim: 3 times/student).

High determination: Objective title for students who always diligently solve (AC) problem B of all 10 weekly contests (inclusive of problem B of the Mock contest), be it during contest time or as homework assignment. This achievement will be auto updated by this system at the end of the semester. ** Bookworm: Subjective title for students who diligently study and review CP4 book 1+2 by the end of Week12 (at least 10*1.5% - 0.5% = 14.5% score, i.e., at most one 1.0 with the rest 1.5). This achievement will be manually updated at the end of the semester. The two ** will only be given to the top 3 CP4 book reviewers in the semester. ***** Kattis apprentice: Obtaining ≥ 5000 Kattis points (5% — it is not impossible, e.g., Nicholas Russell Saerang (10.6K), marc-phua (9.7K), matthewng — hidden (9.2K), Artemis Ngoh (6.3K), Nicholas Foo Chuan le (6K), and bayweiheng (5.9K))/100 (3% — appear at ranklist page — there are ~13 NUS staff/students here)/200 (2%)/400 (1%) of Kattis ranklist by Sat, 10 May 2025, 23:59 (this achievement will NOT be updated instantly as this will keep changing every week). ***** CodeForces specialist: Given to student who also join CodeForces contests and attain (max) rating of at least 3000 (Red color) (5%)/2400 (Red color) (4%)/2100 (Orange color) (3%)/1900 (Purple color) (2%)/1600 (Blue color) (1%) by Sat, 10 May 2025, 23:59 (this achievement will NOT be updated instantly as this will keep changing every week).

这门课讲了什么？

Cursor

这门课是新加坡国立大学（NUS）开设的CS3233 - Competitive Programming，中文可以译为“竞赛编程”。它是面向本科生和部分优秀中学生的高强度算法竞赛训练课程，由著名的算法竞赛教练 Steven Halim 教授主讲。

课程目标

提升学生在算法竞赛中的实战能力，为参加 ICPC、IOI 等国际/国家级编程竞赛做准备。
帮助学生在顶级 IT 公司技术面试中脱颖而出。
系统学习并应用高级算法与数据结构，解决具有挑战性的计算问题。

主要内容

课程内容覆盖了算法竞赛中常见的所有核心算法与技巧，包括但不限于：

基础算法与技巧
- 完全搜索（Bruteforce/Complete Search）
- 分治、递归、变换与征服（Divide/Reduce/Transform and Conquer）
- 贪心算法（Greedy）
- 动态规划（Dynamic Programming, DP）
专题算法
- 图论（Graph Algorithms）：最短路、网络流、图匹配、最小生成树等
- 数学相关（Mathematics）：数论、组合数学、概率、模运算等
- 字符串处理（String Processing）：KMP、Z-Algorithm、后缀数组/树、哈希等
- 计算几何（Computational Geometry）：点、线、多边形、凸包等
高级与实战技巧
- 状态压缩、位运算、二分答案、Meet in the Middle
- 高级数据结构：线段树、树状数组、并查集等
- 优化算法：网络流、最大匹配、NP-hard 问题的近似与启发式解法
- 竞赛常用编程语言库（C++ STL、Python 标准库、Java API）
实战训练
- 每周小型竞赛（Mini Contest）
- 团队赛（Team Contest）
- Kattis 平台刷题
- 书面作业与经典题目讲解
- 期中/期末团队赛

课程特色

难度极高，适合有竞赛基础的同学（如 NOI/ICPC/Codeforces/Leetcode 高分选手）。
实战为主，每周都有竞赛和作业，强调速度和正确率。
与业界顶级公司深度合作，有机会直接与 Jane Street、HRT、Jump Trading、Optiver、Citadel、华为等公司 HR 交流。
多语言要求，主要用 C++，也支持 Python 和 Java。
成就系统，鼓励刷题、参与竞赛、活跃课堂、获得高分等。

适合人群

有志于参加算法竞赛（ICPC、IOI、NOI等）的学生
想要系统提升算法与编程能力、冲击顶级 IT 公司技术岗的同学
已有一定算法基础，能熟练使用 C++/Python/Java 编程

课程评价

课程难度极高，平均分很高的同学才容易拿高分
课程内容极其丰富，涵盖了算法竞赛的全部精华
课程氛围紧张刺激，适合喜欢挑战的同学

总结一句话

CS3233 是一门专为算法竞赛和顶级 IT 公司面试准备的高强度算法实战课程，内容涵盖所有主流算法与数据结构，强调实战与速度，是 NUS 乃至亚洲最顶尖的竞赛编程课程之一。

如果你想了解具体某一周的内容、作业、竞赛题目或讲义，可以告诉我！