10187 - From Dusk Till Dawn

[hoshiko]

Can Vladimir take more than one train from 6 pm to 6 am, or just one train?

thinks~~

[likhan]

If he can cover many visits with many train within the constraints he can take as many train as he wishes within the constraints.

Most probably the problem you are facing is the if he gets on a train in one day say at 5 am and leaves the train at 7 pm the next day this is not legal. he cannot travel at day time. and at day he must stay inside the train station in his coffin.

[yiuyuho]

I see that in judge data there are starting times > 24.

I dunno if that is intiutive to do a %24 as soon as you get the starting time, but what does it mean for a train to department on 1241254 hour of the day?

Would that contain many days or simply is 22?

[igamenir]

Can Vladimir take another train in the same hour in the same hour he arrived? (e.g. 18-22 and than 22-26)

[Abednego]

Could anyone please explain what the path is in sample case #2?

Code: Select all

10
Lugoj Sibiu 12 6
Lugoj Sibiu 18 6
Lugoj Sibiu 24 5
Lugoj Medias 22 8
Lugoj Medias 18 8
Lugoj Reghin 17 4
Sibiu Reghin 19 9
Sibiu Medias 20 3
Reghin Medias 20 4
Reghin Bacau 24 6
Lugoj Bacau

I can't see any path from Lugoj to Bacau. All possible paths must come through Reghin, but the Lugoj-Reghin train leaves at 17 (which is before 18), and the Sibiu-Reghin train arrives at 9, which is after 6. What is wrong?

MODIFIED: Nevermind. I need to read the problem statement more carefully. :-)

[Abednego]

yiuyuho, if the departure time is >=6 or <18, I ignore the train.

[Ndiyaa ndako]

I've tried unsuccessfully to solve this using breadth first search. Is it possible to solve this problem this way or not?

[shamim]

BFS is OK, but your state space should be two dimensional, one for each station and the second for time of arrival.

[Mg9H]

Here is what my program went wrong before I fixed and got it ACC:

1. You should store all the valid routes even if there are 2 or more routes connecting 2 cities.

2. Always start at 18.00 from the starting city.

Good luck

[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/viewto ... ight=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