10475 - Help the Leaders

[Dominik Michniewski]

I try to solve (I think easy) this problem, but I got WA several times ....
Maybe someone tell me some special IO ?

I use folowing algorithm:
when I read input, I sort topics by length and lexicographily if necessary.
I create matrix with all possible topics and I mark prohibited pairs in them (when t1 and t2 is placed as constraint, both matrix[t1][t2] and matrix[t2][t1] are marked)
after that I generate all possible group of topics.

Is this algorithm wrong?
Maybe someone want to take a look at my code ?

Best regards
DM

[kmhasan]

The only thing I can think of is that you could have missed the line:

Topics should be considered case insensitive. While printing the topics print all the characters as uppercase.

[Dominik Michniewski]

I do it by uppercase all letters when I read it but I got WA instead of this ...
I don't have any more ideas (

Any hint more ?

Regards
DM

[Larry]

There are many potential for silly mistakes with cases and things (like printing them back out, etc..).. it took me awhile, and I just started from scratch.. maybe you could do the same and be more careful?

[Dominik Michniewski]

Could anyone tell me:
FOr this input:

Code: Select all

9 3 5
a
b
c
aa
bb
cc
aaa
bbb
ccc
a aa
bb bbb
ccc c

this output is correct ?

Code: Select all

Set 1:
AAA BBB CCC AA BB
AAA BBB CCC AA CC
AAA BBB CCC AA A
AAA BBB CCC AA B
AAA BBB CCC AA C
AAA BBB CCC BB CC
AAA BBB CCC BB A
AAA BBB CCC BB B
AAA BBB CCC BB C
AAA BBB CCC CC A
AAA BBB CCC CC B
AAA BBB CCC CC C
AAA BBB CCC A B
AAA BBB CCC A C
AAA BBB CCC B C
AAA BBB AA BB CC
AAA BBB AA BB A
AAA BBB AA BB B
AAA BBB AA BB C
AAA BBB AA CC A
AAA BBB AA CC B
AAA BBB AA CC C
AAA BBB AA A B
AAA BBB AA A C
AAA BBB AA B C
AAA BBB BB CC A
AAA BBB BB CC B
AAA BBB BB CC C
AAA BBB BB A B
AAA BBB BB A C
AAA BBB BB B C
AAA BBB CC A B
AAA BBB CC A C
AAA BBB CC B C
AAA BBB A B C
AAA CCC AA BB CC
AAA CCC AA BB A
AAA CCC AA BB B
AAA CCC AA BB C
AAA CCC AA CC A
AAA CCC AA CC B
AAA CCC AA CC C
AAA CCC AA A B
AAA CCC AA A C
AAA CCC AA B C
AAA CCC BB CC A
AAA CCC BB CC B
AAA CCC BB CC C
AAA CCC BB A B
AAA CCC BB A C
AAA CCC BB B C
AAA CCC CC A B
AAA CCC CC A C
AAA CCC CC B C
AAA CCC A B C
AAA AA BB CC A
AAA AA BB CC B
AAA AA BB CC C
AAA AA BB A B
AAA AA BB A C
AAA AA BB B C
AAA AA CC A B
AAA AA CC A C
AAA AA CC B C
AAA AA A B C
AAA BB CC A B
AAA BB CC A C
AAA BB CC B C
AAA BB A B C
AAA CC A B C
BBB CCC AA CC A
BBB CCC AA CC B
BBB CCC AA CC C
BBB CCC AA A B
BBB CCC AA A C
BBB CCC AA B C
BBB CCC CC A B
BBB CCC CC A C
BBB CCC CC B C
BBB CCC A B C
BBB AA CC A B
BBB AA CC A C
BBB AA CC B C
BBB AA A B C
BBB CC A B C
CCC AA BB CC A
CCC AA BB CC B
CCC AA BB A B
CCC AA CC A B
CCC BB CC A B
AA BB CC B C
BB CC A B C

I'm really frustrated with this problem. It should be easy, but I got WA. Maybe I'm doing something wrong with output ?

Please help
DM

[..]

Here is my output:
Set 1:
AAA BBB CCC AA CC
AAA BBB CCC AA B
AAA BBB CCC CC A
AAA BBB CCC CC B
AAA BBB CCC A B
AAA BBB AA CC B
AAA BBB AA CC C
AAA BBB AA B C
AAA BBB CC A B
AAA BBB CC A C
AAA BBB CC B C
AAA BBB A B C
AAA CCC AA BB CC
AAA CCC AA BB B
AAA CCC AA CC B
AAA CCC BB CC A
AAA CCC BB CC B
AAA CCC BB A B
AAA CCC CC A B
AAA AA BB CC B
AAA AA BB CC C
AAA AA BB B C
AAA AA CC B C
AAA BB CC A B
AAA BB CC A C
AAA BB CC B C
AAA BB A B C
AAA CC A B C
BBB CCC AA CC B
BBB CCC CC A B
BBB AA CC B C
BBB CC A B C
CCC AA BB CC B
CCC BB CC A B
AA BB CC B C
BB CC A B C

[little joey]

There are no tricks here. Everything is strickly as described on the problem page. There is no dirty input. I know that is the most frustrating, because it means your code is incorrect.
I had 10 or so WA's before I discovered a stupid mistake in my sorting code. A mistake in code that you wrote hundreds of times is the hardest to find.
Just go over your code, line by line and take a close look. You'll find your mistake and kick yourself. Or take Larry's advise and start all over again, preferably with a totaly different approach.

One silly little testcase:

Code: Select all

1
3 0 3
Abc
aBa
007

it should give: 007 ABA ABC

Happy hunting!

[little joey]

To ..
Our post must have crossed. You're absolutely right!

[Dominik Michniewski]

Hmmmm
I probably know, what I'm doing wrong ... I try to rewrite code ...

Thanks for help
DM

[Dominik Michniewski]

Silly mistake !!!
I forgot to check this condition:
If we could say obout X, check if other topics isn't in comstraints ...



But now I'm got Accepted !!!
Thanks all again )

DM

[Abednego]

Wow. I can't believe this silly little problem caused so much trouble to so many people. I spent a long time trying to solve it. Then I left it for 2 years, and now I went back to it and spent some more time (and WA submissions). Finally, I found that I forgot to convert the forbidden pairs to upper case! Dominik, thanks for your test case. It helped.

[Gigi's Baby]

Wow. I can't believe this silly little problem caused so much trouble to so many people. I spent a long time trying to solve it. Then I left it for 2 years, and now I went back to it and spent some more time (and WA submissions). Finally, I found that I forgot to convert the forbidden pairs to upper case! Dominik, thanks for your test case. It helped.

I made the same mistake and got WA many times...

[helloneo]

looks like so simple..
is there any triky case..?
i don't see why WA.. ;

Code: Select all

CUT AFTER AC..

[DongJoo Kim]

for (i = u+1; i < t; i++) {
if (map1 == 0 && check == 0) {
check = 1;
dfs(i, cnt+1);
check = 0;
}
}

I think this part is quite dangerous, because you only check current topic with next topic.

I changed this part of your code and got AC.

[helloneo]

Thanks..~ I got AC.. ^^;