JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 1.1. Understanding SRM Competition Format
 1.1. Understanding SRM Competition Format | Reply This is a rewrite of this recipe by mart0258.ProblemTopCoder Algorithm Competition has a specific format that differs from other online contests. Individual competitions are called Single Round Matches (commonly abbreviated to SRMs). Prior to competing in an SRM, one has to understand its structure and build a strategy of approaching it.SolutionThe SRM consists of two main phases and three less stressful technical ones. In order of appearance they are: Registration, Coding, Intermission, Challenge, System Testing.Registration phase starts three hours before the start of the SRM and ends 5 minutes before it. As the name implies, this phase allows people to register for the match.In 5-minute slot between Registration and Coding phases registrants are randomly assigned to rooms in groups of at most 20 people. Note that there are two Divisions for people of different level of skill, and each room holds people of one Division.Coding phase is the time (usually 75 minutes) to solve and submit the given problems. Coders of each Division are given their set of three problems of increasing complexity. Problems complexities are roughly described with their point values - usually 250, 500 and 1000 points, thought the exact values can vary from match to match.TopCoder uses a rather specific method of scoring the submitted solutions. Opening the problem (i.e., accessing problem statement and specifications) starts a countdown for it (and closing it doesn't stop the timer). The longer it takes you to solve the problem and submit it, the lower your score for it will be.Intermission is another 5-minute slot between Coding and Challenge phase, during which you can review the problems once more or move away from your computer for a quick rest.Challenge phase is the time (usually 15 minutes) to examine solutions of other people in your room and try to find mistakes in them. When you think you've found one, you can challenge the flawed solution with a test case for which it returns wrong answer. If your challenge succeeds (i.e., the challenged solution fails), you will be awarded 50 points - but if it doesn't, you lose 25 points. The challenged submission gives no points to its author.System Testing it the last phase, which tests the submissions that survived Challenge Phase on larger set of test cases (prepared by problem writer and expanded with successful challenge cases). Submissions that fail on at least one of the test cases gives no points to its author. The competitor's final score is defined as sum of points awarded for successful solutions and points earned (or lost) during Challenge phase. DiscussionPoints, awarded for the problem, decay over time in non-linear fashion. To be more specific, points awarded can be calculated as http://www.topcoder.com/wiki/download/attachments/4587756/pts.gifHere PT is time between opening the problem and submitting it, TT is duration of Coding phase, and MP is the initial point value of the problem. Thus, a problem submitted within one minute from opening it costs approximately 99.88% of its original point value (however unlikely this might seem, 250 pointers in Div1 often are submitted so fast). On the contrary, if you spend all Coding phase on one problem, it will be worth about 30% of its original value. If you resubmit the problem, it will cost you 10% of its value, but you won't get less than 30% of points.The specific contest structure implies a need for a rather specific strategy of approaching it. Of course, it has much less effect on the performance than the skill of problem solving itself, but sometimes a correct strategy can be worth as much as a problem and an SRM win.Pre-match strategies don't really differ from getting ready to any online contest. Take care of your fleshly needs: raid the fridge for food if you're doing to eat while thinking, get yourself a coffee if the SRM starts at 4 a.m., etc. Prepare for a coding session: turn music on if it helps you to code, have pen and paper nearby in case you'll need to jot down some notes or draw a sketch of problem, make sure your language reference is at hand if you use it often. The first TC-specific decision to be taken during the match is: which problem to open first? Basically you'll have to concentrate on solving the first opened problem before moving to other ones - opening several problems and choosing one of them costs points if you submit both and precious time if you submit only one. Thus, the order of opening plays an important role in match strategy. Most coders prefer to open the Easy problem first, and work their way up from there. This approach maximizes the chances of getting non-zero score, especially for people who are not so sure about solving Medium and never try Hard. Higher-rated coders let themselves try other approaches: they can afford starting the match with Medium or even Hard, and doing Easy the last. The motivation is reasonable as well: if you can do all three problems, but there's not enough time, it's better to get Medium+Hard than Easy+Medium. Probably the soundest advice is: do the highest one that you can comfortably submit first.Once you've opened a problem, it's time to solve it. Don't rush into coding though - make sure you've read the statement carefully and had a glance at the examples before coding, otherwise you might find yourself solving a totally different problem than the one you had to. If you just can't stand wasting time on thinking without coding, start coding routine parts of the solution (like input parsing) while thinking about the more complicated parts.Next delicate stage is testing your solution: too much testing will lower your score due to time spent on it, and too little might lower your score to zero if you overlook some tricky corner case, and your solution fails it. Most people agree that testing on examples is a must (especially since some plug-ins automate this), and inventing special test cases is useful for most problems. A strategy worth a separate mention is: test on examples, submit to save time and then test on some interesting cases, resubmitting if your solution fails some of them.The final part of the match is Challenge phase. Some people totally ignore it, but most coders attempt an effort to gain more points - there's nothing to lose by having a look at other's submissions. Strategies in this phase vary more than in any other stage of the SRM; thus, one can:- have one or several pre-made challenge cases and look through all submissions in the room looking for one that will fail these cases;- look for unnaturally fast submissions that overlook something from the problem statement or fail a corner case;- look for very slow submissions that are submitted seconds before the end of Coding phase, since they can be rushed and not tested on examples;- check low-rated coders' submissions, etc.It is recommended against wasting time on reading solutions which are a mess - they look like they are wrong, but they're correct too often to be worth the effort of studying them.With that many choices to be done during a single match, the key to finding the strategy that works best for you is practice and experience.
 Subject Author Date 1.1. Understanding SRM Competition Format Nickolas Aug 30, 2010 at 3:34 PM EDT Re: 1.1. Understanding SRM Competition Format dimkadimon Aug 30, 2010 at 9:28 PM EDT Re: 1.1. Understanding SRM Competition Format Nickolas Aug 31, 2010 at 1:34 AM EDT Re: 1.1. Understanding SRM Competition Format Eryx Nov 4, 2010 at 6:03 PM EDT Re: 1.1. Understanding SRM Competition Format Nickolas Nov 4, 2010 at 6:18 PM EDT
 Forums TopCoder Cookbook Algorithm Competitions - Rewriting Phase 1.1. Understanding SRM Competition Format Previous Thread  |  Next Thread