ICPC Practice V

2019 ICPC Practice Contest series

to
Starts in

About

In an effort to select a team of 3 students to represent our department, our university for participating at the ICPC (International Collegiate Programming Contest) this month (October 26, Saturday), this is the 5th contest.

Go CU Denver!!

Prizes

  1. Getting selected to participate at the Rocky Mountain Regional Contest (a North American Regional ICPC, https://rocky.icpc.io/)
  2. Bragging rights that you have participated an international competitions and competed against schools from Arizona, Utah, Colorado, Wyoming, Eastern Nevada, Idaho, Montana, Alberta, Saskatchewan, and New Mexico.

Rules

  • The creator of this contest is solely responsible for setting and communicating the eligibility requirements associated with prizes awarded to participants, as well as for procurement and distribution of all prizes. The contest creator holds HackerRank harmless from and against any and all claims, losses, damages, costs, awards, settlements, orders, or fines.
  • Code directly from our platform, which supports over 30 languages. Learn more here.

Contest Rules The ICPC maintains the official rules that apply by default to all regional contests. Individual regions may clarify and/or extend these rules as they see fit. Most of the clarifications and extensions for the regional contest are defined in this page and in the Notes to Teams document (which is provided to all teams on the day of the contest).

Electronic Devices Except for simple watches, teams may not have any electronic devices in their possession during the contest. This includes, but is not limited to, phones and other communication devices, calculators, calculator watches, PDAs, electronic translators or dictionaries, e-books, audio players/recorders, video players/recorders, scanners, and printers. Mere possession of such a device will result in immediate disqualification, regardless of whether or not it was used.

Late Registration There is no late registration. If you do not register via the ICPC web site by the posted deadlines, you cannot participate.

Machine-Readable Media Teams may not possess any machine-readable electronic or magnetic media during the contest unless provided by the site explicitly for contest use. Violation of this rule will result in immediate disqualification, regardless of intent or whether the media were actually used.

Reference Materials The World Finals only allow teams to have 25 pages of reference material in PDF format, which is verified and printed out for the team for its use during the contest. For the Mid-Central USA contest, teams may bring any amount of printed reference material, including printouts of source code. If you have a book that includes a CD, be sure to leave the CD at home; see above.

Registration Priority Our primary goal is to maximize the number of teams that participate in the contest; our secondary goal is to maximize the number of schools.

  • Schools may register as many teams as they like before the registration deadline. The ICPC web site automatically time-stamps each registration and marks it “pending”. (2) No registrations will be allowed after the deadline, period. (3) Until the deadline, teams will be “accepted” in the order that they registered, up to a maximum of two teams per school, as long as space is available. (4) Third, fourth, and higher teams from a school will always be left “pending” until after the deadline. (5) After the deadline, if any space is available, third teams will be accepted in the order that they registered, then fourth teams will be accepted in the order that they registered, and so on.

There is no limit on the number of teams that may compete from a single institution assuming that sufficient space is available. However, a school’s teams may only compete at a single site.

**Frequently Asked Questions ** https://rocky.icpc.io/faq.html

Information for Contestants Getting ready for ICPC? Make sure you go through this checklist:

  • Make sure you’re eligible to compete. This PDF flowchart might help.
  • Find a coach and two teammates (unless they found you first).
  • Make sure your coach registers your team before the deadline.
  • Understand the regional contest rules.
  • Study the notes to teams.
  • Participate in the North American online practice contests, or by solving problems on Kattis.
  • Bring lots of reference materials.
  • Understand your programming language.
  • Beef up your programming skills.
  • Check Your Mathematical Knowledge.
  • Practice, practice, practice.

Reference Materials We suggest bringing language reference manuals, data structures and algorithms textbooks, discrete math textbooks, and general math reference books. (The problems don’t typically assume or require sophisticated mathematics, but you might be able to use math to simplify a problem or find an easier solution.) Also bring printouts of the problem statement and solution for any practice problems you worked on, and any notes you or your coach may have created.

Note that while sites will usually provide some online documentation, it is not a good idea to rely on that too heavily. When one of your team members is using the computer, he or she should be programming, not browsing through online documentation looking for inspiration. Use online documentation to help you remember the details of what you already know.

Understanding Your Programming Language Obviously the better you know your language the better you’ll do. Here are some suggestions about what you should know.

All Languages Character classification and case conversion. String handling, including converting between strings and numbers. Using arrays.

C The formatted I/O functions printf and scanf, and the corresponding string functions sprintf and sscanf, which are much more powerful than most people realize. The string functions strchr, strrchr, strspn, strcspn, strpbrk, strstr, and strtok. The binary search function bsearch and the quicksort function qsort.

C++ The STL classes bitset, deque, list, map, priority_queue, queue, set, stack, and vector. The STL algorithms accumulate, adjacent_find, binary_search, copy, count, equal, fill, find, for_each, generate, includes, inner_product, lexicographical_compare, max_element, merge, min_element, mismatch, next_permutation, prev_permutation, remove, replace, reverse, rotate, set_difference, set_intersection, set_symmetric_difference, set_union, sort, swap, transform, and unique. The STL function objects such as equal_to, logical_not, and plus. The string stream classes istringstream and ostringstream.

Java

  • The Scanner and Formatter classes, plus printf.
  • The wrapper classes Boolean, Character, Double, and Integer, which have a number of useful methods.
  • The java.util collection classes ArrayList, BitSet, HashMap, HashSet, LinkedList, Stack, TreeMap, and - TreeSet.
  • The java.util class StringTokenizer.
  • The java.util.regex classes Matcher and Pattern.
  • The java.math class BigInteger.

Python 2/3

  • For standard input: read, readline, readlines Basic data structures: list, dict, set, tuple Modules for data advanced structures: array, collections, heapq, bisect Regular expressions: re - compile, match, search Note: Python may not be a good choice for time-critical problems.

Beef Up Your Programming Skills Knowledge of the following data structures, algorithms, and programming techniques will be useful.

  • Basic data structures: stacks, queues, arrays, and lists.
  • Basic algorithms: sorting and searching.
  • Binary trees.
  • Brute-force search.
  • Backtracking search.
  • Generating all permutations or combinations of a set.
  • Recursion.
  • Dynamic programming.
  • Graphs and their algorithms, including breadth-first search, depth-first search, minimum spanning trees, shortest paths, topological sort, and transitive closure.
  • Basic parsing techniques such as recursive descent, operator precedence, or infix-to-postfix conversion.

You should also practice with a variety of different types of problems. Regionals usually includes some combination of the following:

  • Short problems with elementary coding,
  • Longer problems, but where the instruction sequence is laid out for you; you just have to make sure you make no mistakes when coding it!
  • Problems requiring basic data structures
  • Problems with fairly direct applications of upper level algorithms
  • Problems requiring a very creative solution, no matter how many algorithm classes you have taken
  • Check Your Mathematical Knowledge
  • Up to 25% of the Regional Competition may include higher math as described below:

Higher math may include

  • matrix operations: multiplication, addition, subtraction; solving a matrix equation
  • 3D vector operations: addition, scalar multiplication, dot product, cross product, triple scalar product as volume
  • root finding of continuous functions by bisection
  • calculus of one variable topics: finding extrema with the help of derivatives

Practice, Practice, Practice Schedule. Ideally you should practice once per week. Have a 1-3 hour practice where you try to solve as many problems as possible under contest conditions. Any problems that you don’t solve must be solved during the week before the next practice. Keep a record of all the problems you solved, their solutions, and any notes about unusual features of the problem.

Team Strategy. You only have one computer, so learning to work as a team is essential. The most important thing is to accurately judge the difficulty of the problems. Many talented teams have done poorly because they started working on one of the hardest problems first. Remember that the length of a problem description is not necessarily related to its difficulty. For additional tips, check out Teamwork in Programming Contests: 3*1=4.

Problems There are many sources for practice problems. Here are a few:

Other Competitions - TopCoder - RoboCode

Scoring

How are teams ranked? Teams are first ranked by number of correct solutions: the more problems which are solved by a team, the higher their rank.

Teams that have finished the same number of problems are then ranked by fewest penalty points: the fewer points, the higher the rank. The penalty points accrued for your team is the sum of:

  • 20 points for each incorrect submission before an accepted solution.
  • The number of minutes from the start of the contest to the submission time of the correct solution to a problem.

Example: The contest starts at 10:00 am; Team Zorbo, turns in problem 1 correctly at 10:43, makes two incorrect submissions of problem 2 before submitting a correct solution at 12:35, and makes 3 incorrect submissions for problem 3 without ever turning in a correct solution. The Zorbos would have 225 penalty points broken down in the following table:

Problem Submission Penalty Time Penalty Total
1 0 * 20 = 0 0:43 = 43 43
2 2 * 20 = 40 2:25 = 145 185
total 2 * 20 = 40 3:08 = 188 225

Note that there is no penalty accrued for problem 3, since it was never submitted correctly

Incidentally, the last tie-breaker rule is the time of the last correct submission.

Sign up for ICPC Practice V now.

Not a genuine coding contest?