10475 - Help the Leaders

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10475 - WA ...

Post by Dominik Michniewski » Mon Apr 14, 2003 9:53 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Mon Apr 14, 2003 12:29 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Apr 14, 2003 1:05 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Apr 14, 2003 3:16 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Apr 18, 2003 8:10 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Apr 18, 2003 10:18 am

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
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

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

Post by little joey » Fri Apr 18, 2003 10:27 am

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!

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

Post by little joey » Fri Apr 18, 2003 10:31 am

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Apr 18, 2003 10:59 am

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

Thanks for help :)
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Apr 18, 2003 11:21 am

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

:cry: :cry: :cry: :cry:

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

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon May 02, 2005 8:38 am

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.
If only I had as much free time as I did in college...

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Mon May 02, 2005 11:23 am

Abednego wrote: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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10475 - Help the Leaders

Post by helloneo » Sun Dec 11, 2005 8:36 pm

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

Code: Select all

CUT AFTER AC..
Last edited by helloneo on Tue May 22, 2007 8:01 am, edited 2 times in total.

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

Post by DongJoo Kim » Wed Dec 28, 2005 11:24 am

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Dec 28, 2005 6:59 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”