Home Contact Us Customer Service Subscribe now!
THE SINGAPORE MAGAZINE OF RESEARCH,
TECHNOLOGY AND EDUCATION
About Innovation   |   Editorial Matters
SCHOOLS SECTION:
The World of Competitive Programming
The joy and excitement of competing in the world of competitive programming
Feng Jiahai and Tan Guoxian

omputer literacy is a buzz phrase often touted as an essential 21-century skill. In Singapore, the country's “Smart Nation” initiative in particular, has highlighted the value of computer programming in the public consciousness. Fewer people, though, are acquainted with competitive programming. It is this journey into the world of competitive programming I am fortunate enough to have experienced that I would like to share about in this article.

Competitive programming is a mind sport where contestants pit their wits against each other to complete tasks as fast as possible. The format of the contest varies from individual contests to team contests, from 2-hour contests to 24-hour marathon contests. In general, contestants are given a set of tasks, and have to write a program to solve these tasks. A typical task requirement is to write a program that reads in some input, process it under time and memory constraints, and to produce an output as specified by the task. A simple example of a task may require contestants to find the shortest way to drive from point A to point B, given a list of junctions and the time needed to travel between adjacent junctions. Solutions are assessed in the form of computer programs, and they are first graded based on accuracy, then based on how much CPU time and memory the programs require to compute the solution.

To provide an idea of how crucial the speed of the program is, first consider a naïve solution to a problem which tries to find every permutation of cities to visit. Next, optimize the shortest path out of every possible permutation of cities to visit. Such a solution if done by a traditional brute force approach, faces a combinatorial explosion scenario, and evaluating up to 40! permutations would take the entire computing power of humanity many times the present age of the universe in order to run through. In comparison, a single computer can easily find the shortest path out of a few thousand cities in less than a second, provided a more efficient algorithm is used.

Problem-setters of such competitive programming platforms often find inspiration from real-life applications, then model the data in a simplified way as a problem statement. However, when tasks are not amenable to mathematical description, things begin to get interesting. Creative tasks may require contestants to think out of the box and test out novel ideas. In 2013's International Olympiad in Informatics (IOI), contestants were even required to classify images into categories such as modern art or impressionist landscapes. Art itself is highly subjective, and to identify and model the unique characteristics of each category, at least well enough to differentiate between two categories, is truly a test of ingenuity. The versatility of computer programs lends great diversity to competitive programming problems, which never ceases to pique my interest.

The Present Landscape of Competitive Programming

Competitive programming is a young “sport”, but is widely practiced. Many contests are held by various parties, from companies like Google [1] to the USA Computing Olympiad (USACO) [2] over the Internet, which are open to the public. Attractive cash prizes in the order of cool hundreds of thousands of US dollars are commonplace in the world of Kaggle competitive programming platforms [3]. For example, a team from Singapore won the top prize of $100,000 for the winning algorithm that can more accurately predict flight arrival times. The prizes in such competitive programming platforms are often sponsored by the industry and the government, where millions of dollars in either potential revenue or cost savings motivate them to be sponsors of such attractive prize money.

For high school students however, the allure does not come from just the prize money, but also the fame and prestige of the international recognition in winning a medal. Perhaps the most recognized and prestigious competitive programming contest for high school students is the IOI, which is hosted by a different country every year. Each country can send a team of up to four high school students; the limited places allocated to countries meant the team has to be rigorously selected, commonly through olympiads conducted on a national level. IOI’s present format (as of 2015) consists of two 5-hour contests, with each contest having three problems. IOI 2015, held in Almaty, Kazakhstan, saw more than 300 participants from more than 80 countries. IOI 2016 saw an increase of high school students participating when it was held in Kazan, Russia. The Singapore team participating in IOI 2016 saw impressive results, with Jacob Teo Por Loong winning the gold medal, Clarence Chew Xuan Da and Pang Wen Yuen winning silver medals respectively, and Zhang Guangxuan winning the bronze medal [4].

The Appeal of Competitive Programming

