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 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 (2018/19) ICPC donors: Indeed Singapore, Seagroup, Jump Trading, DRW, Tezos.

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 AY2018/19) is ... technically only limited by the size of COM1-B-PL2 (46 PCs → will be Acer Nitro laptops soon) ... 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 (10 out of 189) 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, ICPC (especially ICPC Asia Singapore Regional Contest 2015/2018), Google Code Jam, Facebook Hacker Cup, 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 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 past eight academic years were 4.57 , 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 trainees (Sec2-JC2 students) beat you in (many) CS3233 contests. 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 current (2018/19) ICPC donors: Indeed Singapore, Seagroup, Jump Trading, DRW, Tezos; or other IT companies like Google, 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 AY2018/19. 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 ICPC coach, ICPC Asia Singapore Regional Contest Director, the author of Competitive Programming text book (the official text book of this module, we will use 2018b version that is given for free onsite at ICPC Asia Singapore 2018 — Yes, all accepted students will get free CP3.18b courtesy of Tezos Southeast Asia).

   Rating (out of 5.0, SoC avg ~4.1)	Jan-Apr 2019 (n=21)	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.7+? (Target)	4.8 (PB)	4.8 (PB) ▲	4.563 ▼	4.733 ▲	4.455 ▼	4.545 ▼	4.778
   Module difficulty	4.1-? (Target)	4.1	4.3	4.563 :O	4.067	3.909	4.364	4.444
   Steven's teaching	4.7+? (Target)	4.8	4.8 ▲	4.603 ▼	4.863 (PB) ▲	4.548 ▲	4.455 ▼	4.778

   Qualified Teaching Assistant:
   Robin Christopher Yu a.k.a. robinyu (Philippines first Bronze medalist (2x), then Philippines first Silver medalist, and currently an NUS ICPC team member: team 3Sophomores, 3rd place in ICPC Jakarta 2018).
   Usually, CS3233 TAs have teaching feedback rating of around ~4.5 too (i.e. very good).
   Robin will be mostly available in NUS ICPC Lab (COM1-02-15), especially every Monday, 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 — 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 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() (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 (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 accepted 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 even last year's crazy rate, i.e. by showing Steven that the applicant can score at least 500 Kattis points (only 100 Kattis points in previous AY) by Monday, 14 January 2019, 08.59AM.

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

News Show All

Class Ranklist

Lesson Plan Hide Past Show Past

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
2008/09 (1)	1	Ngo Minh Duc	World Finalist 2009 (HM) & 2010 (HM)	Addepar (US)
2008/09 (1)	2	Nguyen Hoanh Tien	World Finalist 2009 (HM) & 2010 (HM)	Microsoft (US)
2009/10 (2)	1	Trinh Tuan Phuong	World Finalist 2012 (HM) & 2013 (joint-48)	Quantcast (SG)
2010/11 (3)	1	Koh Zi Chun	World Finalist 2012 (HM)	Microsoft (US)
2010/11 (3)	2	Harta Wijaya	World Finalist 2012 (HM) & 2013 (joint-48)	Facebook (US)
2011/12 (4)	1	Yang Mansheng	N/A	Dynamic Technology Lab (SG)
2012/13 (5)	1	Nguyen Tan Sy Nguyen	World Finalist 2013 (joint-48) & 2016 (joint-14)	Anduin Transactions (VN)
2013/14 (6)	1	Nathan Azaria	World Finalist 2014 (joint-19) & 2015 (joint-28)	Facebook (UK)
2013/14 (6)	2	Jonathan Irvin Gunawan	World Finalist 2014 (joint-19) & 2015 (joint-28)	Google (SG)
2014/15 (7)	1	Stefano Chiesa Suryanto	Fourth place in Regional Asia Singapore 2015	Improbable (UK)
2014/15 (7)	2	Vu Dinh Quang Dat	World Finalist 2015 (joint-28) & 2018 (joint-56)	Dynamic Technology Lab (SG)
2015/16 (8)	1	Nguyen Quang Dung	Tenth place in Regional Asia Phuket+Singapore 2015	Graduating soon
2015/16 (8)	2	Truong Ngoc Khanh	Twentieth place in Regional Asia Singapore 2015	Seagroup (SG)
2016/17 (9)	1	Tan Jun An	Sixteenth place in Regional Asia Singapore 2018	Graduating soon
2016/17 (9)	2	Agus Sentosa Hermawan	World Finalist 2017 (joint-20)	4th year UG
2017/18 (10)	1	Robin Christopher Cham Yu	Third place in Regional Asia Jakarta 2018	3rd year UG
2017/18 (10)	2	Sergio Vieri	Third place in Regional Asia Jakarta 2018	3rd year UG
2017/18 (10)	3	Bay Wei Heng	Champion in Regional Asia Yangon 2018, World Finalist 2019 (joint-62)	4th year UG
2018/19 (11)	1	Nguyen Dinh Quang Minh	World Finalist 2018 (joint-14)	2nd year UG
2018/19 (11)	2	Tran Tan Phat	2nd place in Regional Asia Singapore 2018	2nd year UG
2018/19 (11)	3	Herbert Ilhan Tanujaya	N/A	5th year UG

Scoring Scheme for CS3233 S2 AY18/19

There are two big scoring components: SP(eed) (from live contests, up to 60%) and DI(ligence) (from non-speed-related stuffs, up to 53%).
The theoretical max is therefore 113%, with just 62% 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 24%).
The DI(ligence) component is further divided into four sub-components: H(ome)W(ork) (up to 15%), (Problem)Bs (up to 9%), K(attis)S(ets) (up to 12%), and Ac(hievements) (up to 17%).