UVa

From CS315

Jump to: navigation, search

The Association for Computing Machinery (ACM) is currently sponsoring a robotic online judging machine for automated evaluation of select computer programs written in Java, C, C++, and Pascal. These programs are selected from competitive sets of problems located on the judge server. When the program successfully runs, it is judged as accepted and ranked against all previous entries of the same program by other users. Ranking considers primarily, time to successfully run the problem and in some cases the amount of machine memory used during the runtime. Programs that do not function correctly by the standards specified in the problem description will not run and the judge server will display a short description of the program's failure under the user’s submissions page.

The most famous of these ACM sponsored robotic machines is located at Universidad de Valladolid in Spain and was often referred to as UVa-Spain. It no longer takes submissions and has been replaced by a newer system located at Baylor University in the United States which is currently called UVa-Baylor. The following information is for using the UVa-Baylor machine to robotically evaluate your programs.


Contents

Getting an Account

Start by visiting the UVa-Baylor home page. You will see in the upper left side of the screen a Login block. The registration link located under this block is the path way to your new account. Click it. It will ask you for: name, username (make it up), email, password (make it up), and online judge ID(Spain’s User ID: if you previously had a Spain account, this will migrate your statistics).

Once you complete and submit this form, they will send you an email to complete the process. Do what they say and your in.

Migrating Statistics from Spain

There has been some confusion in migrating the information from previously judged programs run at Spain. It centers around Baylor’s newer machine which runs updated versions of most programming languages and seems to have a significant processing power advantage. Currently, there is no way to determine a direct correlation between the runtimes on the Spain machine verses the runtime on the United States’ machine. In general, it is better to evaluate statistics separately for each machine. So the migrated statistics from UVa-Spain can’t be directly compared to the statistics for UVa-Baylor.

Problem Sets

UVa-Baylor Problem Sets Here is where the fun is. These online judges have collections of different programming problems. They exercise the programmer’s knowledge of math, logic, analysis, coding, algorithm design and computer hardware. There are two basic categories of problems. Regular problem sets, they are sorted into volumes I through IX and number 100-through 999. Contest problem sets, they are sorted C through CXII and number 10,000 through 11,289.

The problems represent a significant collection of brain testing questions. They follow the format:

  1. Description of problem
  2. Input specifications
  3. Output specification
  4. Promises on input restrictions, formats,and runtime considerations

While browsing the folders, each problem is listed in a table in numerical order. The problem’s row has a link to the problem description, statistics on the total number of submissions for this problem divided by the solving percentage, and total users divided by the solving percentage.

Programming Languages

This online judge has modern compliers and is ready to compile programs using up to date APIs and libraries. It supports Java, C, C++, and Pascal. Users can develop their code on anything from a plain text editor to fancy IDEs. The judge is only concerned with the code.

Here are the programming language specifications for the UVa-Bayor Online Judge.

Java

AVA 1.6.0 - Java Sun JDK

C

ANSI C 4.1.2 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE

C++

C++ 4.1.2 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE


Pascal

PASCAL 2.0.4 - Free Pascal Compiler

Resources

UVa-Baylor Java Code Skeleton – basic I/O used to get you started

UVa-Spain - a collection of information

Submitting Code

After you have an account, log into the server, then submit your code written in either; Java, C, C++, or Pascal.

Submitting? do this:

  1. Browse the problems
  2. Select the problem set you are interested in. Say problem 100 which is in Volume I of the regular problem sets.
  3. Select the specific problem
  4. Wait for the problem description to open
  5. In the upper right corner of the description are three icons: drive array, pdf file, and three colored bars. Select the drive array. Wait for the submission page to load.
  6. Select the programming language you code is written in
  7. Either cut and paste the code into the text box or upload it from a file
  8. Click the submit button

Checking the Results

