Rules clarifications

[pepak]

Hi!

I am new to this site and these contests. I am supposed to solve the problem 10187 in Java, but after reading the problem specification as well as all How-To's, I can't help but notice that the rules are vague at best. It is quite possible I have overlooked something, so I would appreciate if you could at least tell me if these issues are specified somewhere on this site:

1) Time limit:

- What is the time limit for these problems? Should I write my programs tu run in less than a second? Less than a milisecond? Less than a year?

- What are the specs of the machine that will be running my programs? Will the CPU time be dedicated to my problem or should I expect concurrent execution? Will the results of the Online Judge be consistent? (If a program runs in 0.01s, will it always run in 0.01s or can I expect it to run 10s when the server is under heavy load?)

- How is the time calculated exactly? It is rather important to know if just the time to complete the problem itself is measured, if input and output times are also considered, or, in the particular case of Java, if the time to run the interpreter (and possibly, heaven forbid, the byte-code compiler) is taken into account (also, how is caching performed? If I am the first to run javac, am I at a disadvantage against those who are run after me, because their copy of javac is already in cache?)

2) Memory limit

- An actual number might be quite helpful. Should I aim at 1 MB? 1 KB? 1b?

3) Allowed functions

- It's very nice to know that some classes and methods are prohibited and that the Judge will refuse my submissions if I am using them. But would it be too much trouble to at least provide a list of the prohibited functions?

4) 10187-Specific

- At what time starts Vladimir his travels? As the problem is "specified", the Judge can refuse ANY solution simply by the claim that "you assumed the start was at 0:00, but in fact it is at 1:00".

[kryptolus]

Hi!

I am new to this site and these contests. I am supposed to solve the problem 10187 in Java, but after reading the problem specification as well as all How-To's, I can't help but notice that the rules are vague at best. It is quite possible I have overlooked something, so I would appreciate if you could at least tell me if these issues are specified somewhere on this site:

I'm pretty new around here but I'll try to answer from what I know.

1) Time limit:

- What is the time limit for these problems? Should I write my programs tu run in less than a second? Less than a milisecond? Less than a year?

The usual time limit is 10 seconds.

- What are the specs of the machine that will be running my programs? Will the CPU time be dedicated to my problem or should I expect concurrent execution? Will the results of the Online Judge be consistent? (If a program runs in 0.01s, will it always run in 0.01s or can I expect it to run 10s when the server is under heavy load?)

If you go to http://online-judge.uva.es/p/problemstat.php?p=:10187, you can see the information about the judge for the problem. I don't know if you can find the specs, but there's no reason you would need them. Submissions for the same problem are judged on one host as far as I know. I'm not sure if only one submission is judged at a time on each host, but I assume that's the case because times are very consistant. The biggest difference I've seen when resubmitting the same code was 0.002seconds. On that page, you can also see how fast every else solved the problem. You can use those numbers to set a goal for yourself.

- How is the time calculated exactly? It is rather important to know if just the time to complete the problem itself is measured, if input and output times are also considered, or, in the particular case of Java, if the time to run the interpreter (and possibly, heaven forbid, the byte-code compiler) is taken into account (also, how is caching performed? If I am the first to run javac, am I at a disadvantage against those who are run after me, because their copy of javac is already in cache?)

I don't use Java for my submissions so I never really searched for answers to such questions... maybe another person can answer them.

2) Memory limit

- An actual number might be quite helpful. Should I aim at 1 MB? 1 KB? 1b?

Not sure what the actual limit is. It's probably different for Java programs.
I think I remember using several megabytes for certain problems without any complications.

3) Allowed functions

- It's very nice to know that some classes and methods are prohibited and that the Judge will refuse my submissions if I am using them. But would it be too much trouble to at least provide a list of the prohibited functions?

I think there's some information available on the forums about this. I think things like file access, exec and similiar functions are prohibited.

4) 10187-Specific

- At what time starts Vladimir his travels? As the problem is "specified", the Judge can refuse ANY solution simply by the claim that "you assumed the start was at 0:00, but in fact it is at 1:00".

I just looked at the description and from what I can tell, the start time is for you to decide. The trains leave at scheduled times so it's not like you can make arbitrary choices of time for the start time.

There are threads for each problem.
http://online-judge.uva.es/board/viewtopic.php?t=5075&highlight=10187

[Darko]

About the running time: I am not quite sure how it works, but UVa uses gcj which compiles the bytecode into an executable and then they run it (or something like that).

