CS3233 - Competitive Programming


This module aims to prepare students in competitive problem solving.

It will benefit NUS students who want to compete in ACM ICPC, invited high school students 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.

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 (Sem 2 AY2017/18) is ... technically only limited by the size of COM1-B-PL2 (46 PCs) ... but not that many NUS students are eligible (or dare enough) to take this extremely competitive module. In recent years, only ~20 NUS students were enrolled and only a few (8 out of 170) are female...

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, ACM ICPC(especially ACM ICPC Asia Singapore Regional Contest 2015/2018), Google Code Jam, Topcoder Open, Facebook Hacker Cup, 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 CS2010/CS2040/C or equivalent (and preferably score A+ in all CS1101S+CS2020 (senior batch) or CS1010+CS1020+CS2010 (senior batch) or CS1010/CS1101S+CS2030+CS2040 (current batch))?

    This module has a very high performance bar and the average CAP of the students enrolled in the current and the past six academic years were 4.78 (remember, year 1 nowadays have much more S/U options) , 4.3+ (not tracked) , 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) 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 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 2018 trainees (Sec2-JC2 students) beat you in (many) CS3233 contests. Read this nice module review by a senior: Benedict Suratanakavikul. Bottom line: Try to ask CS3233 seniors who have taken (and survived) this module before applying!

  4. Are you thinking on applying to top (or emerging) IT companies like NUS ACM ICPC team donors: Sea (Garena), Indeed Tokyo, Google, Jump Trading, (and a few more donors who prefer to remain anonymous); or other IT companies like Facebook, Microsoft, Dropbox, MemSQL, Grab, 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.

  5. Can you code in C++ (primary language), Java (second choice), and/or Python (a new one for this round)?

    We will use C++ (11), Java (8), and Python (3.5.2 in Kattis, 2.5.1 :( in Mooshak for now until I am able to reconfigure Mooshak to accept Python 3) in CS3233 S2 AY2017/18. In this course, we are expecting students to be multi-lingual :O. Although a few ex-students had survived CS3233 with only Java, they struggled more compared to those who are well versed in C++ (fastest programming language for programming competitions). This time, Python (3) will be introduced. 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++ 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, NUS ACM ICPC coach, ACM ICPC Asia Singapore Regional Contest Director, the author of Competitive Programming text book (the official text book of this module, we will use 2017b version).

    Rating (out of 5.0, SoC avg ~4.1) Jan-Apr 2018 (n=21) Jan-Apr 2017 (n=16) Jan-Apr 2016 (n=20) Jan-Apr 2015 (n=22) Jan-Apr 2014 (n=19) Jan-Apr 2013 (n=18) Jan-Apr 2012 (n=24)
    Module feedback 4.8 (PB) 4.8 (PB) 4.563 4.733 4.455 4.545 4.778
    Module difficulty 4.1 4.3 4.563 :O 4.067 3.909 4.364 4.444
    Steven's teaching 4.8 4.8 4.603 4.863 (PB) 4.548 4.455 4.778

    Two Qualified Teaching Assistants (they will teach in alternate weeks):
    1. Gan Wei Liang a.k.a. pandamonium (Singapore two times IOI Silver Medalist 2012-2013, SGP coach 2016, and currently an NUS ACM ICPC team member, team Pandamiao, winner of ACM ICPC Manila 2017, member of IOI International Scientific Committee (ISC) for IOI 2020 host country).
    2. Ranald Lam Yun Shao a.k.a. ranaldlys (Singapore IOI Bronze→Silver→Gold Medalist 2012-2013-2014, SGP coach 2017, and currently an NUS ACM ICPC team member, also in team Pandamiao, winner of ACM ICPC Manila 2017, member of IOI International Technical Committee (ITC) for IOI 2020 host country).
    Usually, CS3233 TAs have teaching feedback rating of around ~4.500 too (i.e. good ones).
    Wei Liang and/or Ranald will be mostly available in NUS ACM ICPC Lab (COM1-02-15), especially every Wednesday, 2.30-4.30pm 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,u,v,w; (PS: i,j,k,l for up to 4-nested loop counter variables and u,v,w for reading directed edge (u → v) with weight w)
    2. Putting all those variables as global variables (so that you never have to pass them as function parameter(s), especially the heavy ones like multi-dimensional arrays)
    3. Intentional memory wastage by declaring big arrays as global variable (usually DP table) as big 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: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() (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 (condition)?(if_true):(if_false); 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 macros and typedefs, e.g. #define INF 1e9; #define 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.

If you have read all (scary) questions above and are still interested, simply notify Steven for offline registration before CORS round 3B (the last day of application). The offline registration will be closed as soon as the number of students hits 25 NUS students as we will be joined by about ~20 SG high school students. To minimize the annual attrition rate on Week 02 (Drop without penalty) and also :O on Recess Week (Drop with a 'W' grade), the pre-acceptance selection will be made much more rigorous than usual, i.e. by showing Steven that the applicant can score at least 100 Kattis points by Sunday, 14 January 2018, 23.59.

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

Update on 16 Jan 2018: As of today, there are already 23 accepted + 2 admin only students. As I have to now cater for ~20 guest high school students (a few are still put on waiting list pending the actual situation of first class on Wed 17 Jan 2018), all other aspiring students from now-end of CORS round 3B will be redirected to apply for CS3233 in Jan-Apr 2019 instead, if they have not graduate by then...


Date News

Class Ranklist

Lesson Plan

The lesson plan is easy to remember: All our face to face activities are on Wednesdays, but basically you will work for the entire week for the entire semester 2 if you take this module, possibly harming the Continuous Assessment (CA) marks of your other modules.

  1. Students read the assigned CP3.17b readings before coming to the Wednesday class.
  2. Then, students complete weekly homework (of previous week) before every Wednesday, 10.00am, problem Bs by Wednesday, 4.30pm, and Kattis set of that week by Wednesday, 8.59pm (preferably by 5.30pm, before the next class).
  3. Then, students come to class, ready to attempt the weekly mini contest (with time and peer-(or young Sec/JC student)-pressure) every Wednesday, 5.30-6.45pm.
  4. Then, TA will give immediate on-the-spot solution discussion until at most 7.15pm (max 25 minutes with buffer).
  5. Finally, after a short break, Steven will give more eye-opening lecture about related (but not 100% the same as what you have read by yourself at home) problem solving techniques every Wednesday, 7.30-8.50pm (max 1h 15m with buffer). Steven will have to dismiss everyone from PL2 latest by 9pm.
  6. We repeat this throughout the semester :).
Week Self Reading from CP3.17b before class (Flipped Classroom) Homework
(Wed, 10.00am)
Contest + Debrief
(Wed, 5.30-6.45-7.15pm, PL2)
Class Topics
(Wed, 7.30-8.50pm, 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
As many pages from CP1/2/3/3.17/b; At least from preface up to the end of Chapter 4; Note: For the actual semester, you must have a copy of CP3.17b to go through this course successfully Lots of preparatory work especially for those who do not have competitive programming background yet No contest yet; But if you are not a multi-lingual programmer yet, pick up both C/C++11 (main), Java, and maybe also Python (2/3) by yourself during holiday time At home: Set up a (free) Kattis account, solve first few easy ≤ 2.5 pointer problems @ Kattis, then use Dec17/early Jan18 holiday (~6 weeks) to get ≥ 100 points (~50 AC of ~2 pointer problems or ~[60..70] AC of ~1.5 pointer problems, use Steven's classification here) in Kattis by Sun, 14 Jan 18, 11.59pm to ensure module acceptance, familiarize yourself with Ubuntu 14 (or 16) LTS with GNOME desktop, or self-read the older teaching materials in this public website
17 Jan
Preface to Chapter 1 (all pages) plus simple Ad Hoc problems in Chapter 9 Continue solving various Kattis problems of your choice. Mock
Ad Hoc
(after first lecture)
TA: Both
Let's Talk CP

Introduction; Brief Course Admins; Focus on delivering some "Wow Moments"; A Bit of C++11; Introduction to Python for ICPC, Mock/Preview Contest (not graded, but has high standard)
24 Jan
Chapter 2; Focus on Section 2.2, 2.4.3, and 2.4.4;
Read the rest of Chapter 2 by yourself

Decision to Drop CS3233 without penalty by Sun, 28 Jan 18 (email UG office)
HW01 due
Kattis set #01 due
Mini 01
"Around Linear" Algorithms
With food + (cash) prizes
TA: Wei Liang
Be A Librarian

Mastery of Libraries (C++ STL, Java API, & Python Standard Library); Focus on Bit Manipulation and Binary Indexed (Fenwick) Tree
VisuAlgo: bitmask, segmenttree (optional), fenwicktree
31 Jan
Chapter 3, 4, and 8; Focus on Section 3.1-2, 4.2.3, 4.4.2-3, and 8.1-8.2;
Read Section 3.3 and 3.4 by yourself

HW02 due
Solve Mini 01 B/C
Kattis set #02 due
Mini 02
TA: Ranald (DS expert)
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)
VisuAlgo: bitmask, recursion
07 Feb
Chapter 3, 4, 5, 6, 8, and 9; Focus on various sections about DP: Section 3.5, 4.7, 4.8.1, 5.4, 5.6, 5.9, 6.5, 8.3, 8.4.2, 8.4.4, 9.6, 9.19, and 9.29

HW03 due
Solve Mini 02 B/C
Kattis set #03 due
Mini 03
Complete Search
With food + (cash) prizes
TA: Wei Liang
The Art of Stenography

Dynamic Programming; "Instant" review of CS2010/CS2020 DP Materials; Focus on relationship between DP and DAG; Discussion of a few non-classic DP examples; Formulating non trivial DP states + transitions
VisuAlgo: bitmask, recursion
14 Feb
Chapter 8; Focus on the new Section 8.4; Optional: Read the first 1/3 of CS4234 material

Happy Valentine's Day (Wed) and Happy CNY (Fri-Sat) of this week, BUT do not disappear!!
HW04 due
Solve Mini 03 B/C
Kattis set #04 due
Mini 04
With food + (cash) prizes
Donated by Indeed Singapore

TA: Ranald
(PS: We will do midterm team contest formation after Mini 04)

Coping with (NP-)hard Problems

Summary of the first 1/3 of CS4234 - Optimisation Algorithms in CS3233 style.
VisuAlgo: mvc, steinertree, tsp
21 Feb
Re-read Week 01-05 reading materials and CS1020/2010/2020/2040/C stuffs;
Read "standard" graph topics by yourself (Section 4.1-4.5)
No written HW
due to long CNY weekend
Solve Mini 04 B/C
Kattis set #05 due
Midterm Team Contest
CS2010/2020/2040/C + Week01-05
5.30-9.00pm (3h 30m)

TA: None, both of them are away to IOI 2018 winter meeting 20-24 Feb 2018 to represent Singapore (host country for IOI 2020)
No lecture, we will do Midterm Team Contest
VisuAlgo (for self-review): heap, hashtable, bst, graphds, dfsbfs, ufds, mst, sssp
28 Feb
Although we are not supposed to have any face to face activity this week, nobody prevents you to keep solving Kattis problems 'by yourself' :). Again, peruse Steven's classification here, this time probably aiming for the 3-4+ pointer problems...

Decision to Drop CS3233 with 'W' grade by Sun, 04 Mar 18 (unfortunately, > 0 student did this... :O)
Nothing this week
Enjoy your break
(or enjoy solving Kattis problems)
No class
No class
07 Mar
Chapter 4 and 9; Focus on Section 4.6 and 9.20; Optional: Read the Max-Flow material of CS4234
HW05 due
(no mini contest in recess week)
Kattis set #06 due
Mini 05
(NP-)hard Problems
TA: Wei Liang
How to Prevent Flood?

Quick overview of Network Flow; Quick review of Ford Fulkerson's Max Flow algorithm variants: Edmonds Karp's and especially Dinic's (short comparison with Push-Relabel); Focus on Flow Graph Modeling skill and applications
VisuAlgo: maxflow
14 Mar
Chapter 4, 8, and 9; Focus on Section 4.7, 4.8.4, 8.4.5, 9.6, 9.8, 9.12, and 9.16; Read the Graph Matching material of CS4234.

NOI 2018 Competition; Fri-Sat, 16-17 Mar 18
HW06 due
Solve Mini 05 B/C
Kattis set #07 due
Mini 06
Network Flow
TA: Ranald
Social Development Network

Quick overview of Graph Matching; Unweighted or Weighted MCBM or MCM; Introducing Kuhn Munkres's (Hungarian) algorithm and Edmonds's (Blossom Shrinking)/Matching algorithm; Focus remains on (Bipartite) Graph Modeling skill and applications
VisuAlgo: maxflow, matching
21 Mar
Chapter 5 and 9; Focus on Section 5.3-5.5;
Read the rest of Chapter 5 by yourself; Plus Section 9.9, 9.10, and 9.23
HW07 due
Solve Mini 06 B/C
Kattis set #08 due
Mini 07
TA: Wei Liang

Mathematics overview with a movie; Focus on Java/Python Big Integer, Combinatorics, Number Theory (Extended Euclid, Modular Inverse, Chinese Remainder Theorem)
VisuAlgo: cyclefinding

Note: Minh (and 2 ex CS3233 students) will disappear for Hello India x Russia Programming Bootcamp as one of team DomiNUS preparation for ACM ICPC World Finals 2018, 21-31 March 2018
28 Mar
Chapter 6; Focus on Section 6.6;
Read the rest of Chapter 6 by yourself

Good Friday and Easter Sunday this Week
HW08 due
Solve Mini 07 B/C
Kattis set #09 due
Mini 08
TA: Wei Liang (math expert)
A Glance at Bioinformatics

String Processing; Focus on Suffix Trie, Suffix Tree, and Suffix Array
VisuAlgo: suffixtree, suffixarray

Note: Minh is still on Leave of Absence
04 Apr
Chapter 7; Focus on Section 7.2, 7.3, 9.4;
Read the rest of Chapter 7 by yourself

Also something from Chapter 8/9 and something not found in CP3.17b
HW09 due
Solve Mini 08 B/C
Kattis set #10 due
Mini 09
TA: Ranald (DS expert)
(PS: We have to take class photo tonight, after Mini 09, then do final team contest formation)

Inside Video Games

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

Please give me 30 extra minutes on 04 April to complete CS3233
We will only end the class at 9.30pm on this night...

11 Apr
The entire CP3.17b book and beyond
No written HW
Solve Mini 09 B/C
Kattis set #11 due
Final Team Contest
Week01-11 stuffs
(geometry problemS exist!)
5.30-9.00pm (3h 30m)
With food (sponsored by
Steven and Grace,
assemble in PL2 by 4.45pm)

TA: Both
No lecture, we will do Final Team Contest
18 Apr
No class
(but we can make this week an online Kattis-problem-solving week, using all your CP knowledge that you have gained this semester, there is an interesting achievement system and special HW10 set-up for this purpose)

Steven, Minh, and two senior CS3233 students: Dat Vu and Manh (team DomiNUS) will go to Beijing to represent NUS for ACM ICPC World Finals 2018
HW10 (special)
deferred until Reading Week
Kattis set #12 due
No class NO CLASS (except last special homework)

Clash with the 12th STePS on this day, 5-10pm

Clash with ACM ICPC World Finals 2018,
Beijing, China, 15-20 April 2018
Time for you to study for your other modules... unless you are chasing some more points from Kattis apprentice achievement... HW10 (special) due Join NUS ACM ICPC team selection (Saturday, 15 September 2018)
(which also doubles as ACM ICPC Asia Singapore 2018 Preliminary Contest)
No final assessment, go and save your other modules

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.

AY (Iteration) Flag and Name Current Job
2008/09 (1) 1 VNM Ngo Minh Duc World Finalist 2009 (HM) & 2010 (HM) Addepar (US)
2008/09 (1) 2 VNM Nguyen Hoanh Tien World Finalist 2009 (HM) & 2010 (HM) Microsoft (US)
2009/10 (2) 1 VNM Trinh Tuan Phuong World Finalist 2012 (HM) & 2013 (joint-48) Quantcast (SG)
2010/11 (3) 1 SGP Koh Zi Chun World Finalist 2012 (HM) Microsoft (US)
2010/11 (3) 2 IDN Harta Wijaya World Finalist 2012 (HM) & 2013 (joint-48) Facebook (US)
2011/12 (4) 1 CHN Yang Mansheng N/A Dynamic Technology Lab (SG)
2012/13 (5) 1 VNM Nguyen Tan Sy Nguyen World Finalist 2013 (joint-48) & 2016 (joint-14) Anduin Transactions (VN)
2013/14 (6) 1 IDN Nathan Azaria World Finalist 2014 (joint-19) & 2015 (joint-28) Facebook (UK)
2013/14 (6) 2 IDN Jonathan Irvin Gunawan World Finalist 2014 (joint-19) & 2015 (joint-28) Google (SG)
2014/15 (7) 1 IDN Stefano Chiesa Suryanto Fourth place in Regional Asia Singapore 2015 Improbable (UK)
2014/15 (7) 2 VNM Vu Dinh Quang Dat World Finalist 2015 (joint-28) & 2018 (joint-56) Dynamic Technology Lab (SG)
2015/16 (8) 1 VNM Nguyen Quang Dung Tenth place in Regional Asia Phuket+Singapore 2015 4thd year UG
2015/16 (8) 2 VNM Truong Ngoc Khanh Twentieth place in Regional Asia Singapore 2015 Seagroup (SG)
2016/17 (9) 1 SGP Tan Jun An N/A 4th year UG
2016/17 (9) 2 IDN Agus Sentosa Hermawan World Finalist 2017 (joint-20) 3rd year UG
2017/18 (10) 1 PHL Robin Christopher Cham Yu Fifth place in Regional Asia Yangon 2017 2nd year UG
2017/18 (10) 2 IDN Sergio Vieri Fifth place in Regional Asia Yangon 2017 2nd year UG
2017/18 (10) 3 SGP Bay Wei Heng Fifteenth place in Regional Asia Jakarta 2017 3rd year UG