Many may be perplexed over what drives competitive programmers to spend hours on end poring over a few problems, which more often than not, are simple problems that can be described in a few sentences. For some, the appeal of competitive programming lies in the process of deducing the solution. Many tasks describe a scenario, which at first glance appears daunting and intractable, but at the same time, the knowledge that the problem setter has a solution continuously taunts and tantalizes the programmer to wrack their brains for an elegant solution. The arduous process of unearthing the solution often reveals hidden structures underlying the original task, which in itself is an act of discovery that is deeply satisfying. This process, perhaps, offers glimpses of the “supreme beauty” that Bertrand Russel had described mathematics to possess.

However, unlike mathematics, competitive programming participants do not only have to arrive at a valid solution, but also have to implement that solution in code. The sense of accomplishment upon completing a computer program is not unlike the joy and pride of a craftsman over his work. The programmer revels in the wonders of creation each and every time he or she writes a program.

Ultimately, competitive programming is a contest, and there always is an atmosphere of (friendly) rivalry. The adrenaline rush, the thrill of the race against time is a constant backdrop in programming contests, and is what draws many to competitive programming. Nonetheless, competitive programmers are united by their shared love of computer science. Take the Topcoder [5] or CodeForces [6] communities for example. Problem solutions are made public, and many freely share their knowledge by writing tutorials or discussing other problems. Even the national training team for the United States opens up their training portal [2] (which contains a repository of problems) to everybody around the world.

Personal Takeaways

Competitive programming for me, though, is not all fun and joy. With the sand trickling down the hourglass, the mounting pressure to solve the problem sometimes was overwhelming. What is especially frustrating is when I am certain that my solution, on paper at least, is correct, but somehow, for some strange reason, my program fails to produce the right answer (typically caused by an implementation mistake). The desperate hunt for the elusive “bug”, especially under time pressure, takes a huge toll on my mental fortitude, being so close to completion, but yet so far. It is times like this where the resilience and mental strength of competitive programmers are put to the test, to not give in to panic and to calmly reevaluate the situation.

This experience in competitive programming is one that I will always treasure, and continue to take part in. Not only has competitive programming exposed me to algorithmic thinking, which further serves as a launchpad into other forms of programming, it has also shaped my character, and shaped who I am. I strongly urge you to find out more about competitive programming and pick it up! [7]

References

  1. Google CodeJam: http://code.google.com/codejam
  2. USA Computing Olympiad: http://usaco.org/
  3. MIT Technology Review: https://www.technologyreview.com/s/513141/a-data-crunching-prize-to-cut-flight-delays/
  4. MOE press release: https://www.moe.gov.sg/news/press-releases/outstanding-performance-by-singapore-at-the-2016-international-olympiads-for-the-sciences--mathematics-and-informatics
  5. Topcoder: https://www.topcoder.com/
  6. CodeForces: http://codeforces.com/
  7. I would recommend using the above-mentioned resources, amongst numerous other online judges (such as UVA) which are by no means of lower quality. You may consider getting the book Competitive Programming (for more information: http://cpbook.net/) or any freshman textbook on
    Algorithms.

Feng Jiahai graduated from Raffles Institution with straight A’s and a distinction in H3 Mathematics. In his high school years, he was an active participant in many Olympiads. He represented Singapore in the International Olympiad of Informatics and the International Olympiad of Physics, where he went on to achieve gold medals in both international olympiads. For more information about this article, please contact Feng Jiahai at fengjiahai@yahoo.com.sg.

Tan Guoxian is a teacher-scientist at the Raffles Science Institute in Raffles Institution. His unique position as a teacher-scientist allows him to mentor research projects with the JC students in his specialized field of pattern recognition in Raffles Institution. For more information about this article, please contact him at guoxian.tan@ri.edu.sg.

Click here to download the full issue for USD 6.50

Advertisement
» addiction treatment
» Business Directory
» Drug and Alcohol Treatment Centers
» essay
» Merchant Account
» advanceloan.net
» Nursing Courses
» Credit Cards
» Drug Treatment Centers
» Durack Institute of Technology
» Online Forex Trading
» Opérateur mobile
» Source Quality China Products
» Yodle
 
Copyright© 2019 World Scientific Publishing Co Pte Ltd and National University of SingaporePrivacy Policy
INNOVATION magazine is a joint publication of Nanyang Technological University, National University of Singapore and World Scientific Publishing Co Pte Ltd