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 (for online 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 (2022++) ICPC donors: Sea Group and Jump Trading (renewals with other donors are still in negotiation as of 01 January 2022).

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 31 DEC 2021: The quota of this class (S2 AY 2021/22) is ... technically only limited by the REDUCED size of COM1-B-PL2+COM1-B-PL4 (46+24 = 68 fast-enough 2018 Acer Nitro Laptops) as I can only have 19+12 = 31 students onsite at PL2+4 reduced capacity of 20 (19 students+1 student TA) + 12 = 32 students excluding the instructors... but not that many NUS students are eligible (or dare enough) to take this extremely competitive module. In 13 academic years of CS3233 classes, on average only ~19 NUS students were enrolled per year and only a few (13 out of 243) are female... This S2 AY 2021/22, it seems that the class size on Week 01 is 31 pax (a new record?) and with 2 female students :O.

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 IOI 2020 (Online Competition) and/or IOI 2021 (Online Competition) hosted by Singapore/NUS), ICPC (especially ICPC Asia Singapore Regional Contest 2015/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 (probably they still join the contests in online mode only due to COVID-19 and MOE rules of no intermingling between schools...). 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 (2019/20 and 20/21; list to be refreshed by January 2022) ICPC donors: Indeed Singapore, Sea Group, SenseTime, Jump Trading, Citadel | Citadel Securities, HRT, DRW; or other large IT companies like Google, Facebook, Microsoft, Dropbox, 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 (now 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 2021/22 (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 (both end up became online competitions), NUS ICPC coach, 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.1)	Jan-Apr 2022 (n≥24?)	Jan-Apr 2021 (n=18)	Jan-Apr 2020 (n=12)	Jan-Apr 2019 (n=22)	Jan-Apr 2018 (n=21)	Jan-Apr 2017 (n=16)
   Module feedback	Target ≥ 4.5	4.8 ▼	4.9 (PB) ▲	4.6 ▼	4.8 ==	4.8 ▲
   Module difficulty	Target ≤ 4.2	4.3 ▼	4.2 ▼	4.3	4.1	4.3
   Steven's teaching	Target ≥ 4.5	4.9 (PB) ==	4.9 (PB) ▲	4.5 ▼	4.8 ==	4.8 ▲

   Qualified Teaching Assistant:
   

   1. Vuong Hong Long, CS3233 winner S2 AY 2019/20, ICPC World Finalist 2021 (MLG)
   2. Dan Alden Baterisna Varsobia, CS3233 winner S2 AY 2020/21
   3. Zhang Guangxuan, ICPC World Finalist 2021 (MLG), problem setter only, for contest style diversity
   4. Marc Phua Hsiao Meng, problem setter only, for contest style diversity
   
   

   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.30pm to answer any CS3233/Competitive Programming queries, if any (or e-consultations via Zoom if necessary).

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; (PS: i,j,k,l for up to 4-nested loop counter variables, m,n for number of edges/vertices of a graph, 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) — 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 19 31 accepted NUS students.

This AY, we will again *NOT* be joined ONSITE by about ~20 SG high school students but some of them may join online due to COVID-19 restrictions.

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 Friday, 31 December 2021, 23.59.

Note: This course registration section will not be prominent from Monday, 10 January 2022 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 for S2 AY 2021/22

R	Flag	Nickname/Kattis (CF)	Spe	Dil	Tot
1	VNM	Hong Duc (user202729_)	4.0	11.5	15.5
2	SGP	nickyfoo (nickyfoo)	3.0	10.5	13.5
2	BGD	Rezwan (Rezwan.Arefin01)	3.0	10.5	13.5
4	IND	Udit (T1duS)	3.0	10.0	13.0
5	IDN	Pa.Nic (Pa.Nic)	4.0	8.5	12.5
5	IDN	Rama (rama_pang)	1.0	11.5	12.5
7	SGP	Eric (no CF yet)	3.0	8.5	11.5
8	VNM	Hoang Kien (Maripium)	4.0	7.0	11.0
9	IDN	Berted (Berted)	1.5	9.0	10.5
10	MNG	Amar (nvmdava)	1.5	8.5	10.0
10	SGP	Frederick (no CF yet)	1.0	9.0	10.0
12	THA	Pontakorn (peppapig)	1.0	8.0	9.0
13	MYS	Ryan (no CF yet)	3.0	5.5	8.5
13	SGP	Yi Qun (no CF yet)	1.0	7.5	8.5
13	SGP	Yong Xiang (no CF yet)	1.0	7.5	8.5
13	SGP	Kevin (no CF yet)	1.0	7.5	8.5
17	USA	Ethan (no CF yet)	3.0	5.0	8.0
17	IND	Shacha (SleepyShashwat)	1.0	7.0	8.0
19	CHN	Li Jiayu (no CF yet)	1.0	6.5	7.5
19	SGP	Genie (no CF yet)	1.0	6.5	7.5
21	SGP	Jia Lin (no CF yet)	1.0	5.5	6.5
22	SGP	Kendrick (no CF yet)	1.0	4.5	5.5
22	SGP	Kai'an (no CF yet)	1.0	4.5	5.5
22	IDN	Audrey (no CF yet)	1.0	4.5	5.5
25	SGP	Li Shuo (no CF yet)	1.0	3.5	4.5
25	MYS	Yong Ler (yongler)	1.0	3.5	4.5
25	SGP	Nicholas (no CF yet)	1.0	3.5	4.5
28	MYS	Yan Jie (no CF yet)	1.0	3.0	4.0
28	IDN	Andrew (no CF yet)	1.0	3.0	4.0

Lesson Plan Hide Past Show Past

The lesson plan is easy to remember: All our face to face activities are on Mondays, 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 CP4 Book 1 and/or Book 2 readings before coming to the Monday class.
2. Then, students complete weekly homework (of previous week) before every Monday, 09.00am and then problem Bs+Kattis set of that week by Monday, 5.30pm (before the next class starts).
3. Then, students come to class, ready to attempt the weekly mini contest (with time and peer-(or young Sec/JC student-online)-pressure) every Monday, 5.30-6.45pm.
4. Then, TA will give immediate on-the-spot solution discussion until at most 7.15pm (inclusive of potential NUS ICPC donor talk).
   
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 Monday, 7.30-8.50pm (max 1h 20m with 10m buffer to 9pm). Steven will have to dismiss everyone from PL2 latest by 9pm.
6. We repeat this throughout the semester :).

This lesson plan is from S2 AY2020/21 and will be updated for the S2 AY2021/22 version and to take into account the latest COVID-19 Safe Management Measures

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 (US)
2013/14 (6)	2	Jonathan Irvin Gunawan	World Finalist 2014 (joint-19) & 2015 (joint-28)	Jump Trading (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	Graduated (pls update me)
2015/16 (8)	2	Truong Ngoc Khanh	Twentieth place in Regional Asia Singapore 2015	Sea Group (SG)
2016/17 (9)	1	Tan Jun An	Sixteenth place in Regional Asia Singapore 2018	Google (SG)
2016/17 (9)	2	Agus Sentosa Hermawan	World Finalist 2017 (joint-20)	Sirclo (ID)
2017/18 (10)	1	Robin Christopher Cham Yu	Third place in Regional Asia Jakarta 2018+2020	Jump Trading (SG)
2017/18 (10)	2	Sergio Vieri	Third place in Regional Asia Jakarta 2018+2020	Google SG
2017/18 (10)	3	Bay Wei Heng	World Finalist 2019 (joint-62) & 2020 (invitational contest - honor)	Jane Street
2018/19 (11)	1	Nguyen Dinh Quang Minh	World Finalist 2018 (joint-14) & 2021 (to be conducted sometime in 22?)	4th year UG
2018/19 (11)	2	Tran Tan Phat	Champion in Regional Asia Jakarta 2019	4th year UG
2018/19 (11)	3	Herbert Ilhan Tanujaya	N/A	Traverse Technologies
2019/20 (12)	1	Vuong Hoang Long	World Finalist 2021 (to be conducted sometime in 22?)	3rd year UG
2020/21 (13)	1	Dan Alden Baterisna	Tenth place in Regional Asia Jakarta 2021	2nd year UG
2021/22 (14)	1	This could be you	???	???

Scoring Scheme for CS3233 S2 AY 2021/22

There are two big scoring components: SP(eed) (from live contests, up to 57%) and DI(ligence) (from non-speed-related stuffs, up to 55%).
The theoretical max is therefore 112%, 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 21%).
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 18%).