10307 - Killing Aliens in Borg Maze

[danifart]

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]

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]

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

[danifart]

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

[Larry]

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]

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

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

[danifart]

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]

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

[CDiMa]

Finally I got it ... (Accepted)

Well done, Dominik!!!

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]

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

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

[CDiMa]

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

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.

4. run union algorithm to create MST

Is this kruskal's? I guess so.

5. printf result

Here we differ... I printf wrong result

Well, I'll continue testing...

Ciao!!!

Claudio

[CDiMa]

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]

Well, finally I made it.
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!!!
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?

Ciao!!!

Claudio

[popel]

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.