Online Judge Programming Contest Problems

[Garrett Rowe]

I just wanted to let those interested know that the UVa Online Judge, a site with literally thousands of programming contest type problems has migrated to a new server and now supports Java 1.6.0. It's not a pay site, registration and submission is all free. For a long time they only supported Java 1.1 so this is a huge improvement.

FYI, all Java programs must be submitted in a single source file called Main.java. Nested classes and the like are allowed I believe, although I haven't tried them yet. The judge places a premium on performance meaning the programs must complete under a certain time limit. Even if the program is correct, it can be discouraging getting "Time Limit Exceeded" rejections. On the very first problem I tried (Problem 100), I couldn't get in under the time limit until I changed my isOdd() method from:

public boolean isOdd(int num)
{
   return (num % 2) == 1;
}

to:

public boolean isOdd(int num)
{
   return (num & 1) == 1;
}

Which I guess is a little faster. Although I got my greatest speed gains when I used a Map to memoize results I'd already calculated, which I guess is a much more effective and realistic optimization.

By the way, I have no affiliation with the site except that I find the problems slightly challenging and pretty fun.

[Jim Yingst]

Interesting - I hadn't seen this before. It looks like they're missing some instructions though. How did you know that the file must be called Main.java? I don't see that anywhere on the site. Also it seems that most of the problems take their input from standard input (System.in), but that's also not specified anywhere. (Or maybe some problems specify it, but not the ones I looked at.)

I tried one problem (#999) that no one has gotten correct yet (according to the online judge). It doesn't seem terribly difficult, merely tedious. But my attempts keep timing out after three seconds. It's possible I've overlooked some possible input that creates an infinite loop or something. But I think it's more likely that there's a problem with the problem, since no one else has gotten it either. It's suspicious that the problem statement talks about an "input file" but we never learn the name of the file. I tried reading from standard input as usual. But I wonder if the judge is sitting there waiting for my program to read from a file, while my program is waiting for the judge to feed it some input. There's also no clear way to exit the program, so maybe it's just waiting for more input at the end. Anyway, seems to be a poorly described problem.

I gather they take submissions from anyone who wants to submit a problem. I don't know if there is any quality control. You can check the stats to see hom many people have solved a given problem, which gives some indication of whether it's possible. However if a problem has a low acceptance percentage, that may be because the problem is inherently challenging, or it may just indicate it's hard becuase the instructions are poor. So it's hard to tell if you've got a good problem or not, until you actually work it through.

[Garrett]: Which I guess is a little faster. Although I got my greatest speed gains when I used a Map to memoize results I'd already calculated, which I guess is a much more effective and realistic optimization.

Yep. In problem 100 I actually used an array, not a Map. I did that for several others too. I'm sure there are some where a Map makes more sense. But don't overlook arrays if they apply - they're very fast.

Anyway, thanks for bringing the site to my attention.

[Garrett Rowe]

Jim Yingst : How did you know that the file must be called Main.java?
I had tried some of the problems before from their old site, which has some useful howto sections. There is also a forum there to discuss problems and particular language issues and the like. But like I said, the old site only supported Java 1.1, and java.io was restricted to the point that you had to roll your own method to read from System.in, BufferedReader and InputStreamReader were off limits.

I believe that all the problems read from standard input (System.in), and the output must be written to standard output (System.out), so if you're timing out its unlikely that its because of file reading issues, it may be that there is an issue with the inputs or that they've just set an exceedingly high bar for the time limit. The fact that no one has solved it leads me to believe there is probably some sort of issue.

Jim Yingst: 'm sure there are some where a Map makes more sense. But don't overlook arrays if they apply - they're very fast.
I hesitated to use an array there simply because I just didn't know how large I was going to have to make it.
[ January 28, 2008: Message edited by: Garrett Rowe ]

[Jim Yingst]

Thanks for the info, Garrett.

[Garrett]: it may be that there is an issue with the inputs or that they've just set an exceedingly high bar for the time limit. The fact that no one has solved it leads me to believe there is probably some sort of issue.

I'm pretty confident the problem is not that the time limit is too short. It's just not a computationally intensive problem, and three seconds is much longer than it needs to be. I might have an infinite loop somehow, but given that there are sixteen other people who haven't solved it (and none who have), I think there's a problem with the tester. The problem itself is just not that complicated.

[Garrett]: I hesitated to use an array there simply because I just didn't know how large I was going to have to make it.

Yes, there's no clear upper bound on the size. But you can write it so that if a given number is beyond the bounds of the array, you simply don't cache that value. That's slower, but still works. Eventually you will get to a number that's below the cutoff. Since the problem specified 1000000 as the maximum number to start with, I used an array of size 2000000 - more than big enough for most of the numbers we need, and small enough to fit easily in a JVM with default settings.

[Oscar Johansson]

When in college, I used to practice programming and algorithms through the problems on this site.

Bring it on : My Stats on Online Judge

Almost all my submissions were done 5 years ago. I may be able to write better/faster solutions now.

[Oggi Olli]

Very cool, thanks for sharing.

I'll most definitely have a go at one of those problems any day soon..!

[mahesha]

thanks for sharing !!!
it is vejavascript: x()
jumpingjoyry useful