976 - Bridge Building

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

Moderator: Board moderators

Post Reply
User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

976 - Bridge Building

Post by rio » Mon Nov 20, 2006 8:38 am

I've got AC, but still thinking this problem.

My code uses 3336 memory, and I want to reduce it.

In my algorithm (I thinsk it's a straight-foward one), the first step is calculating
the distance from bank to bank for each column. For this, I have to buff all the
map, so I used "char map[1000][1000]", and the memory already exceeds 3000.

There are someguys uisng only 2000~ memory. So I wonder, how could they do that.
I tried to determine the bnak-to-bank distance without buffering all the map,
but still ....

Any hint, advice, idea or other approch helps me.
Thanks in advance.
----
Sory for my poor English.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Nov 20, 2006 2:26 pm

My code uses 2336 memory, and I have also used 'char a[1000][1000]'. So, I think that you are using more memory in other calculations. There can be at most 100 bridges. So, to store them I have used another array 'int sv[100][1000]'. Hope these help.
Ami ekhono shopno dekhi...
HomePage

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Nov 20, 2006 3:39 pm

Thanks, Jan. You're right. The arrays doesn't take so memory.
I'm a stupid. My recursive function was eating the memory.

----
Addtion.
I rewrite the recursive function to non-recusive function, and able to
reduce the memory to 1392.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 976 - Bridge Building

Post by DJWS » Sun Apr 13, 2008 9:08 am

Does the input data contain such a case that the two terrain are twisted?

Code: Select all

####################
..######............
....##....#########.
.....##........####.
.....#######....####
.........##.....####
..######.......#####
####################

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 976 - Bridge Building

Post by Jan » Mon Apr 14, 2008 1:09 am

I don't think so. Because the problem states...
You can also be sure that on the same column of the grid map, there will never be a south piece of the bank above a north one
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 9 (900-999)”