CS3233 - Competitive Programming

Introduction

This module aims to prepare students in competitive problem solving.

It will benefit NUS students who want to compete in ICPC, invited high school students (likely only for (online) midterm/final team contests only) 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 (2023++) ICPC donors: Sea Group, Optiver, HRT, Jump Trading, and Citadel | Citadel Securities (one more donor is still in negotiation as of 13 January 2023).

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

UPDATE ON 29 NOV 2022: The quota of this class (S2 AY 2022/23) is ... technically only limited by the ORIGINAL size of COM1-B-PL2 = 46 fast-enough 2018 Acer Nitro Laptops... but not that many NUS students are eligible (or dare enough) to take this extremely competitive module. In 14 academic years of CS3233 classes, on average only ~19 NUS students were enrolled per year and only a few (16 out of 270) are female...

UPDATE ON 11 DEC 2022: There are 37 official + 2 admin = 39 students (class record?..., and the theoretical limit of a 'small module').
Therefore, the registration is now closed.

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

  1. Do you have national (but preferably international) programming competition background before? Examples: NOI (or IDN OSN, VNM VNOI, CHN NOIP, MYS MCO, PHL NOI, IND ICO, etc), IOI (especially the recent IOI 2022 or IOI 2021 (Online Competition)), ICPC (especially the recent ICPC Asia Ho Chi Minh City 2022 or ICPC Asia Singapore Regional Contest 2018), Google Code Jam, Facebook Hacker Cup, CodeForces rated rounds, Topcoder Open, 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...

  2. 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 module has a very high performance bar and the average CAP of the students enrolled in the past academic years excluding recent AYs (cannot track anymore since AY 2019/20 onwards) were 4.57 , 4.78 (remember, year 1 nowadays have much more S/U options) , 4.3+ (not tracked, I didn't survey that AY) , 4.33, 4.44, 4.43, 4.45, and 4.30 (out of 5.00), respectively. You will need special permission from the instructor (Dr Steven Halim) if you do not satisfy the pre-requisites listed above (the filter is there for your own good).

  3. Are you OK to be tortured for one semester for a mere 4 modular credits (your other modules may also suffer)?

    You may have to take lighter set of other modules or be ready to S/U other modules or to rush course project submissions (for project-based modules 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 modules only during study week (no final assessment for CS3233). Please do NOT take CS3233 module with another module that is known to be challenging/demanding (e.g., the 5 MC 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 module before applying, read their public stories, e.g., Lim Jay Ching (exchange from University of Waterloo), or read several NUSWhispers related posts about CS3233!

  4. Are you thinking on applying to top (or emerging) IT companies like NUS current (2022/23; list to be refreshed by January 2023) ICPC donors: Sea Group, Optiver, HRT, Jump Trading, Citadel | Citadel Securities; or other large IT companies like Google, Meta (Facebook), Microsoft, 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...

  5. 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 S2 AY 2022/23 (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.

  6. 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?

    (Senior) Lecturer: Dr Steven Halim, current Singapore IOI team leader, Deputy Director for IOI 2020 and IOI 2021 in Singapore (online competitions), NUS ICPC coach (5x ICPC World Finals Coach Award), ICPC Asia Singapore Regional Contest Director (2015 and 2018), the author of Competitive Programming text book (the official text book of this module, we will use CP4 Book 1 and Book 2).

    Rating (out of 5.0, SoC avg ~4.2) Jan-Apr 2023 (n=39?) Jan-Apr 2022 (n=28) Jan-Apr 2021 (n=18) Jan-Apr 2020 (n=12) Jan-Apr 2019 (n=22) Jan-Apr 2018 (n=21)
    Module feedback Target ≥ 4.5 4.7 4.8 4.9 (PB) 4.6 4.8 ==
    Module difficulty Target ≤ 4.2 4.3 == 4.3 4.2 4.3 4.1
    Steven's teaching Target ≥ 4.5 4.8 4.9 (PB) == 4.9 (PB) 4.5 4.8 ==

    Qualified Teaching Assistant:

    1. Rama Aryasuta Pangestu, CS3233 joint-winner S2 AY 2021/22
    2. Bui Hong Duc, CS3233 joint-winner S2 AY 2021/22, ICPC World Finals 2021 Bronze Medalist
    3. [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.

  7. 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:

    1. 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)
    2. 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)
    3. 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
    4. 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){...}
    5. Using autos everywhere and let the compiler do the variable type deduction work, e.g., for (auto& [v,w]:AL[u]){...}
    6. 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?)
    7. No function other than int main() unless you need to write a recursive function (your compiler just need this to run your code!)
    8. 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);
    9. 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)
    10. 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...
    11. 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
    12. 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
    13. 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;
    14. Use bitmask operations whenever possible, e.g., printf("%d\n", __builtin_popcount(m));
    15. 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>
    16. 'Hack' C++ STL defaults to suit our needs, e.g., inserting negated input integers into priority_queue<int> pq; to make it into a Min-PQ instead of default Max-PQ (instead of definining our own comparison function)
    17. 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)
    18. On some rare occassions, we use the 'forbidden' goto statement...
    19. Using C++ operator shortcuts as far as possible, e.g., ++i; i*=2; i%=7;
    20. using namespace std (as there is no other namespace to consider in a short C++ program)
    21. And many scary stuffs that are hated by SE purists, e.g., fellow SE professors in SoC Prof Ben, Prof Damith, et al...

    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 notify Steven 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 31 39 accepted NUS students (Steven plans to reserve 46-39-2 CS3233R = 5 slots for guest/high school students and also to prevent this class from no-longer being classified as a 'small' class (< 40 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 Steven that the applicant can score at least 500.0 Kattis points by Saturday, 31 December 2022, 23.59.

PS: For S2 AY 2023/24, most likely Steven will set similar at least 500.0 Kattis points by Saturday, 31 December 2023, 23.59 but will add ONE MORE IMPORTANT CONSTRAINT: must have at least CodeForces rating of ≥ 1000 rating (this is a more accurate predictor of potential CS3233 grade).

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

News

Date News

Class Ranklist for S2 AY 2022/23

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)
Past classes more than one week ago are hidden so that we can focus on the current and future classes, but you can restore them by clicking 'Show Past' button above
-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, 02 Jan 2023, 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) Kattis account (open), solve first few easy ≤ 3.0 pointer problems @ Kattis, then use Dec22+early Jan23 holiday (~3-4 weeks) to get ≥ 500.0 points (~250 AC of ~2 pointer problems (first ~3+ pages sorted based on Kattis difficulty ratings :O), use Steven's classification here) in Kattis by Sat, 31 Dec 22, 23:59 (or earlier) to ensure module acceptance, familiarize yourself with Ubuntu 20 LTS with GNOME desktop, or self-read the older teaching materials in this public website
01
09 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
16 Jan
Chapter 2; Focus on Section 2.2 and 2.4.3
Read the rest of Chapter 2 by yourself

Decision to Drop CS3233/R without penalty by Fri, 20 Jan 23 (email UG office for manual drop, cc to Dr Steven Halim; avoid weekend; for this year 2023, the class selection has been made very rigorous and Steven has decided to be stricter in students selection in order to have 'no-one-drop-by-week-02' again)
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
sponsored by
NUS ICPC
endowment fund

Be A Librarian

Mastery of Libraries (C++ STL, Python Standard Library, & Java API); Focus on Bit Manipulation and Binary Indexed (Fenwick) Tree
VisuAlgo: bitmask, fenwicktree, and segmenttree (optional)
03
23 Jan
CNY Reunion Dinner on Sat, 21 Jan
CNY Day 1 on Sun, 22 Jan
CNY Day 2 on Mon, 23 Jan
Tue, 24 Jan is also a PH
CS3233 class this week is canceled
[recharge our batteries here...]
[and Steven is also not in Singapore]
Kattis set #02 is still due on CNY Day 2!
N/A N/A
04
30 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 #03 due
Mini 02
Libraries
Dinner 4.30-5.30pm
plus
Money Contest
sponsored by
HRT

(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
05
06 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 #04 due
Mini 03
Complete/Binary Search
Money Contest
sponsored by
[ICPC donor, TBC]

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
06
13 Feb
Chapter 8 and 9; Focus on Section 8.4, 9.24, and 9.25; Optional: Read the Max-Flow material of CS4234

Valentine's Day on Tue, 14 Feb 2023

NOI 2023 Competition is this Sat, 18 Feb 2023 (TBC)
(online qualification contest)
HW04 due
Solve Mini 03 B/C
Kattis set #05 due
Mini 04
DP or Greedy
Money Contest
sponsored by
Optiver

(PS: We will do midterm team contest formation after Mini 04 so that you can practice as a team over Wk6 and/or recess week)

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
Recess
20 Feb
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 Steven's classification here, this time probably aiming for the 3-4+ pointer problems...

Decision to Drop CS3233/R with 'W' grade by Sun, 26 Feb 23
Kattis set #06, continued
No class
No class
07
27 Feb
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)
HW05 due
Solve Mini 04 B/C
Kattis set #06 due
Week01-06 + CS2040/C/S
5.30-9.30pm (4h)
Money Contest
sponsored by
[ICPC donor, TBC]

Starts at 5.30pm SGT, ends at 9.30pm SGT (4 hours)

No lecture, we will do Midterm Team Contest
VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp

This Midterm Team Contest is on Kattis
08
06 Mar
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
HW06 due
(upsolve some non AC Midterm Contest problems by yourself, optional)
Kattis set #07 due
Mini 05
Graph1
Network Flow
Money Contest
sponsored by
[ICPC donor, TBC]

Social Development Network

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
09
13 Mar
Chapter 8; Focus on the Section 8.6; Optional: Read the first 1/3 of CS4234 material

NOI 2023 Competition is this Sat, 18 Mar 2023 (TBC)
(onsite for all again... like in 2019? TBC...)
HW07 due
Solve Mini 05 B/C
Kattis set #08 due
Mini 06
Graph2
Matching
Money Contest
sponsored by
Optiver

Coping with (NP-)hard Problems

Summary of 2/3 of CS4234 - Optimisation Algorithms (except local search) in CS3233 style.
VisuAlgo: mvc, steinertree, tsp
10
20 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 #09 due
Mini 07
(NP-)hard Problems
Money Contest
sponsored by
[ICPC donor, TBC]

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
11
27 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 #10 due
Mini 08
Mathematics
Money Contest
sponsored by
[ICPC donor, TBC]

(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
12
03 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

Good Friday and Easter Sunday this Week
HW10 due
Solve Mini 08 B/C
Kattis set #11 due
Mini 09
String
Money Contest
sponsored by
[ICPC donor, TBC]

(we will do final team contest formation after Mini 09 so that you can practice as a team briefly)
(we will take another class photo #2 if #1 was not that good)

Inside Video Games

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

(Steven will run a short last lecture to close the module and may extend beyond 9pm)
The Last Lecture (8.45-9.15pm)

Thu, 06 Apr 2023 is chosen as
NUS well being day S2 AY 2022/23
This is just before Fri, 07 Apr 2023 Good Friday PH
CS3233 class is not affected
(in fact, you may want to use the long weekend
for final team contest preparation)
13
10 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.30-9.30pm (4h)
Money Contest
sponsored by
[ICPC donor, TBC]


Join NUS ICPC team selection
(~Early? September? 2023)
Starts at 5.30pm SGT, ends at 9.30pm SGT (4 hours)

No lecture, we will do Final Team Contest

This Final Team Contest will be on Kattis
No final assessment, go and save your other modules after tonight
(PS: esp if you have submitted HW05)

Hall of Fame

This table records the previous top students of CS3233 under Dr Steven Halim (rank 1 up to at most rank 3) of that Academic Year and their current known affiliation as per last contact with Dr Steven Halim.

AY (Iteration) Rank Flag and Name Best ICPC Record Current Job
08/09 (1) 1 VNM Ngo Minh Duc World Finalist 2009 (HM) & 2010 (HM) Addepar (US)
08/09 (1) 2 VNM Nguyen Hoanh Tien World Finalist 2009 (HM) & 2010 (HM) Microsoft (US)
09/10 (2) 1 VNM Trinh Tuan Phuong World Finalist 2012 (HM) & 2013 (joint-48) Quantcast (SG)
10/11 (3) 1 SGP Koh Zi Chun World Finalist 2012 (HM) Microsoft (US)
10/11 (3) 2 IDN Harta Wijaya World Finalist 2012 (HM) & 2013 (joint-48) Facebook (US)
11/12 (4) 1 CHN Yang Mansheng N/A Dynamic Technology Lab (SG)
12/13 (5) 1 VNM Nguyen Tan Sy Nguyen World Finalist 2013 (joint-48) & 2016 (joint-14) Anduin Transactions (VN)
13/14 (6) 1 IDN Nathan Azaria World Finalist 2014 (joint-19) & 2015 (joint-28) Facebook (US)
13/14 (6) 2 IDN Jonathan Irvin Gunawan World Finalist 2014 (joint-19) & 2015 (joint-28) Jump Trading (SG)
14/15 (7) 1 IDN Stefano Chiesa Suryanto Fourth place in ICPC Asia Singapore 2015 Improbable (UK)
14/15 (7) 2 VNM Vu Dinh Quang Dat World Finalist 2015 (joint-28) & 2018 (joint-56) Dynamic Technology Lab (SG)
15/16 (8) 1 VNM Nguyen Quang Dung Tenth place in ICPC Asia Phuket+Singapore 2015 Graduated
15/16 (8) 2 VNM Truong Ngoc Khanh Twentieth place in ICPC Asia Singapore 2015 Sea Group (SG)
16/17 (9) TA/Exempted SGP Gan Wei Liang Champion in ICPC Asia Manila 2017+Nakhon Pathom 2018 Jump Trading (SG)
16/17 (9) 1 SGP Tan Jun An Sixteenth place in ICPC Asia Singapore 2018 Google (SG)
16/17 (9) 2 IDN Agus Sentosa Hermawan World Finalist 2017 (joint-20) Sirclo (ID)
17/18 (10) TA/Exempted SGP Ranald Lam Yun Shao Champion in ICPC Asia Manila 2017+Nakhon Pathom 2018 Jump Trading (SG)
17/18 (10) 1 PHL Robin Christopher Cham Yu Third place in Regional Asia Jakarta 2018+2020 Sea Group (SG)
17/18 (10) 2 IDN Sergio Vieri Third place in Regional Asia Jakarta 2018+2020 Google (SG)
17/18 (10) 3 SGP Bay Wei Heng World Finalist 2019 (joint-62) & 2020 (invitational contest - honor) Jane Street
18/19 (11) Exempted SGP Bernard Teo Zhi Yi World Finalist 2019 (joint-62) & 2020 (invitational contest - honor) Hudson River Trading
18/19 (11) Exempted SGP Lim Li World Finalist 2022 (Nov 2023) Stripe
18/19 (11) 1 VNM Nguyen Dinh Quang Minh World Finalist 2018 (joint-14) & 2021 (6-11 Nov 2022) 5th year UG
18/19 (11) 2 VNM Tran Tan Phat Champion in ICPC Asia Jakarta 2019 Graduated
18/19 (11) 3 IDN Herbert Ilhan Tanujaya N/A Momos.io
19/20 (12) Exempted SGP Gabriel Goh Kheng Lin Third place in ICPC Asia Jakarta 2020 4th year UG
19/20 (12) 1 VNM Vuong Hoang Long World Finalist 2021 (6-11 Nov 2022) 4th year UG
20/21 (13) Exempted SGP Zhang Guangxuan World Finalist 2021 (6-11 Nov 2022) 3rd year UG
20/21 (13) Exempted SGP Clarence Chew Xuan Da Third place in ICPC Asia Jakarta 2020 3rd year UG
20/21 (13) 1 PHL Dan Alden Varsobia Baterisna Tenth place in ICPC Asia Ho Chi Minh City 2022 3rd year UG
21/22 (14) Exempted SGP Huang Xing Chen Third place in ICPC Asia Ho Chi Minh City 2022 2nd year UG
21/22 (14) Joint-1 IDN Rama Aryasuta Pangestu Second place in ICPC Asia Jakarta 2021 2nd year UG
21/22 (14) Joint-1 VNM Bui Hong Duc World Finalist 2021 Bronze Medallist 2nd year UG
21/22 (14) 3 MNG Nyamdavaa Amar World Finalist 2023 (Nov 2023, 99%) 2nd year UG
22/23 (15) Exempted SGP Jeffrey Lee Chun Hean World Finalist 2023 (Nov 2023, 99%) 1st year UG
22/23 (15) Exempted SGP Teow Hua Jun Nineteenth place in ICPC Asia Ho Chi Minh City 2022 1st year UG

Scoring Scheme for CS3233 S2 AY 2022/23

There are two big scoring components: SP(eed) (from live contests, up to 57%) and DI(ligence) (from non-speed-related stuffs, up to 57%).
The theoretical max is therefore 114%, with just 60% needed to secure at least a B+ grade in this extremely competitive module.
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 (new system) or fallback to Mooshak (old system).
(9 weeks x (3%+0.5%+0.5%)/week = 36%).

  1. very easy/easy/warm-up/1-2 simple CP technique(s): 1%.
  2. medium/last week material, 2%; may have weakened subtask for 1%.
  3. 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 Steven 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 + update the lecturer, 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.15pm (closed by the time TA consultation hour is over), if you fail to solve it during the live Mini Contest. Simply submit your code to cs3233.com (or to Mooshak), 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 before deadline.
There is no additional marks for solving problem C at home (for CS3233R students).


Kattis Set (12%)

We use NUS@Kattis for this semester.

Steven selects eight targeted Kattis problems related to CS3233 topic of that week (steven has solved seven 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 Steven can see all CS3233 class submissions at nus.kattis!

  • Set #00, Competitive Programming Preview (not graded)
  • Set #01, Ad Hoc
  • Set #02, CNY period: CS2040/C/S++ Basic Graph Review (Graph Traversal, MST, SSSP, APSP, Special Graphs)
  • Set #03, Data Structures and Libraries
  • Set #04, Complete Search and easier BSTA+Other
  • Set #05, Dynamic Programming
  • NUS recess week (nothing is due this week)
  • Set #06, Greedy and Network Flow
  • Set #07, Easier Mathematics
  • Set #08, Graph Matching and Miscellaneous 1
  • Set #09, NP-hard Problems and harder BSTA+Other
  • Set #10, Harder Mathematics
  • Set #11, String Processing
  • Set #12, Computational Geometry and Miscellaneous 2

Achievement System of CS3233 (20%)

One star = 1%, most achievements are manual entry:

  1. ***** 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 Steven/TAs on Mon 4.00-5.15pm), active in Kattis, etc), awarded by Steven/TAs throughout the semester (max claim: 5 times/student).
  2. *** 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).
  3. * 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.
  4. ** 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.
  5. **** Kattis apprentice: Obtaining ≥ 5000 Kattis points (4% — it is not impossible, e.g., marc-phua — hidden (9.8K), matthewng — hidden (9.2K), bayweiheng (5.6K), and Nicholas Foo Chuan le (5.4K))/100 (3% — appear at ranklist page — there are ~16 NUS staff/students here)/200 (2%)/400 (1%) of Kattis ranklist by Sat, 06 May 2023, 23:59 (this achievement will NOT be updated instantly as this will keep changing every week).
  6. ***** 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, 06 May 2023, 23:59 (this achievement will NOT be updated instantly as this will keep changing every week).