Discussion @ 1287. Mars Canals @ Timus Online Judge

How to solve this problem using <1MB memory?

Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 19 Aug 2010 15:32

I used only ~2MB in C#, but want to know how to improve it.
Thx.

Re: How to solve this problem using <1MB memory?

Posted by Vedernikoff Sergey (HSE: АОП) 19 Aug 2010 21:15

The problem can be solved in O(N) memory. Just read line-by-line and calculate something =)

Re: How to solve this problem using <1MB memory?

Posted by Andrew Hoffmann aka SKYDOS [Vladimir SU] 19 Aug 2010 21:18

I did a little bit different: I saved NxN matrix using BitArray and after that used 2xN array to culc answers, but I see that its even possible to solve this problem without saving all matrix at all, just 2xN array.

Discussion of Problem 1287. Mars Canals