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:

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

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

3. 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).

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

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 (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?
   

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

   1. Teow Hua Jun, IOI Bronze Medallist
   2. Yeung Man Tsung, CS3233 winner S2 AY 2022/23, IOI Silver Medallist
   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
   
   

   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 Show All

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 Hide Past Show Past

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	Ngo Minh Duc	WF 09 (HM) & 10 (HM)	Addepar (US)
08/09 (1)	2	Nguyen Hoanh Tien	WF 09 (HM) & 10 (HM)	Microsoft (US)
09/10 (2)	1	Trinh Tuan Phuong	WF 12 (HM) & 13 (joint-48)	Quantcast (SG)
10/11 (3)	1	Koh Zi Chun	WF 12 (HM)	Microsoft (US)
10/11 (3)	2	Harta Wijaya	WF 12 (HM) & 13 (joint-48)	Meta (US)
11/12 (4)	1	Yang Mansheng	N/A	DTL (SG)
12/13 (5)	1	Nguyen Tan Sy Nguyen	WF 13 (joint-48) & 16 (joint-14)	Anduin (VN)
13/14 (6)	1	Nathan Azaria	WF 14 (joint-19) & 15 (joint-28)	Roblox (US)
13/14 (6)	2	Jonathan Irvin Gunawan	WF 14 (joint-19) & 15 (joint-28)	Meta (SG)
14/15 (7)	1	Stefano Chiesa Suryanto	Asia Singapore 15 (4th)	Hearth (US)
14/15 (7)	2	Vu Dinh Quang Dat	WF 15 (joint-28) & 18 (joint-56)	DTL (SG)
15/16 (8)	1	Nguyen Quang Dung	Asia Phuket+Singapore 15 (10th)	[a private hedge fund]
15/16 (8)	2	Truong Ngoc Khanh	Asia Singapore 15 (20th)	ByteDance (SG)
16/17 (9)	TA/Exempted	Gan Wei Liang	Asia Manila 17+Nakhon Pathom 18 (1st)	Jump Trading (SG)
16/17 (9)	1	Tan Jun An	Asia Singapore 18 (16th)	Google (SG)
16/17 (9)	2	Agus Sentosa Hermawan	WF 17 (joint-20)	Glints
17/18 (10)	TA/Exempted	Ranald Lam Yun Shao	Asia Manila 17+Nakhon Pathom 18 (1st)	Jump Trading (SG)
17/18 (10)	1	Robin Christopher Cham Yu	Asia Jakarta 18+20 (3rd)	Sea Group (SG)
17/18 (10)	2	Sergio Vieri	Asia Jakarta 18+20 (3rd)	Jane Street (HK)
17/18 (10)	3	Bay Wei Heng	WF 2019 (joint-62) & 20 (honor)	Jane Street (HK)
18/19 (11)	Exempted	Bernard Teo Zhi Yi	WF 19 (joint-62) & 20 (honor)	HRT (SG)
18/19 (11)	Exempted	Lim Li	WF 22 (joint-61)	Stripe (SG)
18/19 (11)	1	Nguyen Dinh Quang Minh	WF 2018 (joint-14) & 2021 (HM)	[a private hedge fund]
18/19 (11)	2	Tran Tan Phat	Asia Jakarta 19 (1st)	[Graduated]
18/19 (11)	3	Herbert Ilhan Tanujaya	N/A	Allium
19/20 (12)	Exempted	Gabriel Goh Kheng Lin	Asia Jakarta 20 (3rd)	[Graduated]
19/20 (12)	1	Vuong Hoang Long	WF 21 (HM)	Pendle Finance (SG)
20/21 (13)	Exempted	Zhang Guangxuan	WF 21 (HM)	Jane Street (HK)
20/21 (13)	Exempted	Clarence Chew Xuan Da	Asia Jakarta 20 (3rd)	NUS PhD student
20/21 (13)	1	Dan Alden Varsobia Baterisna	Asia Jakarta 23 (4th)	NUS SoC Research Assistant
21/22 (14)	Exempted	Huang Xing Chen	Asia Ho Chi Minh City 22 (3rd)	4th year UG
21/22 (14)	Joint-1	Rama Aryasuta Pangestu	AP 24 (2nd); WF 24 (Silver)	4th year UG, joining Jump Trading (SG) soon
21/22 (14)	Joint-1	Bui Hong Duc	AP 24 (2nd); WF 21 (Bronze) & 24 (Silver)	DRW (SG)
21/22 (14)	3	Nyamdavaa Amar	AP 24 (2nd); WF 24 (Silver)	Tower Research Capital (UK)
22/23 (15)	Exempted	Jeffrey Lee Chun Hean	WF 23 (HM)	3rd year UG, Jane Street Intern (HK)
22/23 (15)	Exempted	Teow Hua Jun	Asia Hanoi 2024 (2nd)	3rd year UG, Jump Trading Intern (SG)
22/23 (15)	1	Yeung Man Tsung	Asia Jakarta 23 (12th)	3rd year UG, Jump Trading Intern (SG)
22/23 (15)	2	Tan Chee Heng	Asia Jakarta 23 (12th)	4th year UG
23/24 (16)	1	Nguyen Cao Duy	N/A	2nd year UG
23/24 (16)	2	Watanabe Yuto	ICPC Jak23+24 (2nd); AP 25 (2nd)	2nd year UG
23/24 (16)	3	Nguyen Nhat Minh	WF 23 (HM)	2nd year UG
24/25 (17)	Exempted	Tan Yi Kai	Asia Jakarta 25 (4th)	1st year UG
24/25 (17)	Exempted	Shen Zihan	Asia Jakarta 25 (4th)	1st year UG
24/25 (17)	Exempted	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%).