10307 - Killing Aliens in Borg Maze

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

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm

10307 - Killing Aliens in Borg Maze(+100 hours) (2)

Post by danifart » Mon Apr 19, 2004 8:45 pm

Wow, it seems that the original post crashed! (Time Limit Exceeded x__DDDD). Ok, I wrote the following test case:

20 24
###################
# # # #
# ####A A#### #
# A # # # # A #
# A# # # #A #
# A # #A# # A #
# # ### ### # #
######A A S A A####
#AA A# ### ### # #
# A # #A# # A #
####AAA# # # #A #
# A A# # # # A #
# ####A A#### #
# # # #
# # # #
# #
# AA A #
# #
# #
# A #
# #
# #
# AA A #
###################

Which my program cannot complete, it runs out of memory! :O.
However, the judge gives me wrong answer so my mistake isn't there (or not yet :p). Can anyone break my program??

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm

Post by danifart » Mon Apr 19, 2004 8:48 pm

Again, the test case...:

Code: Select all

20 24
###################
#      #     #    #
#   ####A   A#### #
#   A  # # # #  A #
#     A# # # #A   #
#   A  # #A# #  A #
#    # ### ### #  #
######A A S A A####
#AA A# ### ### #  #
# A    # #A# #  A #
####AAA# # # #A   #
#   A A# # # #  A #
#   ####A   A#### #
#      #     #    #
#      #     #    #
#                 #
# AA  A           #
#                 #
#                 #
#  A              #
#                 #
#                 #
# AA  A           #
###################

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

Post by Dominik Michniewski » Mon Apr 19, 2004 10:14 pm

Three things:
1. !!!!!!!! PLESAE REMOVE YOUR CODE FROM THIS THREAD !!!! in other case this thread stops as one before ...
2. My program outputs 90 for your test case ...
3. Please post me last test case (first, which you post)

Maybe any other guru tell what result he does ??

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)

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm

Post by danifart » Tue Apr 20, 2004 12:40 am

How did you do to find the minimum distance between nodes?

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

Post by Larry » Tue Apr 20, 2004 2:07 am

With relatively good comments, my code is about 120 lines. I don't expect anyone to read through your code to see what you're trying to do, so instead, explain your algorithm if you want someone to break it..

As for the "correct" solution, there are enough threads that go into it, so do a search and it isn't so bad.

DM:

For the input, I get:

87

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue Apr 20, 2004 9:32 am

Larry wrote:As for the "correct" solution, there are enough threads that go into it, so do a search and it isn't so bad.

DM:

For the input, I get:

87
For a while I thought that my program was much better since it gave 79 8)
I made a mistake cut and pasting the sample input and dropped a space at the end of the line.
After filling the lines so that each one had the expected 20 characters my prog gives 87 too.
So it starts to get intriguing... why does my prog get WA?

Does the judge's input have truncated lines? The problem statement clearly says that the input has y lines each of x characters...

Ciao!!!

Claudio

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

Post by Dominik Michniewski » Tue Apr 20, 2004 6:13 pm

Finally I got it ... (Accepted)

I have a little mistake in my code, when I search aliens on board :(

So, MST is good approach to solve this question. I agree with Larry - my code has only 130 lines of code, and I think that's enough :-) My code now output 87 for your input Danifart :-)

To CDiMa: my code use width and height of plane only for searching aliens on board. So if judge has data i.e.

Code: Select all

7 3
####
#AS#
####
my program will work fine :) It's possible, because perimeter of maze is always closed. I use gets() to read whiole lines, so I don't carre how long are they :)

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)

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm

Post by danifart » Tue Apr 20, 2004 7:31 pm

How did you do to find the minimum distance between Aliens? My spanning tree only works when the map is small, but with my test case it overflows!

Thx.

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

Post by Dominik Michniewski » Tue Apr 20, 2004 9:04 pm

I just run BFS for every founded alien and start point and find length of shortest path to every other alien/start point - it's possible to optimalize this approach, but I'm to lasy to do this ;-)
if you use BFS, additional memory which is neccessary has only size O(N^2) where N is number of indywiduals on baord

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)

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Apr 21, 2004 9:21 am

Dominik Michniewski wrote:Finally I got it ... (Accepted)
Well done, Dominik!!!
Dominik Michniewski wrote:To CDiMa: my code use width and height of plane only for searching aliens on board. So if judge has data i.e.

Code: Select all

7 3
####
#AS#
####
my program will work fine :) It's possible, because perimeter of maze is always closed. I use gets() to read whiole lines, so I don't carre how long are they :)
Hmmm... Well, I changed my prog so that it handles incomplete lines. Now it gives 87 on the sample of danifart without padding the lines, but still WA for me.

Maybe you can post some other input/output that you used?

Ciao!!!

Claudio

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

Post by Dominik Michniewski » Wed Apr 21, 2004 2:46 pm

I'm very sorry , but I onlyuse three inputs: two from sample input and one of danifart - in last one I found my mistake :oops:

Maybe helps, if I describe my algorithm (but it's spoiler ... ):
1. read data ;-)
2. run bfs for every alien and start point - I find in such way distances between any to aliens or alien and start point
3. sort this distances by length ascending
4. run union algorithm to create MST
5. printf result :-)

Steps 1 and 5 are easy ;-)

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)

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Wed Apr 21, 2004 3:11 pm

Dominik Michniewski wrote:Maybe helps, if I describe my algorithm (but it's spoiler ... ):
1. read data ;-)
I'm doing this also, but I'm looking for an algo that telepatically collects the input. Should improve run times significantly ;)
Dominik Michniewski wrote:2. run bfs for every alien and start point - I find in such way distances between any to aliens or alien and start point
3. sort this distances by length ascending
I do in a single step both of these, i.e. I store the edges between aliens in distance order.
Dominik Michniewski wrote:4. run union algorithm to create MST
Is this kruskal's? I guess so.
Dominik Michniewski wrote:5. printf result :-)
Here we differ... I printf wrong result 8)

Well, I'll continue testing...

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Fri Apr 23, 2004 10:39 am

CDiMa wrote:
Dominik Michniewski wrote:2. run bfs for every alien and start point - I find in such way distances between any to aliens or alien and start point
3. sort this distances by length ascending
I do in a single step both of these, i.e. I store the edges between aliens in distance order.
Well, my mistake was here. Array short by one. If there were 100 aliens my prog ended up giving wrong answers.

Thanks for all who helped.

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

10307 making borg 10x faster.

Post by CDiMa » Fri Apr 23, 2004 10:58 am

Well, finally I made it. :D
My prog solves 10307 in .2 but I see that many people do it 10 times faster, not to mention the fastest one that does it in .006!!! :o
Runtime of my program is dominated by building the distance array between aliens.
I'm doing a BFS search starting from each alien. Is there a significantly faster way of doing this? :roll:

Ciao!!!

Claudio

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Location: Dhaka, Bangladesh
Contact:

Post by popel » Sun May 29, 2005 11:44 am

Refer to "The C Programming Language" by Kernighan & Ritchie
2nd Edition - Chapter - 6, page - 138
The Language definition does guarantee, however, that pointer arithmatic that involves the first element beyond the end of an array will work properly.
μδ. ταηνιπ αλ αμιη

Post Reply

Return to “Volume 103 (10300-10399)”