To see the results: click the My Submissions link in the left hand frame. It will take you to a summary of all your recent submissions.

  • Here is a list of the possible verdicts according to the UVa-Spain documentation. UVa-Baylor’s site has no information on which of these verdicts is still implemented
  1. Accepted (AC)
  2. Presentation Error (PE)
  3. Accepted (P.E.)
  4. Wrong Answer (WA)
  5. Crash - Runtime Error (RE)
  6. Time Limit Exceeded (TL)
  7. Memory Limit Exceeded (ML)
  8. Output Limit Exceeded (OL)
  9. Restricted Function (RF)
  10. Compile Error (CE)
  11. Submission Error (SE)
  12. Can't Be Judged (CJ)
  13. Access Denied (AD)
  14. Non Authenticated (NA)
  15. Out Of Contest Time (OC)
  16. Delayed (DL)
  17. Judge Disabled
  18. Judge Not Ready

A detailed description of the verdicts can be reviewed at Understanding Online Judge Answers

Your Ranking for the problem?

To see Your Ranking, go back to the problem description (you must be logged on and the program must be accepted by the judge) then click the three colored bars icon in the upper right corner just right of the pdf icon. It takes you to a ranking page that displays the top 20 plus your ranking. It will be just above the top ranked program time. You can see your runtime and problem ranking.

University of Texas at Austin

Here are some student write-ups on select problems recently worked.

Interview with CS315 Puzzler Grader - Mike Slegeir

Advice

  • What is the most important piece of advice you could give to lower classmen trying to get the fastest times?

The thing that will make your program the fastest is the fastest algorithm. Each operation you do may use the fewest cycles possible, but that doesn't matter if it does too much work.

Insights and/or Suggestions

  • What insights and/or suggestions do you have into System methods and design strategies that work best to reduce time, say like:

Data Storage

  • Data Storage - native arrays verses Java Collections, conversions to smaller native types like short or byte or any other data holding ideas, pre-building and storing repeatedly used values?

Native data types will always be the fastest since any other data type is just built upon native types.

Mathematics

  • Mathematics - what math functions seem to work fastest like: plus, minus, %, i<<2, or i>>2, multiplication, division? When should math replace logic decisions?

The only time I think it would be beneficial to replace a mathematic operation with a bit-wise operator is if you aren't changing the number of operations that are being performed. For example x/2 => x>>1 is good, x%2 => x&1 is good, but x*3 => x<<1 + x has diminishing returns (but I doubt it's even as fast). Overall, a good compiler should take of these optimizations for you, and they often will, but whether or not Java specifically optimizes these things I can't say for certain.

Algorithm Analysis

  • Algorithm Analysis – when trying to cut times, what do you look at in the program flow first. How do you determine if it can be cut?

This is tricky, and varies depending on the problem. The advise I would give is to look at the high level structure of the algorithm and see if there's redundant work that can be eliminated or if there is a way to implement it using fewer steps.

Cautions

  • Do you have any cautions to offer lower classmen on using the UVa and trying to beat the best times like; deciding how the program should be approached, or anything else that you feel someone should be careful about when working with either the problem sets or the UVa server?

I think students should first make the program work and understand why it works before they start optimizing. Then when trying to optimize it's easier to guarantee that all the optimizations are the right ones, and it's easier to see which ones may actually make a difference. 

 "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." 
(Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.)

Common Problems

  • What are the two most common problems you have seen in class puzzlers that cause a reduction in assignment grades?

In order of severity and frequency: A lot of students will turn in their assignments that still read input from files, rather than System.in. Others will name files or the class improperly. Lastly, students will either turn in confusing code because they

  • a) weren't explaining what they were doing
  • b) had jumbled up syntax that made things hard to follow
  • c) flooded their code with irrelevant comments (often I see comments that just restate the line of code in English; it doesn't help the reader understand the algorithm)

Hope that helps, Mike

Written by Paul Ashe

Retrieved from "http://z.cs.utexas.edu/users/downing/cs315/index.php/UVa"
Personal tools