Lily's Blog

Mobile Application Development and Competitive Practice Problems

ACM Style Competitions

Here's some important information from this site (http://mcicpc.cs.atu.edu/) that depicts the essential aspects of ACM style events.

An except below:

Competition/practice overview

In the contest (and practices!), you get to bring any book/paper references you like.  I was really impressed by the student that brought his favorite book with physical tabs added to locate the most important parts.  Your team of three people is presented with one computer and 6-10 problems on paper.  Each problem generally has 1-2 page specifications, showing sample input and output data, and requiring 10-120 line of code beyond the standard I/O setup (if you are concise – which is not exactly necessary).  Some are very easy, and a good team will bang out such a problem first in 10-20 minutes.  Others take much longer, figuring out an appropriate algorithm, and covering and coding all the special cases.  Problems are non-interactive and follow the simple pattern:  read data from the input file, process data, output data to standard output.  Input data will always have a count at the beginning or a sentinel at the end, making it easy to construct a main loop without worrying about end-of-file conditions.

In all problems exact input and output formats are specified.  The judge’s input data is generally much more thorough than the sample input data you are given.  Your program is run with the secret judge’s input data.  It should produce the exact right output to the screen, or your submission is wrong.  Little information is given back to you if you make an error – one of 5 categories is checked off.  Unfortunately this complicates finding and correcting bugs for another submission.  File naming conventions must be followed exactly.  there is a base name for a given problem, say “juggler” for instance.  Then the input file must be “juggler.in”.  Debugging info needs to go  to the standard error stream, not standard output.  The source file name is “juggler” with the appropriate language extension (juggler.cpp, juggler.java).  The base name is generally all lowercase.  If you write in Java, this makes you break the usual Java class naming convention:  the source file name and main class name are all lower case.

The scoring is based first on the number of problems eventually submitted totally correct.  In some competitions, some teams get all the problems (from 150 or so total teams among all local sites).  In some competitions no one team gets all the problems.  Among teams solving the same number of problems, time and incorrect submission penalties determine who is ahead.  For each problem, time is measured from the beginning of the competition to the time of correct submission.  Each incorrect submission for a problem that is ultimately submitted correctly adds a 20 minute penalty to your correct submission time.  Problems that never get a correct submission, no matter how many incorrect submissions, are ignored in scoring.  Note that time is measured on each problem from the beginning of the competition, not the time of the last correct solution.  This means that it is strategic to do the simplest problems first.  Fifteen minutes for one problem solution, followed by 50 more minutes for a second solution would give you 15 + (15+50) = 80 minutes for the two problems. Fifty minutes solving the first problem, followed by 15 more minutes for the second problem would give you 50 + (50+15) = 115 minutes for the two problems – much worse.  If the 15 minute problem was submitted correctly the first time, and the 50 minute problem had two incorrect submissions before the correct submission, the total minutes recorded would be 2*20 = 40 minute more, (120 or 155).

Because of the two very different attributes of scoring, there are different strategies.  Different team members may have different skills, encouraging splitting the problems up and basically working alone.  Pn problems where one team member has a clear idea or is the only one clued in, working alone saves the time of coordinating, and possibly leads to having time to solve an extra problem, which is the most important thing in scoring.  The secondary scoring critieria, time until solutions, encourages working together.  As a simplicication, ignore the time to type into the computer:  If three problems each take 30 minutes for one individual, but can be modularized into three 10 minute portions for each team member, then working together, problems can be submitted after 10, 20, and 30 minutes for a score of 60, but if everyone works separately (and then types instantly) the times would be 30, 30, and 30, for a score of 90.  The overhead of time to communicate plans detracts from the cooperative solving approach.

The most important thing that encourages working together is running out of time.  It is a common point of frustration to have 2-3 problems 90% complete at the end, and then they all count for nothing.  If several are working on problems that require some thinking time and they do not have time to finish, then switch approach:  Agree on one of them that can be split in pieces among several people thinking about distinct pieces, or brainstorming together, and get it done in time!

You get to submit written questions to the judges if anything seems ambiguous to you, and you get a written response back.  Sometimes the questions and answers from other teams are posted for all to see.  

For input in Java use java.util.Scanner. Note that the file names specified are generally in lower case.  For a java source file, that means the main class name needs to be the same lowercase name.  For sample problems with statements see the sample problems.  Note the solutions to Addition for a simple illustration of the basic I/O and naming format.

Favorite topics/algorithms for problems:

  • Translate a simple, straightforward description
  • Shortest or longest paths in graphs
  • Sorting
  • Recursive searches
  • Geometrical output (always text, but graphical ideas for positioning parts are likely to come in).  Java programmers not familiar with two dimensional arrays might want to look at my Java 2-D Array Introduction.
  • Problems involving all combinations, permutations, or subsets.  I have sample code that is also a good review of recursion in recursion.html

Be sure to read the excellent, extensive description of language and algorithmic skills desired is at the Mid-Central site http://mcicpc.cs.atu.edu/.

Loading