10681 - Teobaldo's Trip

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

alex[LSD]
Learning poster
Posts: 53
Joined: Sat Jan 24, 2004 9:22 pm
Location: Tomsk, Siberia, RUSSIA
Contact:

10681 - Teobaldo's Trip

Post by alex[LSD] » Sun Jul 18, 2004 5:56 am

: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.
The more contests are held, the happier I am.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Sun Jul 18, 2004 11:15 am

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:
You should never take more than you give in the circle of life.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 12:05 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Jul 18, 2004 12:51 pm

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...

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Sun Jul 18, 2004 3:16 pm

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.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Jul 18, 2004 3:48 pm

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
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:26 pm

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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:29 pm

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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:32 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 5:33 pm

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?

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:44 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 5:46 pm

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jul 18, 2004 5:49 pm

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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:51 pm

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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 18, 2004 5:54 pm

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.

Post Reply

Return to “Volume 106 (10600-10699)”