10395 - Titans in Danger

[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]

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]

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]

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]

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]

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]

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. anyways, no complaints anymore, i've got AC [ all the thanx to Adrian ]

[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]

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]

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]

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.

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]

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

[Andrey Mokhov]

Thanks a lot, Adrian!
I got AC

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]

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]

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