10395 - Titans in Danger

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

Moderator: Board moderators

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

10395 - Titans in Danger

Post by Adil »

hello there.

10395 problem states:
No two Titans will have the same initial character in the name
but i cheaked it, and there seems to be multiple occurances of the same character in the input. the problem statement should probably be changed, or the judge input should be changed.

i might be wrong, but i dont think i am.

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

to those who got AC, what's the output for "aab" and "aabb"?

mine gives:

aab
baa
aba

......and

aabb
baab
abab
bbaa
abba
baba

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan »

I think you are getting it all wrong. Plz check I don't think there are two same characters in a string. Mine one got AC.

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

there aren't any duplicate characters? the following program shouldn't get Run-Time error unless there's duplicate characters in the input. and guess what, it does get Runtime Error (SIGSEGV) for 10395.

[c]#include <stdio.h>

char str[100];

void main()
{
while(gets(str))
{
char *s = str, *t;

while(*s)
{
t = s+1;
while(*t)
{
if(*t == *s)
{
t = 0;
*t = 12;
}
t++;
}
s++;
}
}
}
[/c]

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

Post by Adrian Kuegel »

You are right, I checked it, too and found that there must be test cases with repeated letters.
Here is my output for your input:
aab
aab
baa
aba
aba
baa

aabb
aabb
baab
abab
abab
baab
baab
abab
abab
baab
aabb
aabb
abba
baba
baba
abba
bbaa
bbaa
bbaa
bbaa
abba
baba
baba
abba

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

I know

Post by shahriar_manzoor »

Yes we found the bug during the realtime contest and fixed it and rejudged all solutions. But the fix was not made for the Online Judge. As we were so busy with the realtime contest. The strange point is if you use the algorithm you r supposed to use u will get accepted

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

yes. that's the case. i was getting WA because i was going the wrong way, and that made me look for holes in the problem-statements. :lol: anyways, no complaints anymore, i've got AC [ all the thanx to Adrian ]

Dan Adkins
New poster
Posts: 1
Joined: Fri Nov 08, 2002 3:41 am

Post by Dan Adkins »

In addition to the bug already mentioned in the problem statement, I'm confused by the following statement:
Whenever the stone rises, the leftmost Titan loves to start.
What does that mean? At first, I thought it meant that the leftmost Titan *always* had to move. But, the sample data contradicts that:
...
gurcoth
gcruoth
...
So, what does that statement mean?

And, is the problem to generate all permutations using only swap? My program does that (I checked the output for all posible lengths of input) but doesn't pass. Is there some other restriction on the sequence of permutations?

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

Post by Adrian Kuegel »

Yes, you only have to generate permutations using swaps.
Whenever the stone rises, the leftmost Titan loves to start.
This means that the left character has to be swapped whenever it is possible. I can send you my output for the cases abcde and abcdef if you want. I used a recursive function with parameter length that permutates the array by calling the function with length-1 and swapping in between (here are two cases, one for length even, one for length odd).

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post by SnapDragon »

This question is horribly badly worded... he WANTS you to choose your permutations in a certain way, but he gives you absolutely no useful description of what that way is, and the sample output he gives you isn't sufficient. As was pointed out, the sample output has gurcoth-gcruoth when gurcoth-curgoth would also have been possible... so it's not true that the "leftmost Titan loves to start".

Basically, it amounts to "with no description, guess exactly the same weird permutation function that I've written". Horrific.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

anyway WA... ;(

Post by Andrey Mokhov »

My program gives the right sample output (at least the right parts of it that are given in the problem statement). It also works correctly on the input/output given by Adrian Kuegel.

I use recursive method and my function works depending on whether length of the string is odd or even, as was said in the Board.

But judges don't like my program. It gets WA. :cry:

Can anyone say if there is something special with the problem that wasn't said in the problem statement and in the Board?

I don't want to ask for the outputs for strings like 'abcdefgh' or 'abcdefghi' - 'cause it's like giving correct program... and also as the Board is not infinite to hold'em in.

But I think that output for 'abcd' can be given and I'll be very glad if someone would give it.

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

Post by Adrian Kuegel »

Here is my output for abcd and abcdef:
http://www.wohnheim.uni-ulm.de/~akuegel/out.txt

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

That was really bad problem...

Post by Andrey Mokhov »

Thanks a lot, Adrian!
I got AC :D

This problem is really strange, especially its statement.
I generated perms in the wrong way for 'abcdef' case.

To my mind your output should be included to the problem statement.

Thanks again and again!

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

10395

Post by dwyak »

Whenever the stone rises, the leftmost Titan loves to start.
gurcoth
gcruoth
~~~~~~
Why to exchange 'u' & 'c'? According to the problem description, 'g' (the leftmost Titan) should be start.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov »

The problem is that if 'g' starts then soon you will get in situation when you won't be able to make any move. That's why you must swap 'u' and 'c'.

Post Reply

Return to “Volume 103 (10300-10399)”