Page 1 of 3

10681 - Teobaldo's Trip

Posted: Sun Jul 18, 2004 5:56 am
by alex[LSD]
:lol:
Well thats funny. Some problemsetters are now ASUMING things that all preblemsolvers are SO USED to. Look at this particular problem. It just ain`t said nowhere that the guy can`t go over TWO "links between cities" in ONE day. Nobody informed us that the guy is that slow.
Like in the sample input #2, he could go from 1->2 during the first day. And 2->1->3 during the second day. WHY THE HELL NOT?!
Thanks for y'all's attention. If I am wrong tell me so. I m glad I was sleepeng yesterday instead of solving this.

Posted: Sun Jul 18, 2004 11:15 am
by Mohammad Mahmudur Rahman
Hi Alex,
Well, I do support your concern that the problemsetters are leaving too much to be assumed now-a-days. But I think this problem description did not confuse the solvers that much because the problem statement leads to the idea of uniform speed by default (As otherwise is not specified) and the Sample output matches the idea. But what should someone do when the problem statement does not match with sample I/O & finally one has to get AC by sending a solution for which sample I/O doesn't match (Problem C for the yesterday's contest, surely it did not have a multiple corrector judge program). How can a programmer assume which Sample I/O is correct & which must be corrected by himself? :evil:

Finally, I think you've done the best thing yesterday -
I m glad I was sleepeng yesterday instead of solving this.
If this sorts of problem is given again, I hope to join you. :wink:

Posted: Sun Jul 18, 2004 12:05 pm
by Adrian Kuegel
But what should someone do when the problem statement does not match with sample I/O & finally one has to get AC by sending a solution for which sample I/O doesn't match (Problem C for the yesterday's contest, surely it did not have a multiple corrector judge program). How can a programmer assume which Sample I/O is correct & which must be corrected by himself?
Yes, problem C was really annoying. I finished my program after 7 minutes, and then tried to figure out what I did wrong. After convincing myself, that my output was correct I submitted, ignoring the fact that I couldn't reproduce the sample output and got Accepted.
But also in problem B it was not good explained what to do in case of multiple solutions; I think this is the reason why nobody got Accepted.
And problem E didn't define what kind of alimentary chains are allowed - if one animal can appear more than once or not.
From someone of my university I heard that he found out with asserts that limits for problems D and F were wrong in the judge input file.
So only problem without mistake seems to be problem G.

Posted: Sun Jul 18, 2004 12:51 pm
by little joey
Yep. After reading all problem statements and struggling with problem C for a while, and waiting for ages for the OJ to compile and judge my code, I turned away in disgust, put off my PC and watched a DVD for the rest of the evening. Congrats to you Adrian that you still managed to solve 5/7.

One thing to say, is that this was a local contest and therefore it only has to live up to local standards. I sincerely hope that all problems are fixed _before_ they are added to the archive. But my expectations are low...

Posted: Sun Jul 18, 2004 3:16 pm
by rotoZOOM
I examined my program for problem C (contained 3 lines of algo code) for a long time and didn't find any mistake. Sample input is wrong (MM must be in [0-59] in last case there is 79).
What about D:
Description clearly says
The input set consists of a positive number N ≤ 1000 , that gives the length of the sequence, followed by N integers. Each bet is an integer greater than 0 and less than 1000.
What do we see in sample input ? Right ! We see many negative numbers there. How can I perform it.
Ok I just read in all numbers (due to sample input), but I met next problem. There are cases when N>1000.
After that I turned power off and went to sleep.
I hope I never see such problems again.

Posted: Sun Jul 18, 2004 3:48 pm
by Dreamer#1
Adrian Wrote:

From someone of my university I heard that he found out with asserts that limits for problems D and F were wrong in the judge input file.
I think you are right. I got AC in D but not sure whether the limits were ok or not cause I'd set the array size to 10100 but about problem F there must be something improper about the judge data because I'm sure there can't be any mistakes in my code but I got RTE, which is quite impossible if the limits specified in the problem were maintained in the input data set. Even a WA wouldn't have made me feel as bad as I feel now. No luck with C either. Don't know why time limit of E was set to 40 secs cause I feel that is primarily the reason behind such a huge queue at the last hour. By the way, my AC solution for E took just 0.5 secs.

I think the limits MUST be specified CORRECTLY at the problem statement about the input.

regards

-Dreamer

Posted: Sun Jul 18, 2004 5:26 pm
by jpfarias
Hi!

I'm the problemsetter for E. I did not took much attention on the other problems. Did not tried to solve them also.

On my problem, I think there is not much more to say. I just say that an animal is predator of another, so they are in same chain. Is this dificult to realize? If some animal appear or not twice or more on the input I think this will not influence the final result. If A is predator of B and C is predator of B, the chain has size 3. What's wrong with that?

I'll read the other problems later and see if I get as confused as you.

JP.

Posted: Sun Jul 18, 2004 5:29 pm
by jpfarias
About the problem C, I've read it before and we have corrected that mistake in sample input/output. Maybe the wrong version was sent to the judge.

JP.

Posted: Sun Jul 18, 2004 5:32 pm
by jpfarias
Me again....

The time limit were tested on a slow machine. I dunno what is the machine specs on the judge. That could be the cause of a big time limit.

JP.

Posted: Sun Jul 18, 2004 5:33 pm
by Adrian Kuegel
I didn't ask if an animal occurs more than once in the input; I asked if it is allowed that it occurs more than once in a chain.
Suppose, the predator relation is given as
a b
b c
c a
Then, if animal can occur more than once in a chain, the maximal chain length is infinity, which should then be defined in the problem.
So I assumed that each animal can occur only once. But then you ask for the longest path in a (cyclic) graph, which is an NP complete problem. So I used brute force to solve it, although I thought that the given limits on number of animals would lead to a TLE. But surprisingly, the answer I got was WA!!!.
Therefore I thought, I must have misunderstood the problem.
Can you clarify it please?

Posted: Sun Jul 18, 2004 5:44 pm
by jpfarias
Sure!

a b ==> b is predator of a
b c ==> c is predator of b
c a ==> a is predator of c

Got that? The size is 3, there are 3 animais in the chain. The chain is cyclic, but I don't ask you for the size of the largest path in the chain, just how many animals there are in the chain.

Hope it's clear now.

JP.

Posted: Sun Jul 18, 2004 5:46 pm
by Adrian Kuegel
Ok, with the example you gave above I was able to understand the problem.
You asked about the size of largest connected component.
But as you can see when you look at the ranklist, many others had problems to understand what you asked for, because you can be sure if the problem statement was clear, this would have been a very easy problem.

Posted: Sun Jul 18, 2004 5:49 pm
by Adrian Kuegel
I just say that an animal is predator of another, so they are in same chain. Is this dificult to realize?
Can you show me the part of the problem description that says this? I couldn't find it when rereading the problem.

Posted: Sun Jul 18, 2004 5:51 pm
by jpfarias
Sorry if the problem statement was not thet clear... That was the first problem I've wrote.

I try to be more clear if I come to be the problemsetter again.

Now I see that it's a little difficult to switch from problemsolver to problemsetter. I was thinking on the solution while I was writing the problem description and forgot to think if the problem was that clear.

JP.

Posted: Sun Jul 18, 2004 5:54 pm
by jpfarias
You're right! I did not told anywhere that if a is predator of b then they are in the same chain.

But if you can't realize that, all the thing lose it's sense, right?

JP.