For whatever reason, they stuck with the gcc version 2.95, and its gcj supports only Java 1.1 (although they claim it supports Java 1.2, but it doesn't). Well, it supports some of Java 1.1, I should say.

Memory requirements are the same as for the others - I think it's 32 MB (although I noticed they increased it to 64MB for the last couple of contests, so maybe they are heading in that direction). And yes, the time limit is usually 10 secs.

I think that teachers should not force students to submit here in Java because the judge is not Java-friendly. For what is supported, you might as well use C. I haven't tried other online judges, but there are some that support 1.5 from what I understand (hm, should look it up).

There are so many weird things going on with their Java compiler, all I can suggest is, make Java 1.1 docs handy and read a few posts here about restrictions.

Btw, I thought that all Runtime Errors get reported as Wrong Answers, but I got a RTE in Java for the first time the other day (trying to print (char)253). But - in most cases, if you get WA, check if the running time is about the same as other Java submitions, if not, might be a RTE. Usually the problem turns to be I/O. You can check their front page, they have the submissions per language, Java has suspiciously few RTEs.

I don't know why I stuck with Java, but if you have no reason to do so and if you are required to do these problems, switch to C/C++ while you still can

If you are still going to stick with Java, note that it is much slower than others - there are ways to speed something up (like using System.out.write() instead of System.out.print()), but you are pretty much on your own. Only built-in data structures available to you are Vectors and Hashtables, for instance.

(Note: I wouldn't advocate this change if they actually supported recent Java, and by "recent" I mean anything within the last 10 years. I'd be fine if they only added Collections.)

Darko

[pepak]

Thank you for your answers

3) Allowed functions

I think there's some information available on the forums about this. I think things like file access, exec and similiar functions are prohibited.

Unfortunatelly, the information available on the forums is very poor. The best I could find is a list of some packages that contain prohibited classes. There's no mention whether other packages also contain prohibited classes and which particular classes from the "dangerous" packages are prohibited.

4) 10187-Specific

I just looked at the description and from what I can tell, the start time is for you to decide. The trains leave at scheduled times so it's not like you can make arbitrary choices of time for the start time.

I find that hard to believe. If I am permitted to set my initial time at will, I can get more than one valid output for given input data. The reason is, the total travel time is not important in this problem - the number of times 12:00 is crossed is.

For example, consider that the graph only contains three towns:

Code: Select all

  Berlin
  Paris
  Madrid

only three trains:

Code: Select all

  Berlin-Paris leaving at 18:00 and 0:00, both with 4 hours travel time
  Paris-Madrid leaving at 0:00 with 5 hours travel time

Let's say Vladimir wants to travel from Berlin to Madrid. If I can set the starting time to 18:00, I will travel 4 hours to Paris, wait 2 hours for the next train and reach Madrid at 5:00, not needing any can of blood. If the starting time is 0:00, Vladimir would need 1 can of blood because he would have to spend the day in Paris, waiting 20 hours for his train to Madrid.

[kryptolus]

I find that hard to believe. If I am permitted to set my initial time at will, I can get more than one valid output for given input data. The reason is, the total travel time is not important in this problem - the number of times 12:00 is crossed is.

For example, consider that the graph only contains three towns:

Code: Select all

  Berlin
  Paris
  Madrid

only three trains:

Code: Select all

  Berlin-Paris leaving at 18:00 and 0:00, both with 4 hours travel time
  Paris-Madrid leaving at 0:00 with 5 hours travel time

Let's say Vladimir wants to travel from Berlin to Madrid. If I can set the starting time to 18:00, I will travel 4 hours to Paris, wait 2 hours for the next train and reach Madrid at 5:00, not needing any can of blood. If the starting time is 0:00, Vladimir would need 1 can of blood because he would have to spend the day in Paris, waiting 20 hours for his train to Madrid.

The problem asks for the trip with the minimum amount of blood required. Given the above situation, I personally would think needing zero cans of blood is the minimum solution. A post in the problem thread, however, says "Always start at 18.00 from the starting city. ", but I don't know if that is correct or not. The best way is to just try both solutions. This detail should not have a major effect on the algorithm.

[pepak]

For whatever reason, they stuck with the gcc version 2.95, and its gcj supports only Java 1.1 (although they claim it supports Java 1.2, but it doesn't). Well, it supports some of Java 1.1, I should say.

I may have understood it incorrectly, but I believe the prohibited classes are an (artificial) additional limitation to the limitations set by gcj. In other words, that I can write a program that will compile perfectly well with gcj, but will still be rejected by the Online Judge because it uses one of the prohibited classes.

I think that teachers should not force students to submit here in Java because the judge is not Java-friendly. For what is supported, you might as well use C. I haven't tried other online judges, but there are some that support 1.5 from what I understand (hm, should look it up).

Well, I guess I will have to write it in two languages: One for submission (requirement: something that will get submitted) and one for class (requirement: something which is in Java). I just don't feel like wrestling with an unknown compiler with further unspecified limitations, especially not in a language which I rather hate.

There are so many weird things going on with their Java compiler, all I can suggest is, make Java 1.1 docs handy and read a few posts here about restrictions.

The reports about multiple dereference problems were very "encouraging" indeed :-\

Thanks for the answers

[kryptolus]

The following page has some information about the restricted packages:
http://acm.uva.es/problemset/java.html