Tips to be Competitive
General tips below:
Tip 1: Type Code Faster!
No kidding! Although this tip may not mean much as ICPC and (especially) IOI are not
typing contests, we have seen Rank i and Rank i + 1 ICPC teams separated only by a few
minutes and frustrated IOI contestants who miss out on salvaging important marks by not
being able to code a last-minute brute force solution properly. When you can solve the same
number of problems as your competitor, it will then be down to coding skill (your ability to
produce concise and robust code) and ... typing speed.
Try this typing test at http://www.typingtest.com and follow the instructions there
on how to improve your typing skill. Steven’s is ∼85-95 wpm and Felix’s is ∼55-65 wpm. If
your typing speed is much less than these numbers, please take this tip seriously!
On top of being able to type alphanumeric characters quickly and correctly, you will
also need to familiarize your fingers with the positions of the frequently used programming
language characters: parentheses () or {} or square brackets [] or angle brackets <>, the
semicolon ; and colon :, single quotes ‘’ for characters, double quotes “” for strings, the
ampersand &, the vertical bar or the ‘pipe’ |, the exclamation mark !, etc.
Tip 2: Quickly Identify Problem Types
In ICPCs, the contestants (teams) are given a set of problems (≈ 7-12 problems) of varying
types. From our observation of recent ICPC Asia Regional problem sets, we can categorize
the problems types and their rate of appearance,
In IOIs, the contestants are given 6 tasks over 2 days (8 tasks over 2 days in 2009-2010) that
cover items 1-5 and 10, with a much smaller subset of items 6-10 in Table 1.1. For details,
please refer to the 2009 IOI syllabus [20] and the IOI 1989-2008 problem classification [67].
Category
In This Book
Ad Hoc 1-2
Greedy (usually the original ones)0-1
Chapter 4
Mathematics 1
String Processing 1
Computational Geometry 1
Some Harder/Rare Problems 1
total 10-13
Table 1.1: Recent ACM ICPC (Asia) Regional Problem Types
The classification in Table 1.1 is adapted from [48] and by no means complete. Some techniques, e.g. ‘sorting’, are not classified here as they are ‘trivial’ and usually used only as a
‘sub-routine’ in a bigger problem. We do not include ‘recursion’ as it is embedded in cate-
gories like recursive backtracking or Dynamic Programming. We also omit ‘data structures’ as the usage of efficient data structure can be considered to be integral for solving harder
problems. Of course, problems sometimes require mixed techniques: A problem can be classified into more than one type. For example, Floyd Warshall’s algorithm is both a solution
for the All-Pairs Shortest Paths (APSP, Section 4.5) graph problem and a Dynamic Programming (DP) algorithm. Prim’s and Kruskal’s algorithms are both solutions
for the Minimum Spanning Tree, graph problem and Greedy algorithms we will discuss (harder) problems that require more than one algorithms and/or data structures to be solved.
In the (near) future, these classifications may change. One significant example is Dynamic
Programming. This technique was not known before 1940s, nor frequently used in ICPCs or
IOIs before mid 1990s, but it is considered a definite prerequisite today. As an illustration:
There were ≥ 3 DP problems (out of 11) in the recent ICPC World Finals 2010.However, the main goal is not just to associate problems with the techniques required to
solve them like in Table 1.1. Once you are familiar with most of the topics in this book, youshould also be able to classify problems into the three types in .To be competitive, that is, do well in a programming contest, you must be able to confidently and frequently classify problems as type A and minimize the number of problems that you
classify into type B. That is, you need to acquire sufficient algorithm knowledge and develop your programming skills so that you consider many classical problems to be easy. However,
to win a programming contest, you will also need to develop sharp problem solving skills (e.g. reducing the given problem to a known problem, identifying subtle hints.
Tip 3: Do Algorithm Analysis
Once you have designed an algorithm to solve a particular problem in a programming contest,
you must then ask this question: Given the maximum input bound (usually given in a good
problem description), can the currently developed algorithm, with its time/space complexity,
pass the time/memory limit given for that particular problem?
Sometimes, there are more than one way to attack a problem. Some approaches may be
incorrect, others not fast enough, and yet others ‘overkill’. A good strategy is to brainstorm
for many possible algorithms and then pick the simplest solution that works (i.e. is fast
enough to pass the time and memory limit and yet still produce the correct answer) .
Tip 4: Master Programming Languages
There are several programming languages supported in ICPC 7 , including C/C++ and Java.
Which programming languages should one aim to master?
Our experience gives us this answer: We prefer C++ with its built-in Standard Template
Library (STL) but we still need to master Java. Even though it is slower, Java has powerful
built-in libraries and APIs such as BigInteger/BigDecimal, GregorianCalendar, Regex, etc.
Java programs are easier to debug with the virtual machine’s ability to provide a stack trace
when it crashes (as opposed to core dumps or segmentation faults in C/C++). On the
other hand, C/C++ has its own merits as well. Depending on the problem at hand, either
language may be the better choice for implementing a solution in the shortest time.
Suppose that a problem requires you to compute 25! (the factorial of 25). The answer is
very large: 15,511,210,043,330,985,984,000,000. This far exceeds the largest built-in primitive
integer data type (unsigned long long: 2 64 − 1). As there is no built-in arbitrary-precision
arithmetic library in C/C++ as of yet, we would have needed to implement one from scratch.
The Java code, however, is exceedingly simple. In this case,
using Java definitely makes for shorter coding time.
Tip 5: Master the Art of Testing Code
You thought you nailed a particular problem. You identified its problem type, designed
the algorithm for it, verified that the algorithm (with the data structures it uses) will run
in time (and within memory limits) by considering the time (and space) complexity, and
implemented the algorithm, but your solution is still not Accepted (AC).
Depending on the programming contest, you may or may not get credit for solving the
problem partially. In ICPC, you will only get points for a particular problem if your team’s
code solves all the secret test cases for that problem. Other verdicts such as Presentation
Error (PE), Wrong Answer (WA), Time Limit Exceeded (TLE), Memory Limit Exceeded
(MLE), Run Time Error (RTE), etc. do not increase your team’s points. In current IOI
(2010-2012), the subtask scoring system is used. Test cases are grouped into subtasks, usually
simpler variants of the original task with smaller input bounds. You will only be credited
for solving a subtask if your code solves all test cases in it. You are given tokens that you
can use (sparingly) throughout the contest to view the judge’s evaluation of your code.
taken from-CP 3
Tip 1: Type Code Faster!
No kidding! Although this tip may not mean much as ICPC and (especially) IOI are not
typing contests, we have seen Rank i and Rank i + 1 ICPC teams separated only by a few
minutes and frustrated IOI contestants who miss out on salvaging important marks by not
being able to code a last-minute brute force solution properly. When you can solve the same
number of problems as your competitor, it will then be down to coding skill (your ability to
produce concise and robust code) and ... typing speed.
Try this typing test at http://www.typingtest.com and follow the instructions there
on how to improve your typing skill. Steven’s is ∼85-95 wpm and Felix’s is ∼55-65 wpm. If
your typing speed is much less than these numbers, please take this tip seriously!
On top of being able to type alphanumeric characters quickly and correctly, you will
also need to familiarize your fingers with the positions of the frequently used programming
language characters: parentheses () or {} or square brackets [] or angle brackets <>, the
semicolon ; and colon :, single quotes ‘’ for characters, double quotes “” for strings, the
ampersand &, the vertical bar or the ‘pipe’ |, the exclamation mark !, etc.
Tip 2: Quickly Identify Problem Types
In ICPCs, the contestants (teams) are given a set of problems (≈ 7-12 problems) of varying
types. From our observation of recent ICPC Asia Regional problem sets, we can categorize
the problems types and their rate of appearance,
In IOIs, the contestants are given 6 tasks over 2 days (8 tasks over 2 days in 2009-2010) that
cover items 1-5 and 10, with a much smaller subset of items 6-10 in Table 1.1. For details,
please refer to the 2009 IOI syllabus [20] and the IOI 1989-2008 problem classification [67].
Category
In This Book
Ad Hoc 1-2
Complete Search (Iterative/Recursive) 1-2
Divide and Conquer 0-1Greedy (usually the original ones)0-1
Dynamic Programming (usually the original ones) 1-3
Graph 1-2Chapter 4
Mathematics 1
String Processing 1
Computational Geometry 1
Some Harder/Rare Problems 1
total 10-13
Table 1.1: Recent ACM ICPC (Asia) Regional Problem Types
The classification in Table 1.1 is adapted from [48] and by no means complete. Some techniques, e.g. ‘sorting’, are not classified here as they are ‘trivial’ and usually used only as a
‘sub-routine’ in a bigger problem. We do not include ‘recursion’ as it is embedded in cate-
gories like recursive backtracking or Dynamic Programming. We also omit ‘data structures’ as the usage of efficient data structure can be considered to be integral for solving harder
problems. Of course, problems sometimes require mixed techniques: A problem can be classified into more than one type. For example, Floyd Warshall’s algorithm is both a solution
for the All-Pairs Shortest Paths (APSP, Section 4.5) graph problem and a Dynamic Programming (DP) algorithm. Prim’s and Kruskal’s algorithms are both solutions
for the Minimum Spanning Tree, graph problem and Greedy algorithms we will discuss (harder) problems that require more than one algorithms and/or data structures to be solved.
In the (near) future, these classifications may change. One significant example is Dynamic
Programming. This technique was not known before 1940s, nor frequently used in ICPCs or
IOIs before mid 1990s, but it is considered a definite prerequisite today. As an illustration:
There were ≥ 3 DP problems (out of 11) in the recent ICPC World Finals 2010.However, the main goal is not just to associate problems with the techniques required to
solve them like in Table 1.1. Once you are familiar with most of the topics in this book, youshould also be able to classify problems into the three types in .To be competitive, that is, do well in a programming contest, you must be able to confidently and frequently classify problems as type A and minimize the number of problems that you
classify into type B. That is, you need to acquire sufficient algorithm knowledge and develop your programming skills so that you consider many classical problems to be easy. However,
to win a programming contest, you will also need to develop sharp problem solving skills (e.g. reducing the given problem to a known problem, identifying subtle hints.
Tip 3: Do Algorithm Analysis
Once you have designed an algorithm to solve a particular problem in a programming contest,
you must then ask this question: Given the maximum input bound (usually given in a good
problem description), can the currently developed algorithm, with its time/space complexity,
pass the time/memory limit given for that particular problem?
Sometimes, there are more than one way to attack a problem. Some approaches may be
incorrect, others not fast enough, and yet others ‘overkill’. A good strategy is to brainstorm
for many possible algorithms and then pick the simplest solution that works (i.e. is fast
enough to pass the time and memory limit and yet still produce the correct answer) .
Tip 4: Master Programming Languages
There are several programming languages supported in ICPC 7 , including C/C++ and Java.
Which programming languages should one aim to master?
Our experience gives us this answer: We prefer C++ with its built-in Standard Template
Library (STL) but we still need to master Java. Even though it is slower, Java has powerful
built-in libraries and APIs such as BigInteger/BigDecimal, GregorianCalendar, Regex, etc.
Java programs are easier to debug with the virtual machine’s ability to provide a stack trace
when it crashes (as opposed to core dumps or segmentation faults in C/C++). On the
other hand, C/C++ has its own merits as well. Depending on the problem at hand, either
language may be the better choice for implementing a solution in the shortest time.
Suppose that a problem requires you to compute 25! (the factorial of 25). The answer is
very large: 15,511,210,043,330,985,984,000,000. This far exceeds the largest built-in primitive
integer data type (unsigned long long: 2 64 − 1). As there is no built-in arbitrary-precision
arithmetic library in C/C++ as of yet, we would have needed to implement one from scratch.
The Java code, however, is exceedingly simple. In this case,
using Java definitely makes for shorter coding time.
Tip 5: Master the Art of Testing Code
You thought you nailed a particular problem. You identified its problem type, designed
the algorithm for it, verified that the algorithm (with the data structures it uses) will run
in time (and within memory limits) by considering the time (and space) complexity, and
implemented the algorithm, but your solution is still not Accepted (AC).
Depending on the programming contest, you may or may not get credit for solving the
problem partially. In ICPC, you will only get points for a particular problem if your team’s
code solves all the secret test cases for that problem. Other verdicts such as Presentation
Error (PE), Wrong Answer (WA), Time Limit Exceeded (TLE), Memory Limit Exceeded
(MLE), Run Time Error (RTE), etc. do not increase your team’s points. In current IOI
(2010-2012), the subtask scoring system is used. Test cases are grouped into subtasks, usually
simpler variants of the original task with smaller input bounds. You will only be credited
for solving a subtask if your code solves all test cases in it. You are given tokens that you
can use (sparingly) throughout the contest to view the judge’s evaluation of your code.
taken from-CP 3
Amazing tips for beginners. I would share this post with my friends. Thanks for sharing such an informative piece of content.
ReplyDelete